Merge git://git.kernel.org/pub/scm/linux/kernel/git/mingo/linux-2.6-sched
[linux-2.6] / 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/ext4_jbd2.h>
36 #include <linux/jbd2.h>
37 #include <linux/highuid.h>
38 #include <linux/pagemap.h>
39 #include <linux/quotaops.h>
40 #include <linux/string.h>
41 #include <linux/slab.h>
42 #include <linux/falloc.h>
43 #include <linux/ext4_fs_extents.h>
44 #include <asm/uaccess.h>
45
46
47 /*
48  * ext_pblock:
49  * combine low and high parts of physical block number into ext4_fsblk_t
50  */
51 static ext4_fsblk_t ext_pblock(struct ext4_extent *ex)
52 {
53         ext4_fsblk_t block;
54
55         block = le32_to_cpu(ex->ee_start_lo);
56         block |= ((ext4_fsblk_t) le16_to_cpu(ex->ee_start_hi) << 31) << 1;
57         return block;
58 }
59
60 /*
61  * idx_pblock:
62  * combine low and high parts of a leaf physical block number into ext4_fsblk_t
63  */
64 static ext4_fsblk_t idx_pblock(struct ext4_extent_idx *ix)
65 {
66         ext4_fsblk_t block;
67
68         block = le32_to_cpu(ix->ei_leaf_lo);
69         block |= ((ext4_fsblk_t) le16_to_cpu(ix->ei_leaf_hi) << 31) << 1;
70         return block;
71 }
72
73 /*
74  * ext4_ext_store_pblock:
75  * stores a large physical block number into an extent struct,
76  * breaking it into parts
77  */
78 static void ext4_ext_store_pblock(struct ext4_extent *ex, ext4_fsblk_t pb)
79 {
80         ex->ee_start_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff));
81         ex->ee_start_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) & 0xffff);
82 }
83
84 /*
85  * ext4_idx_store_pblock:
86  * stores a large physical block number into an index struct,
87  * breaking it into parts
88  */
89 static void ext4_idx_store_pblock(struct ext4_extent_idx *ix, ext4_fsblk_t pb)
90 {
91         ix->ei_leaf_lo = cpu_to_le32((unsigned long) (pb & 0xffffffff));
92         ix->ei_leaf_hi = cpu_to_le16((unsigned long) ((pb >> 31) >> 1) & 0xffff);
93 }
94
95 static handle_t *ext4_ext_journal_restart(handle_t *handle, int needed)
96 {
97         int err;
98
99         if (handle->h_buffer_credits > needed)
100                 return handle;
101         if (!ext4_journal_extend(handle, needed))
102                 return handle;
103         err = ext4_journal_restart(handle, needed);
104
105         return handle;
106 }
107
108 /*
109  * could return:
110  *  - EROFS
111  *  - ENOMEM
112  */
113 static int ext4_ext_get_access(handle_t *handle, struct inode *inode,
114                                 struct ext4_ext_path *path)
115 {
116         if (path->p_bh) {
117                 /* path points to block */
118                 return ext4_journal_get_write_access(handle, path->p_bh);
119         }
120         /* path points to leaf/index in inode body */
121         /* we use in-core data, no need to protect them */
122         return 0;
123 }
124
125 /*
126  * could return:
127  *  - EROFS
128  *  - ENOMEM
129  *  - EIO
130  */
131 static int ext4_ext_dirty(handle_t *handle, struct inode *inode,
132                                 struct ext4_ext_path *path)
133 {
134         int err;
135         if (path->p_bh) {
136                 /* path points to block */
137                 err = ext4_journal_dirty_metadata(handle, path->p_bh);
138         } else {
139                 /* path points to leaf/index in inode body */
140                 err = ext4_mark_inode_dirty(handle, inode);
141         }
142         return err;
143 }
144
145 static ext4_fsblk_t ext4_ext_find_goal(struct inode *inode,
146                               struct ext4_ext_path *path,
147                               ext4_fsblk_t block)
148 {
149         struct ext4_inode_info *ei = EXT4_I(inode);
150         ext4_fsblk_t bg_start;
151         ext4_grpblk_t colour;
152         int depth;
153
154         if (path) {
155                 struct ext4_extent *ex;
156                 depth = path->p_depth;
157
158                 /* try to predict block placement */
159                 ex = path[depth].p_ext;
160                 if (ex)
161                         return ext_pblock(ex)+(block-le32_to_cpu(ex->ee_block));
162
163                 /* it looks like index is empty;
164                  * try to find starting block from index itself */
165                 if (path[depth].p_bh)
166                         return path[depth].p_bh->b_blocknr;
167         }
168
169         /* OK. use inode's group */
170         bg_start = (ei->i_block_group * EXT4_BLOCKS_PER_GROUP(inode->i_sb)) +
171                 le32_to_cpu(EXT4_SB(inode->i_sb)->s_es->s_first_data_block);
172         colour = (current->pid % 16) *
173                         (EXT4_BLOCKS_PER_GROUP(inode->i_sb) / 16);
174         return bg_start + colour + block;
175 }
176
177 static ext4_fsblk_t
178 ext4_ext_new_block(handle_t *handle, struct inode *inode,
179                         struct ext4_ext_path *path,
180                         struct ext4_extent *ex, int *err)
181 {
182         ext4_fsblk_t goal, newblock;
183
184         goal = ext4_ext_find_goal(inode, path, le32_to_cpu(ex->ee_block));
185         newblock = ext4_new_block(handle, inode, goal, err);
186         return newblock;
187 }
188
189 static int ext4_ext_space_block(struct inode *inode)
190 {
191         int size;
192
193         size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
194                         / sizeof(struct ext4_extent);
195 #ifdef AGGRESSIVE_TEST
196         if (size > 6)
197                 size = 6;
198 #endif
199         return size;
200 }
201
202 static int ext4_ext_space_block_idx(struct inode *inode)
203 {
204         int size;
205
206         size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
207                         / sizeof(struct ext4_extent_idx);
208 #ifdef AGGRESSIVE_TEST
209         if (size > 5)
210                 size = 5;
211 #endif
212         return size;
213 }
214
215 static int ext4_ext_space_root(struct inode *inode)
216 {
217         int size;
218
219         size = sizeof(EXT4_I(inode)->i_data);
220         size -= sizeof(struct ext4_extent_header);
221         size /= sizeof(struct ext4_extent);
222 #ifdef AGGRESSIVE_TEST
223         if (size > 3)
224                 size = 3;
225 #endif
226         return size;
227 }
228
229 static int ext4_ext_space_root_idx(struct inode *inode)
230 {
231         int size;
232
233         size = sizeof(EXT4_I(inode)->i_data);
234         size -= sizeof(struct ext4_extent_header);
235         size /= sizeof(struct ext4_extent_idx);
236 #ifdef AGGRESSIVE_TEST
237         if (size > 4)
238                 size = 4;
239 #endif
240         return size;
241 }
242
243 static int
244 ext4_ext_max_entries(struct inode *inode, int depth)
245 {
246         int max;
247
248         if (depth == ext_depth(inode)) {
249                 if (depth == 0)
250                         max = ext4_ext_space_root(inode);
251                 else
252                         max = ext4_ext_space_root_idx(inode);
253         } else {
254                 if (depth == 0)
255                         max = ext4_ext_space_block(inode);
256                 else
257                         max = ext4_ext_space_block_idx(inode);
258         }
259
260         return max;
261 }
262
263 static int __ext4_ext_check_header(const char *function, struct inode *inode,
264                                         struct ext4_extent_header *eh,
265                                         int depth)
266 {
267         const char *error_msg;
268         int max = 0;
269
270         if (unlikely(eh->eh_magic != EXT4_EXT_MAGIC)) {
271                 error_msg = "invalid magic";
272                 goto corrupted;
273         }
274         if (unlikely(le16_to_cpu(eh->eh_depth) != depth)) {
275                 error_msg = "unexpected eh_depth";
276                 goto corrupted;
277         }
278         if (unlikely(eh->eh_max == 0)) {
279                 error_msg = "invalid eh_max";
280                 goto corrupted;
281         }
282         max = ext4_ext_max_entries(inode, depth);
283         if (unlikely(le16_to_cpu(eh->eh_max) > max)) {
284                 error_msg = "too large eh_max";
285                 goto corrupted;
286         }
287         if (unlikely(le16_to_cpu(eh->eh_entries) > le16_to_cpu(eh->eh_max))) {
288                 error_msg = "invalid eh_entries";
289                 goto corrupted;
290         }
291         return 0;
292
293 corrupted:
294         ext4_error(inode->i_sb, function,
295                         "bad header in inode #%lu: %s - magic %x, "
296                         "entries %u, max %u(%u), depth %u(%u)",
297                         inode->i_ino, error_msg, le16_to_cpu(eh->eh_magic),
298                         le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max),
299                         max, le16_to_cpu(eh->eh_depth), depth);
300
301         return -EIO;
302 }
303
304 #define ext4_ext_check_header(inode, eh, depth) \
305         __ext4_ext_check_header(__FUNCTION__, inode, eh, depth)
306
307 #ifdef EXT_DEBUG
308 static void ext4_ext_show_path(struct inode *inode, struct ext4_ext_path *path)
309 {
310         int k, l = path->p_depth;
311
312         ext_debug("path:");
313         for (k = 0; k <= l; k++, path++) {
314                 if (path->p_idx) {
315                   ext_debug("  %d->%llu", le32_to_cpu(path->p_idx->ei_block),
316                             idx_pblock(path->p_idx));
317                 } else if (path->p_ext) {
318                         ext_debug("  %d:%d:%llu ",
319                                   le32_to_cpu(path->p_ext->ee_block),
320                                   ext4_ext_get_actual_len(path->p_ext),
321                                   ext_pblock(path->p_ext));
322                 } else
323                         ext_debug("  []");
324         }
325         ext_debug("\n");
326 }
327
328 static void ext4_ext_show_leaf(struct inode *inode, struct ext4_ext_path *path)
329 {
330         int depth = ext_depth(inode);
331         struct ext4_extent_header *eh;
332         struct ext4_extent *ex;
333         int i;
334
335         if (!path)
336                 return;
337
338         eh = path[depth].p_hdr;
339         ex = EXT_FIRST_EXTENT(eh);
340
341         for (i = 0; i < le16_to_cpu(eh->eh_entries); i++, ex++) {
342                 ext_debug("%d:%d:%llu ", le32_to_cpu(ex->ee_block),
343                           ext4_ext_get_actual_len(ex), ext_pblock(ex));
344         }
345         ext_debug("\n");
346 }
347 #else
348 #define ext4_ext_show_path(inode,path)
349 #define ext4_ext_show_leaf(inode,path)
350 #endif
351
352 static void ext4_ext_drop_refs(struct ext4_ext_path *path)
353 {
354         int depth = path->p_depth;
355         int i;
356
357         for (i = 0; i <= depth; i++, path++)
358                 if (path->p_bh) {
359                         brelse(path->p_bh);
360                         path->p_bh = NULL;
361                 }
362 }
363
364 /*
365  * ext4_ext_binsearch_idx:
366  * binary search for the closest index of the given block
367  * the header must be checked before calling this
368  */
369 static void
370 ext4_ext_binsearch_idx(struct inode *inode, struct ext4_ext_path *path, int block)
371 {
372         struct ext4_extent_header *eh = path->p_hdr;
373         struct ext4_extent_idx *r, *l, *m;
374
375
376         ext_debug("binsearch for %d(idx):  ", block);
377
378         l = EXT_FIRST_INDEX(eh) + 1;
379         r = EXT_LAST_INDEX(eh);
380         while (l <= r) {
381                 m = l + (r - l) / 2;
382                 if (block < le32_to_cpu(m->ei_block))
383                         r = m - 1;
384                 else
385                         l = m + 1;
386                 ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ei_block),
387                                 m, le32_to_cpu(m->ei_block),
388                                 r, le32_to_cpu(r->ei_block));
389         }
390
391         path->p_idx = l - 1;
392         ext_debug("  -> %d->%lld ", le32_to_cpu(path->p_idx->ei_block),
393                   idx_pblock(path->p_idx));
394
395 #ifdef CHECK_BINSEARCH
396         {
397                 struct ext4_extent_idx *chix, *ix;
398                 int k;
399
400                 chix = ix = EXT_FIRST_INDEX(eh);
401                 for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ix++) {
402                   if (k != 0 &&
403                       le32_to_cpu(ix->ei_block) <= le32_to_cpu(ix[-1].ei_block)) {
404                                 printk("k=%d, ix=0x%p, first=0x%p\n", k,
405                                         ix, EXT_FIRST_INDEX(eh));
406                                 printk("%u <= %u\n",
407                                        le32_to_cpu(ix->ei_block),
408                                        le32_to_cpu(ix[-1].ei_block));
409                         }
410                         BUG_ON(k && le32_to_cpu(ix->ei_block)
411                                            <= le32_to_cpu(ix[-1].ei_block));
412                         if (block < le32_to_cpu(ix->ei_block))
413                                 break;
414                         chix = ix;
415                 }
416                 BUG_ON(chix != path->p_idx);
417         }
418 #endif
419
420 }
421
422 /*
423  * ext4_ext_binsearch:
424  * binary search for closest extent of the given block
425  * the header must be checked before calling this
426  */
427 static void
428 ext4_ext_binsearch(struct inode *inode, struct ext4_ext_path *path, int block)
429 {
430         struct ext4_extent_header *eh = path->p_hdr;
431         struct ext4_extent *r, *l, *m;
432
433         if (eh->eh_entries == 0) {
434                 /*
435                  * this leaf is empty:
436                  * we get such a leaf in split/add case
437                  */
438                 return;
439         }
440
441         ext_debug("binsearch for %d:  ", block);
442
443         l = EXT_FIRST_EXTENT(eh) + 1;
444         r = EXT_LAST_EXTENT(eh);
445
446         while (l <= r) {
447                 m = l + (r - l) / 2;
448                 if (block < le32_to_cpu(m->ee_block))
449                         r = m - 1;
450                 else
451                         l = m + 1;
452                 ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ee_block),
453                                 m, le32_to_cpu(m->ee_block),
454                                 r, le32_to_cpu(r->ee_block));
455         }
456
457         path->p_ext = l - 1;
458         ext_debug("  -> %d:%llu:%d ",
459                         le32_to_cpu(path->p_ext->ee_block),
460                         ext_pblock(path->p_ext),
461                         ext4_ext_get_actual_len(path->p_ext));
462
463 #ifdef CHECK_BINSEARCH
464         {
465                 struct ext4_extent *chex, *ex;
466                 int k;
467
468                 chex = ex = EXT_FIRST_EXTENT(eh);
469                 for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ex++) {
470                         BUG_ON(k && le32_to_cpu(ex->ee_block)
471                                           <= le32_to_cpu(ex[-1].ee_block));
472                         if (block < le32_to_cpu(ex->ee_block))
473                                 break;
474                         chex = ex;
475                 }
476                 BUG_ON(chex != path->p_ext);
477         }
478 #endif
479
480 }
481
482 int ext4_ext_tree_init(handle_t *handle, struct inode *inode)
483 {
484         struct ext4_extent_header *eh;
485
486         eh = ext_inode_hdr(inode);
487         eh->eh_depth = 0;
488         eh->eh_entries = 0;
489         eh->eh_magic = EXT4_EXT_MAGIC;
490         eh->eh_max = cpu_to_le16(ext4_ext_space_root(inode));
491         ext4_mark_inode_dirty(handle, inode);
492         ext4_ext_invalidate_cache(inode);
493         return 0;
494 }
495
496 struct ext4_ext_path *
497 ext4_ext_find_extent(struct inode *inode, int block, struct ext4_ext_path *path)
498 {
499         struct ext4_extent_header *eh;
500         struct buffer_head *bh;
501         short int depth, i, ppos = 0, alloc = 0;
502
503         eh = ext_inode_hdr(inode);
504         depth = ext_depth(inode);
505         if (ext4_ext_check_header(inode, eh, depth))
506                 return ERR_PTR(-EIO);
507
508
509         /* account possible depth increase */
510         if (!path) {
511                 path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 2),
512                                 GFP_NOFS);
513                 if (!path)
514                         return ERR_PTR(-ENOMEM);
515                 alloc = 1;
516         }
517         path[0].p_hdr = eh;
518
519         i = depth;
520         /* walk through the tree */
521         while (i) {
522                 ext_debug("depth %d: num %d, max %d\n",
523                           ppos, le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
524
525                 ext4_ext_binsearch_idx(inode, path + ppos, block);
526                 path[ppos].p_block = idx_pblock(path[ppos].p_idx);
527                 path[ppos].p_depth = i;
528                 path[ppos].p_ext = NULL;
529
530                 bh = sb_bread(inode->i_sb, path[ppos].p_block);
531                 if (!bh)
532                         goto err;
533
534                 eh = ext_block_hdr(bh);
535                 ppos++;
536                 BUG_ON(ppos > depth);
537                 path[ppos].p_bh = bh;
538                 path[ppos].p_hdr = eh;
539                 i--;
540
541                 if (ext4_ext_check_header(inode, eh, i))
542                         goto err;
543         }
544
545         path[ppos].p_depth = i;
546         path[ppos].p_hdr = eh;
547         path[ppos].p_ext = NULL;
548         path[ppos].p_idx = NULL;
549
550         /* find extent */
551         ext4_ext_binsearch(inode, path + ppos, block);
552
553         ext4_ext_show_path(inode, path);
554
555         return path;
556
557 err:
558         ext4_ext_drop_refs(path);
559         if (alloc)
560                 kfree(path);
561         return ERR_PTR(-EIO);
562 }
563
564 /*
565  * ext4_ext_insert_index:
566  * insert new index [@logical;@ptr] into the block at @curp;
567  * check where to insert: before @curp or after @curp
568  */
569 static int ext4_ext_insert_index(handle_t *handle, struct inode *inode,
570                                 struct ext4_ext_path *curp,
571                                 int logical, ext4_fsblk_t ptr)
572 {
573         struct ext4_extent_idx *ix;
574         int len, err;
575
576         err = ext4_ext_get_access(handle, inode, curp);
577         if (err)
578                 return err;
579
580         BUG_ON(logical == le32_to_cpu(curp->p_idx->ei_block));
581         len = EXT_MAX_INDEX(curp->p_hdr) - curp->p_idx;
582         if (logical > le32_to_cpu(curp->p_idx->ei_block)) {
583                 /* insert after */
584                 if (curp->p_idx != EXT_LAST_INDEX(curp->p_hdr)) {
585                         len = (len - 1) * sizeof(struct ext4_extent_idx);
586                         len = len < 0 ? 0 : len;
587                         ext_debug("insert new index %d after: %llu. "
588                                         "move %d from 0x%p to 0x%p\n",
589                                         logical, ptr, len,
590                                         (curp->p_idx + 1), (curp->p_idx + 2));
591                         memmove(curp->p_idx + 2, curp->p_idx + 1, len);
592                 }
593                 ix = curp->p_idx + 1;
594         } else {
595                 /* insert before */
596                 len = len * sizeof(struct ext4_extent_idx);
597                 len = len < 0 ? 0 : len;
598                 ext_debug("insert new index %d before: %llu. "
599                                 "move %d from 0x%p to 0x%p\n",
600                                 logical, ptr, len,
601                                 curp->p_idx, (curp->p_idx + 1));
602                 memmove(curp->p_idx + 1, curp->p_idx, len);
603                 ix = curp->p_idx;
604         }
605
606         ix->ei_block = cpu_to_le32(logical);
607         ext4_idx_store_pblock(ix, ptr);
608         curp->p_hdr->eh_entries = cpu_to_le16(le16_to_cpu(curp->p_hdr->eh_entries)+1);
609
610         BUG_ON(le16_to_cpu(curp->p_hdr->eh_entries)
611                              > le16_to_cpu(curp->p_hdr->eh_max));
612         BUG_ON(ix > EXT_LAST_INDEX(curp->p_hdr));
613
614         err = ext4_ext_dirty(handle, inode, curp);
615         ext4_std_error(inode->i_sb, err);
616
617         return err;
618 }
619
620 /*
621  * ext4_ext_split:
622  * inserts new subtree into the path, using free index entry
623  * at depth @at:
624  * - allocates all needed blocks (new leaf and all intermediate index blocks)
625  * - makes decision where to split
626  * - moves remaining extents and index entries (right to the split point)
627  *   into the newly allocated blocks
628  * - initializes subtree
629  */
630 static int ext4_ext_split(handle_t *handle, struct inode *inode,
631                                 struct ext4_ext_path *path,
632                                 struct ext4_extent *newext, int at)
633 {
634         struct buffer_head *bh = NULL;
635         int depth = ext_depth(inode);
636         struct ext4_extent_header *neh;
637         struct ext4_extent_idx *fidx;
638         struct ext4_extent *ex;
639         int i = at, k, m, a;
640         ext4_fsblk_t newblock, oldblock;
641         __le32 border;
642         ext4_fsblk_t *ablocks = NULL; /* array of allocated blocks */
643         int err = 0;
644
645         /* make decision: where to split? */
646         /* FIXME: now decision is simplest: at current extent */
647
648         /* if current leaf will be split, then we should use
649          * border from split point */
650         BUG_ON(path[depth].p_ext > EXT_MAX_EXTENT(path[depth].p_hdr));
651         if (path[depth].p_ext != EXT_MAX_EXTENT(path[depth].p_hdr)) {
652                 border = path[depth].p_ext[1].ee_block;
653                 ext_debug("leaf will be split."
654                                 " next leaf starts at %d\n",
655                                   le32_to_cpu(border));
656         } else {
657                 border = newext->ee_block;
658                 ext_debug("leaf will be added."
659                                 " next leaf starts at %d\n",
660                                 le32_to_cpu(border));
661         }
662
663         /*
664          * If error occurs, then we break processing
665          * and mark filesystem read-only. index won't
666          * be inserted and tree will be in consistent
667          * state. Next mount will repair buffers too.
668          */
669
670         /*
671          * Get array to track all allocated blocks.
672          * We need this to handle errors and free blocks
673          * upon them.
674          */
675         ablocks = kzalloc(sizeof(ext4_fsblk_t) * depth, GFP_NOFS);
676         if (!ablocks)
677                 return -ENOMEM;
678
679         /* allocate all needed blocks */
680         ext_debug("allocate %d blocks for indexes/leaf\n", depth - at);
681         for (a = 0; a < depth - at; a++) {
682                 newblock = ext4_ext_new_block(handle, inode, path, newext, &err);
683                 if (newblock == 0)
684                         goto cleanup;
685                 ablocks[a] = newblock;
686         }
687
688         /* initialize new leaf */
689         newblock = ablocks[--a];
690         BUG_ON(newblock == 0);
691         bh = sb_getblk(inode->i_sb, newblock);
692         if (!bh) {
693                 err = -EIO;
694                 goto cleanup;
695         }
696         lock_buffer(bh);
697
698         err = ext4_journal_get_create_access(handle, bh);
699         if (err)
700                 goto cleanup;
701
702         neh = ext_block_hdr(bh);
703         neh->eh_entries = 0;
704         neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode));
705         neh->eh_magic = EXT4_EXT_MAGIC;
706         neh->eh_depth = 0;
707         ex = EXT_FIRST_EXTENT(neh);
708
709         /* move remainder of path[depth] to the new leaf */
710         BUG_ON(path[depth].p_hdr->eh_entries != path[depth].p_hdr->eh_max);
711         /* start copy from next extent */
712         /* TODO: we could do it by single memmove */
713         m = 0;
714         path[depth].p_ext++;
715         while (path[depth].p_ext <=
716                         EXT_MAX_EXTENT(path[depth].p_hdr)) {
717                 ext_debug("move %d:%llu:%d in new leaf %llu\n",
718                                 le32_to_cpu(path[depth].p_ext->ee_block),
719                                 ext_pblock(path[depth].p_ext),
720                                 ext4_ext_get_actual_len(path[depth].p_ext),
721                                 newblock);
722                 /*memmove(ex++, path[depth].p_ext++,
723                                 sizeof(struct ext4_extent));
724                 neh->eh_entries++;*/
725                 path[depth].p_ext++;
726                 m++;
727         }
728         if (m) {
729                 memmove(ex, path[depth].p_ext-m, sizeof(struct ext4_extent)*m);
730                 neh->eh_entries = cpu_to_le16(le16_to_cpu(neh->eh_entries)+m);
731         }
732
733         set_buffer_uptodate(bh);
734         unlock_buffer(bh);
735
736         err = ext4_journal_dirty_metadata(handle, bh);
737         if (err)
738                 goto cleanup;
739         brelse(bh);
740         bh = NULL;
741
742         /* correct old leaf */
743         if (m) {
744                 err = ext4_ext_get_access(handle, inode, path + depth);
745                 if (err)
746                         goto cleanup;
747                 path[depth].p_hdr->eh_entries =
748                      cpu_to_le16(le16_to_cpu(path[depth].p_hdr->eh_entries)-m);
749                 err = ext4_ext_dirty(handle, inode, path + depth);
750                 if (err)
751                         goto cleanup;
752
753         }
754
755         /* create intermediate indexes */
756         k = depth - at - 1;
757         BUG_ON(k < 0);
758         if (k)
759                 ext_debug("create %d intermediate indices\n", k);
760         /* insert new index into current index block */
761         /* current depth stored in i var */
762         i = depth - 1;
763         while (k--) {
764                 oldblock = newblock;
765                 newblock = ablocks[--a];
766                 bh = sb_getblk(inode->i_sb, (ext4_fsblk_t)newblock);
767                 if (!bh) {
768                         err = -EIO;
769                         goto cleanup;
770                 }
771                 lock_buffer(bh);
772
773                 err = ext4_journal_get_create_access(handle, bh);
774                 if (err)
775                         goto cleanup;
776
777                 neh = ext_block_hdr(bh);
778                 neh->eh_entries = cpu_to_le16(1);
779                 neh->eh_magic = EXT4_EXT_MAGIC;
780                 neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode));
781                 neh->eh_depth = cpu_to_le16(depth - i);
782                 fidx = EXT_FIRST_INDEX(neh);
783                 fidx->ei_block = border;
784                 ext4_idx_store_pblock(fidx, oldblock);
785
786                 ext_debug("int.index at %d (block %llu): %lu -> %llu\n", i,
787                                 newblock, (unsigned long) le32_to_cpu(border),
788                                 oldblock);
789                 /* copy indexes */
790                 m = 0;
791                 path[i].p_idx++;
792
793                 ext_debug("cur 0x%p, last 0x%p\n", path[i].p_idx,
794                                 EXT_MAX_INDEX(path[i].p_hdr));
795                 BUG_ON(EXT_MAX_INDEX(path[i].p_hdr) !=
796                                 EXT_LAST_INDEX(path[i].p_hdr));
797                 while (path[i].p_idx <= EXT_MAX_INDEX(path[i].p_hdr)) {
798                         ext_debug("%d: move %d:%llu in new index %llu\n", i,
799                                         le32_to_cpu(path[i].p_idx->ei_block),
800                                         idx_pblock(path[i].p_idx),
801                                         newblock);
802                         /*memmove(++fidx, path[i].p_idx++,
803                                         sizeof(struct ext4_extent_idx));
804                         neh->eh_entries++;
805                         BUG_ON(neh->eh_entries > neh->eh_max);*/
806                         path[i].p_idx++;
807                         m++;
808                 }
809                 if (m) {
810                         memmove(++fidx, path[i].p_idx - m,
811                                 sizeof(struct ext4_extent_idx) * m);
812                         neh->eh_entries =
813                                 cpu_to_le16(le16_to_cpu(neh->eh_entries) + m);
814                 }
815                 set_buffer_uptodate(bh);
816                 unlock_buffer(bh);
817
818                 err = ext4_journal_dirty_metadata(handle, bh);
819                 if (err)
820                         goto cleanup;
821                 brelse(bh);
822                 bh = NULL;
823
824                 /* correct old index */
825                 if (m) {
826                         err = ext4_ext_get_access(handle, inode, path + i);
827                         if (err)
828                                 goto cleanup;
829                         path[i].p_hdr->eh_entries = cpu_to_le16(le16_to_cpu(path[i].p_hdr->eh_entries)-m);
830                         err = ext4_ext_dirty(handle, inode, path + i);
831                         if (err)
832                                 goto cleanup;
833                 }
834
835                 i--;
836         }
837
838         /* insert new index */
839         err = ext4_ext_insert_index(handle, inode, path + at,
840                                     le32_to_cpu(border), newblock);
841
842 cleanup:
843         if (bh) {
844                 if (buffer_locked(bh))
845                         unlock_buffer(bh);
846                 brelse(bh);
847         }
848
849         if (err) {
850                 /* free all allocated blocks in error case */
851                 for (i = 0; i < depth; i++) {
852                         if (!ablocks[i])
853                                 continue;
854                         ext4_free_blocks(handle, inode, ablocks[i], 1);
855                 }
856         }
857         kfree(ablocks);
858
859         return err;
860 }
861
862 /*
863  * ext4_ext_grow_indepth:
864  * implements tree growing procedure:
865  * - allocates new block
866  * - moves top-level data (index block or leaf) into the new block
867  * - initializes new top-level, creating index that points to the
868  *   just created block
869  */
870 static int ext4_ext_grow_indepth(handle_t *handle, struct inode *inode,
871                                         struct ext4_ext_path *path,
872                                         struct ext4_extent *newext)
873 {
874         struct ext4_ext_path *curp = path;
875         struct ext4_extent_header *neh;
876         struct ext4_extent_idx *fidx;
877         struct buffer_head *bh;
878         ext4_fsblk_t newblock;
879         int err = 0;
880
881         newblock = ext4_ext_new_block(handle, inode, path, newext, &err);
882         if (newblock == 0)
883                 return err;
884
885         bh = sb_getblk(inode->i_sb, newblock);
886         if (!bh) {
887                 err = -EIO;
888                 ext4_std_error(inode->i_sb, err);
889                 return err;
890         }
891         lock_buffer(bh);
892
893         err = ext4_journal_get_create_access(handle, bh);
894         if (err) {
895                 unlock_buffer(bh);
896                 goto out;
897         }
898
899         /* move top-level index/leaf into new block */
900         memmove(bh->b_data, curp->p_hdr, sizeof(EXT4_I(inode)->i_data));
901
902         /* set size of new block */
903         neh = ext_block_hdr(bh);
904         /* old root could have indexes or leaves
905          * so calculate e_max right way */
906         if (ext_depth(inode))
907           neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode));
908         else
909           neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode));
910         neh->eh_magic = EXT4_EXT_MAGIC;
911         set_buffer_uptodate(bh);
912         unlock_buffer(bh);
913
914         err = ext4_journal_dirty_metadata(handle, bh);
915         if (err)
916                 goto out;
917
918         /* create index in new top-level index: num,max,pointer */
919         err = ext4_ext_get_access(handle, inode, curp);
920         if (err)
921                 goto out;
922
923         curp->p_hdr->eh_magic = EXT4_EXT_MAGIC;
924         curp->p_hdr->eh_max = cpu_to_le16(ext4_ext_space_root_idx(inode));
925         curp->p_hdr->eh_entries = cpu_to_le16(1);
926         curp->p_idx = EXT_FIRST_INDEX(curp->p_hdr);
927
928         if (path[0].p_hdr->eh_depth)
929                 curp->p_idx->ei_block =
930                         EXT_FIRST_INDEX(path[0].p_hdr)->ei_block;
931         else
932                 curp->p_idx->ei_block =
933                         EXT_FIRST_EXTENT(path[0].p_hdr)->ee_block;
934         ext4_idx_store_pblock(curp->p_idx, newblock);
935
936         neh = ext_inode_hdr(inode);
937         fidx = EXT_FIRST_INDEX(neh);
938         ext_debug("new root: num %d(%d), lblock %d, ptr %llu\n",
939                   le16_to_cpu(neh->eh_entries), le16_to_cpu(neh->eh_max),
940                   le32_to_cpu(fidx->ei_block), idx_pblock(fidx));
941
942         neh->eh_depth = cpu_to_le16(path->p_depth + 1);
943         err = ext4_ext_dirty(handle, inode, curp);
944 out:
945         brelse(bh);
946
947         return err;
948 }
949
950 /*
951  * ext4_ext_create_new_leaf:
952  * finds empty index and adds new leaf.
953  * if no free index is found, then it requests in-depth growing.
954  */
955 static int ext4_ext_create_new_leaf(handle_t *handle, struct inode *inode,
956                                         struct ext4_ext_path *path,
957                                         struct ext4_extent *newext)
958 {
959         struct ext4_ext_path *curp;
960         int depth, i, err = 0;
961
962 repeat:
963         i = depth = ext_depth(inode);
964
965         /* walk up to the tree and look for free index entry */
966         curp = path + depth;
967         while (i > 0 && !EXT_HAS_FREE_INDEX(curp)) {
968                 i--;
969                 curp--;
970         }
971
972         /* we use already allocated block for index block,
973          * so subsequent data blocks should be contiguous */
974         if (EXT_HAS_FREE_INDEX(curp)) {
975                 /* if we found index with free entry, then use that
976                  * entry: create all needed subtree and add new leaf */
977                 err = ext4_ext_split(handle, inode, path, newext, i);
978
979                 /* refill path */
980                 ext4_ext_drop_refs(path);
981                 path = ext4_ext_find_extent(inode,
982                                             le32_to_cpu(newext->ee_block),
983                                             path);
984                 if (IS_ERR(path))
985                         err = PTR_ERR(path);
986         } else {
987                 /* tree is full, time to grow in depth */
988                 err = ext4_ext_grow_indepth(handle, inode, path, newext);
989                 if (err)
990                         goto out;
991
992                 /* refill path */
993                 ext4_ext_drop_refs(path);
994                 path = ext4_ext_find_extent(inode,
995                                             le32_to_cpu(newext->ee_block),
996                                             path);
997                 if (IS_ERR(path)) {
998                         err = PTR_ERR(path);
999                         goto out;
1000                 }
1001
1002                 /*
1003                  * only first (depth 0 -> 1) produces free space;
1004                  * in all other cases we have to split the grown tree
1005                  */
1006                 depth = ext_depth(inode);
1007                 if (path[depth].p_hdr->eh_entries == path[depth].p_hdr->eh_max) {
1008                         /* now we need to split */
1009                         goto repeat;
1010                 }
1011         }
1012
1013 out:
1014         return err;
1015 }
1016
1017 /*
1018  * ext4_ext_next_allocated_block:
1019  * returns allocated block in subsequent extent or EXT_MAX_BLOCK.
1020  * NOTE: it considers block number from index entry as
1021  * allocated block. Thus, index entries have to be consistent
1022  * with leaves.
1023  */
1024 static unsigned long
1025 ext4_ext_next_allocated_block(struct ext4_ext_path *path)
1026 {
1027         int depth;
1028
1029         BUG_ON(path == NULL);
1030         depth = path->p_depth;
1031
1032         if (depth == 0 && path->p_ext == NULL)
1033                 return EXT_MAX_BLOCK;
1034
1035         while (depth >= 0) {
1036                 if (depth == path->p_depth) {
1037                         /* leaf */
1038                         if (path[depth].p_ext !=
1039                                         EXT_LAST_EXTENT(path[depth].p_hdr))
1040                           return le32_to_cpu(path[depth].p_ext[1].ee_block);
1041                 } else {
1042                         /* index */
1043                         if (path[depth].p_idx !=
1044                                         EXT_LAST_INDEX(path[depth].p_hdr))
1045                           return le32_to_cpu(path[depth].p_idx[1].ei_block);
1046                 }
1047                 depth--;
1048         }
1049
1050         return EXT_MAX_BLOCK;
1051 }
1052
1053 /*
1054  * ext4_ext_next_leaf_block:
1055  * returns first allocated block from next leaf or EXT_MAX_BLOCK
1056  */
1057 static unsigned ext4_ext_next_leaf_block(struct inode *inode,
1058                                         struct ext4_ext_path *path)
1059 {
1060         int depth;
1061
1062         BUG_ON(path == NULL);
1063         depth = path->p_depth;
1064
1065         /* zero-tree has no leaf blocks at all */
1066         if (depth == 0)
1067                 return EXT_MAX_BLOCK;
1068
1069         /* go to index block */
1070         depth--;
1071
1072         while (depth >= 0) {
1073                 if (path[depth].p_idx !=
1074                                 EXT_LAST_INDEX(path[depth].p_hdr))
1075                   return le32_to_cpu(path[depth].p_idx[1].ei_block);
1076                 depth--;
1077         }
1078
1079         return EXT_MAX_BLOCK;
1080 }
1081
1082 /*
1083  * ext4_ext_correct_indexes:
1084  * if leaf gets modified and modified extent is first in the leaf,
1085  * then we have to correct all indexes above.
1086  * TODO: do we need to correct tree in all cases?
1087  */
1088 int ext4_ext_correct_indexes(handle_t *handle, struct inode *inode,
1089                                 struct ext4_ext_path *path)
1090 {
1091         struct ext4_extent_header *eh;
1092         int depth = ext_depth(inode);
1093         struct ext4_extent *ex;
1094         __le32 border;
1095         int k, err = 0;
1096
1097         eh = path[depth].p_hdr;
1098         ex = path[depth].p_ext;
1099         BUG_ON(ex == NULL);
1100         BUG_ON(eh == NULL);
1101
1102         if (depth == 0) {
1103                 /* there is no tree at all */
1104                 return 0;
1105         }
1106
1107         if (ex != EXT_FIRST_EXTENT(eh)) {
1108                 /* we correct tree if first leaf got modified only */
1109                 return 0;
1110         }
1111
1112         /*
1113          * TODO: we need correction if border is smaller than current one
1114          */
1115         k = depth - 1;
1116         border = path[depth].p_ext->ee_block;
1117         err = ext4_ext_get_access(handle, inode, path + k);
1118         if (err)
1119                 return err;
1120         path[k].p_idx->ei_block = border;
1121         err = ext4_ext_dirty(handle, inode, path + k);
1122         if (err)
1123                 return err;
1124
1125         while (k--) {
1126                 /* change all left-side indexes */
1127                 if (path[k+1].p_idx != EXT_FIRST_INDEX(path[k+1].p_hdr))
1128                         break;
1129                 err = ext4_ext_get_access(handle, inode, path + k);
1130                 if (err)
1131                         break;
1132                 path[k].p_idx->ei_block = border;
1133                 err = ext4_ext_dirty(handle, inode, path + k);
1134                 if (err)
1135                         break;
1136         }
1137
1138         return err;
1139 }
1140
1141 static int
1142 ext4_can_extents_be_merged(struct inode *inode, struct ext4_extent *ex1,
1143                                 struct ext4_extent *ex2)
1144 {
1145         unsigned short ext1_ee_len, ext2_ee_len, max_len;
1146
1147         /*
1148          * Make sure that either both extents are uninitialized, or
1149          * both are _not_.
1150          */
1151         if (ext4_ext_is_uninitialized(ex1) ^ ext4_ext_is_uninitialized(ex2))
1152                 return 0;
1153
1154         if (ext4_ext_is_uninitialized(ex1))
1155                 max_len = EXT_UNINIT_MAX_LEN;
1156         else
1157                 max_len = EXT_INIT_MAX_LEN;
1158
1159         ext1_ee_len = ext4_ext_get_actual_len(ex1);
1160         ext2_ee_len = ext4_ext_get_actual_len(ex2);
1161
1162         if (le32_to_cpu(ex1->ee_block) + ext1_ee_len !=
1163                         le32_to_cpu(ex2->ee_block))
1164                 return 0;
1165
1166         /*
1167          * To allow future support for preallocated extents to be added
1168          * as an RO_COMPAT feature, refuse to merge to extents if
1169          * this can result in the top bit of ee_len being set.
1170          */
1171         if (ext1_ee_len + ext2_ee_len > max_len)
1172                 return 0;
1173 #ifdef AGGRESSIVE_TEST
1174         if (le16_to_cpu(ex1->ee_len) >= 4)
1175                 return 0;
1176 #endif
1177
1178         if (ext_pblock(ex1) + ext1_ee_len == ext_pblock(ex2))
1179                 return 1;
1180         return 0;
1181 }
1182
1183 /*
1184  * This function tries to merge the "ex" extent to the next extent in the tree.
1185  * It always tries to merge towards right. If you want to merge towards
1186  * left, pass "ex - 1" as argument instead of "ex".
1187  * Returns 0 if the extents (ex and ex+1) were _not_ merged and returns
1188  * 1 if they got merged.
1189  */
1190 int ext4_ext_try_to_merge(struct inode *inode,
1191                           struct ext4_ext_path *path,
1192                           struct ext4_extent *ex)
1193 {
1194         struct ext4_extent_header *eh;
1195         unsigned int depth, len;
1196         int merge_done = 0;
1197         int uninitialized = 0;
1198
1199         depth = ext_depth(inode);
1200         BUG_ON(path[depth].p_hdr == NULL);
1201         eh = path[depth].p_hdr;
1202
1203         while (ex < EXT_LAST_EXTENT(eh)) {
1204                 if (!ext4_can_extents_be_merged(inode, ex, ex + 1))
1205                         break;
1206                 /* merge with next extent! */
1207                 if (ext4_ext_is_uninitialized(ex))
1208                         uninitialized = 1;
1209                 ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
1210                                 + ext4_ext_get_actual_len(ex + 1));
1211                 if (uninitialized)
1212                         ext4_ext_mark_uninitialized(ex);
1213
1214                 if (ex + 1 < EXT_LAST_EXTENT(eh)) {
1215                         len = (EXT_LAST_EXTENT(eh) - ex - 1)
1216                                 * sizeof(struct ext4_extent);
1217                         memmove(ex + 1, ex + 2, len);
1218                 }
1219                 eh->eh_entries = cpu_to_le16(le16_to_cpu(eh->eh_entries) - 1);
1220                 merge_done = 1;
1221                 WARN_ON(eh->eh_entries == 0);
1222                 if (!eh->eh_entries)
1223                         ext4_error(inode->i_sb, "ext4_ext_try_to_merge",
1224                            "inode#%lu, eh->eh_entries = 0!", inode->i_ino);
1225         }
1226
1227         return merge_done;
1228 }
1229
1230 /*
1231  * check if a portion of the "newext" extent overlaps with an
1232  * existing extent.
1233  *
1234  * If there is an overlap discovered, it updates the length of the newext
1235  * such that there will be no overlap, and then returns 1.
1236  * If there is no overlap found, it returns 0.
1237  */
1238 unsigned int ext4_ext_check_overlap(struct inode *inode,
1239                                     struct ext4_extent *newext,
1240                                     struct ext4_ext_path *path)
1241 {
1242         unsigned long b1, b2;
1243         unsigned int depth, len1;
1244         unsigned int ret = 0;
1245
1246         b1 = le32_to_cpu(newext->ee_block);
1247         len1 = ext4_ext_get_actual_len(newext);
1248         depth = ext_depth(inode);
1249         if (!path[depth].p_ext)
1250                 goto out;
1251         b2 = le32_to_cpu(path[depth].p_ext->ee_block);
1252
1253         /*
1254          * get the next allocated block if the extent in the path
1255          * is before the requested block(s) 
1256          */
1257         if (b2 < b1) {
1258                 b2 = ext4_ext_next_allocated_block(path);
1259                 if (b2 == EXT_MAX_BLOCK)
1260                         goto out;
1261         }
1262
1263         /* check for wrap through zero */
1264         if (b1 + len1 < b1) {
1265                 len1 = EXT_MAX_BLOCK - b1;
1266                 newext->ee_len = cpu_to_le16(len1);
1267                 ret = 1;
1268         }
1269
1270         /* check for overlap */
1271         if (b1 + len1 > b2) {
1272                 newext->ee_len = cpu_to_le16(b2 - b1);
1273                 ret = 1;
1274         }
1275 out:
1276         return ret;
1277 }
1278
1279 /*
1280  * ext4_ext_insert_extent:
1281  * tries to merge requsted extent into the existing extent or
1282  * inserts requested extent as new one into the tree,
1283  * creating new leaf in the no-space case.
1284  */
1285 int ext4_ext_insert_extent(handle_t *handle, struct inode *inode,
1286                                 struct ext4_ext_path *path,
1287                                 struct ext4_extent *newext)
1288 {
1289         struct ext4_extent_header * eh;
1290         struct ext4_extent *ex, *fex;
1291         struct ext4_extent *nearex; /* nearest extent */
1292         struct ext4_ext_path *npath = NULL;
1293         int depth, len, err, next;
1294         unsigned uninitialized = 0;
1295
1296         BUG_ON(ext4_ext_get_actual_len(newext) == 0);
1297         depth = ext_depth(inode);
1298         ex = path[depth].p_ext;
1299         BUG_ON(path[depth].p_hdr == NULL);
1300
1301         /* try to insert block into found extent and return */
1302         if (ex && ext4_can_extents_be_merged(inode, ex, newext)) {
1303                 ext_debug("append %d block to %d:%d (from %llu)\n",
1304                                 ext4_ext_get_actual_len(newext),
1305                                 le32_to_cpu(ex->ee_block),
1306                                 ext4_ext_get_actual_len(ex), ext_pblock(ex));
1307                 err = ext4_ext_get_access(handle, inode, path + depth);
1308                 if (err)
1309                         return err;
1310
1311                 /*
1312                  * ext4_can_extents_be_merged should have checked that either
1313                  * both extents are uninitialized, or both aren't. Thus we
1314                  * need to check only one of them here.
1315                  */
1316                 if (ext4_ext_is_uninitialized(ex))
1317                         uninitialized = 1;
1318                 ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
1319                                         + ext4_ext_get_actual_len(newext));
1320                 if (uninitialized)
1321                         ext4_ext_mark_uninitialized(ex);
1322                 eh = path[depth].p_hdr;
1323                 nearex = ex;
1324                 goto merge;
1325         }
1326
1327 repeat:
1328         depth = ext_depth(inode);
1329         eh = path[depth].p_hdr;
1330         if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))
1331                 goto has_space;
1332
1333         /* probably next leaf has space for us? */
1334         fex = EXT_LAST_EXTENT(eh);
1335         next = ext4_ext_next_leaf_block(inode, path);
1336         if (le32_to_cpu(newext->ee_block) > le32_to_cpu(fex->ee_block)
1337             && next != EXT_MAX_BLOCK) {
1338                 ext_debug("next leaf block - %d\n", next);
1339                 BUG_ON(npath != NULL);
1340                 npath = ext4_ext_find_extent(inode, next, NULL);
1341                 if (IS_ERR(npath))
1342                         return PTR_ERR(npath);
1343                 BUG_ON(npath->p_depth != path->p_depth);
1344                 eh = npath[depth].p_hdr;
1345                 if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max)) {
1346                         ext_debug("next leaf isnt full(%d)\n",
1347                                   le16_to_cpu(eh->eh_entries));
1348                         path = npath;
1349                         goto repeat;
1350                 }
1351                 ext_debug("next leaf has no free space(%d,%d)\n",
1352                           le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
1353         }
1354
1355         /*
1356          * There is no free space in the found leaf.
1357          * We're gonna add a new leaf in the tree.
1358          */
1359         err = ext4_ext_create_new_leaf(handle, inode, path, newext);
1360         if (err)
1361                 goto cleanup;
1362         depth = ext_depth(inode);
1363         eh = path[depth].p_hdr;
1364
1365 has_space:
1366         nearex = path[depth].p_ext;
1367
1368         err = ext4_ext_get_access(handle, inode, path + depth);
1369         if (err)
1370                 goto cleanup;
1371
1372         if (!nearex) {
1373                 /* there is no extent in this leaf, create first one */
1374                 ext_debug("first extent in the leaf: %d:%llu:%d\n",
1375                                 le32_to_cpu(newext->ee_block),
1376                                 ext_pblock(newext),
1377                                 ext4_ext_get_actual_len(newext));
1378                 path[depth].p_ext = EXT_FIRST_EXTENT(eh);
1379         } else if (le32_to_cpu(newext->ee_block)
1380                            > le32_to_cpu(nearex->ee_block)) {
1381 /*              BUG_ON(newext->ee_block == nearex->ee_block); */
1382                 if (nearex != EXT_LAST_EXTENT(eh)) {
1383                         len = EXT_MAX_EXTENT(eh) - nearex;
1384                         len = (len - 1) * sizeof(struct ext4_extent);
1385                         len = len < 0 ? 0 : len;
1386                         ext_debug("insert %d:%llu:%d after: nearest 0x%p, "
1387                                         "move %d from 0x%p to 0x%p\n",
1388                                         le32_to_cpu(newext->ee_block),
1389                                         ext_pblock(newext),
1390                                         ext4_ext_get_actual_len(newext),
1391                                         nearex, len, nearex + 1, nearex + 2);
1392                         memmove(nearex + 2, nearex + 1, len);
1393                 }
1394                 path[depth].p_ext = nearex + 1;
1395         } else {
1396                 BUG_ON(newext->ee_block == nearex->ee_block);
1397                 len = (EXT_MAX_EXTENT(eh) - nearex) * sizeof(struct ext4_extent);
1398                 len = len < 0 ? 0 : len;
1399                 ext_debug("insert %d:%llu:%d before: nearest 0x%p, "
1400                                 "move %d from 0x%p to 0x%p\n",
1401                                 le32_to_cpu(newext->ee_block),
1402                                 ext_pblock(newext),
1403                                 ext4_ext_get_actual_len(newext),
1404                                 nearex, len, nearex + 1, nearex + 2);
1405                 memmove(nearex + 1, nearex, len);
1406                 path[depth].p_ext = nearex;
1407         }
1408
1409         eh->eh_entries = cpu_to_le16(le16_to_cpu(eh->eh_entries)+1);
1410         nearex = path[depth].p_ext;
1411         nearex->ee_block = newext->ee_block;
1412         ext4_ext_store_pblock(nearex, ext_pblock(newext));
1413         nearex->ee_len = newext->ee_len;
1414
1415 merge:
1416         /* try to merge extents to the right */
1417         ext4_ext_try_to_merge(inode, path, nearex);
1418
1419         /* try to merge extents to the left */
1420
1421         /* time to correct all indexes above */
1422         err = ext4_ext_correct_indexes(handle, inode, path);
1423         if (err)
1424                 goto cleanup;
1425
1426         err = ext4_ext_dirty(handle, inode, path + depth);
1427
1428 cleanup:
1429         if (npath) {
1430                 ext4_ext_drop_refs(npath);
1431                 kfree(npath);
1432         }
1433         ext4_ext_tree_changed(inode);
1434         ext4_ext_invalidate_cache(inode);
1435         return err;
1436 }
1437
1438 int ext4_ext_walk_space(struct inode *inode, unsigned long block,
1439                         unsigned long num, ext_prepare_callback func,
1440                         void *cbdata)
1441 {
1442         struct ext4_ext_path *path = NULL;
1443         struct ext4_ext_cache cbex;
1444         struct ext4_extent *ex;
1445         unsigned long next, start = 0, end = 0;
1446         unsigned long last = block + num;
1447         int depth, exists, err = 0;
1448
1449         BUG_ON(func == NULL);
1450         BUG_ON(inode == NULL);
1451
1452         while (block < last && block != EXT_MAX_BLOCK) {
1453                 num = last - block;
1454                 /* find extent for this block */
1455                 path = ext4_ext_find_extent(inode, block, path);
1456                 if (IS_ERR(path)) {
1457                         err = PTR_ERR(path);
1458                         path = NULL;
1459                         break;
1460                 }
1461
1462                 depth = ext_depth(inode);
1463                 BUG_ON(path[depth].p_hdr == NULL);
1464                 ex = path[depth].p_ext;
1465                 next = ext4_ext_next_allocated_block(path);
1466
1467                 exists = 0;
1468                 if (!ex) {
1469                         /* there is no extent yet, so try to allocate
1470                          * all requested space */
1471                         start = block;
1472                         end = block + num;
1473                 } else if (le32_to_cpu(ex->ee_block) > block) {
1474                         /* need to allocate space before found extent */
1475                         start = block;
1476                         end = le32_to_cpu(ex->ee_block);
1477                         if (block + num < end)
1478                                 end = block + num;
1479                 } else if (block >= le32_to_cpu(ex->ee_block)
1480                                         + ext4_ext_get_actual_len(ex)) {
1481                         /* need to allocate space after found extent */
1482                         start = block;
1483                         end = block + num;
1484                         if (end >= next)
1485                                 end = next;
1486                 } else if (block >= le32_to_cpu(ex->ee_block)) {
1487                         /*
1488                          * some part of requested space is covered
1489                          * by found extent
1490                          */
1491                         start = block;
1492                         end = le32_to_cpu(ex->ee_block)
1493                                 + ext4_ext_get_actual_len(ex);
1494                         if (block + num < end)
1495                                 end = block + num;
1496                         exists = 1;
1497                 } else {
1498                         BUG();
1499                 }
1500                 BUG_ON(end <= start);
1501
1502                 if (!exists) {
1503                         cbex.ec_block = start;
1504                         cbex.ec_len = end - start;
1505                         cbex.ec_start = 0;
1506                         cbex.ec_type = EXT4_EXT_CACHE_GAP;
1507                 } else {
1508                         cbex.ec_block = le32_to_cpu(ex->ee_block);
1509                         cbex.ec_len = ext4_ext_get_actual_len(ex);
1510                         cbex.ec_start = ext_pblock(ex);
1511                         cbex.ec_type = EXT4_EXT_CACHE_EXTENT;
1512                 }
1513
1514                 BUG_ON(cbex.ec_len == 0);
1515                 err = func(inode, path, &cbex, cbdata);
1516                 ext4_ext_drop_refs(path);
1517
1518                 if (err < 0)
1519                         break;
1520                 if (err == EXT_REPEAT)
1521                         continue;
1522                 else if (err == EXT_BREAK) {
1523                         err = 0;
1524                         break;
1525                 }
1526
1527                 if (ext_depth(inode) != depth) {
1528                         /* depth was changed. we have to realloc path */
1529                         kfree(path);
1530                         path = NULL;
1531                 }
1532
1533                 block = cbex.ec_block + cbex.ec_len;
1534         }
1535
1536         if (path) {
1537                 ext4_ext_drop_refs(path);
1538                 kfree(path);
1539         }
1540
1541         return err;
1542 }
1543
1544 static void
1545 ext4_ext_put_in_cache(struct inode *inode, __u32 block,
1546                         __u32 len, ext4_fsblk_t start, int type)
1547 {
1548         struct ext4_ext_cache *cex;
1549         BUG_ON(len == 0);
1550         cex = &EXT4_I(inode)->i_cached_extent;
1551         cex->ec_type = type;
1552         cex->ec_block = block;
1553         cex->ec_len = len;
1554         cex->ec_start = start;
1555 }
1556
1557 /*
1558  * ext4_ext_put_gap_in_cache:
1559  * calculate boundaries of the gap that the requested block fits into
1560  * and cache this gap
1561  */
1562 static void
1563 ext4_ext_put_gap_in_cache(struct inode *inode, struct ext4_ext_path *path,
1564                                 unsigned long block)
1565 {
1566         int depth = ext_depth(inode);
1567         unsigned long lblock, len;
1568         struct ext4_extent *ex;
1569
1570         ex = path[depth].p_ext;
1571         if (ex == NULL) {
1572                 /* there is no extent yet, so gap is [0;-] */
1573                 lblock = 0;
1574                 len = EXT_MAX_BLOCK;
1575                 ext_debug("cache gap(whole file):");
1576         } else if (block < le32_to_cpu(ex->ee_block)) {
1577                 lblock = block;
1578                 len = le32_to_cpu(ex->ee_block) - block;
1579                 ext_debug("cache gap(before): %lu [%lu:%lu]",
1580                                 (unsigned long) block,
1581                                 (unsigned long) le32_to_cpu(ex->ee_block),
1582                                 (unsigned long) ext4_ext_get_actual_len(ex));
1583         } else if (block >= le32_to_cpu(ex->ee_block)
1584                         + ext4_ext_get_actual_len(ex)) {
1585                 lblock = le32_to_cpu(ex->ee_block)
1586                         + ext4_ext_get_actual_len(ex);
1587                 len = ext4_ext_next_allocated_block(path);
1588                 ext_debug("cache gap(after): [%lu:%lu] %lu",
1589                                 (unsigned long) le32_to_cpu(ex->ee_block),
1590                                 (unsigned long) ext4_ext_get_actual_len(ex),
1591                                 (unsigned long) block);
1592                 BUG_ON(len == lblock);
1593                 len = len - lblock;
1594         } else {
1595                 lblock = len = 0;
1596                 BUG();
1597         }
1598
1599         ext_debug(" -> %lu:%lu\n", (unsigned long) lblock, len);
1600         ext4_ext_put_in_cache(inode, lblock, len, 0, EXT4_EXT_CACHE_GAP);
1601 }
1602
1603 static int
1604 ext4_ext_in_cache(struct inode *inode, unsigned long block,
1605                         struct ext4_extent *ex)
1606 {
1607         struct ext4_ext_cache *cex;
1608
1609         cex = &EXT4_I(inode)->i_cached_extent;
1610
1611         /* has cache valid data? */
1612         if (cex->ec_type == EXT4_EXT_CACHE_NO)
1613                 return EXT4_EXT_CACHE_NO;
1614
1615         BUG_ON(cex->ec_type != EXT4_EXT_CACHE_GAP &&
1616                         cex->ec_type != EXT4_EXT_CACHE_EXTENT);
1617         if (block >= cex->ec_block && block < cex->ec_block + cex->ec_len) {
1618                 ex->ee_block = cpu_to_le32(cex->ec_block);
1619                 ext4_ext_store_pblock(ex, cex->ec_start);
1620                 ex->ee_len = cpu_to_le16(cex->ec_len);
1621                 ext_debug("%lu cached by %lu:%lu:%llu\n",
1622                                 (unsigned long) block,
1623                                 (unsigned long) cex->ec_block,
1624                                 (unsigned long) cex->ec_len,
1625                                 cex->ec_start);
1626                 return cex->ec_type;
1627         }
1628
1629         /* not in cache */
1630         return EXT4_EXT_CACHE_NO;
1631 }
1632
1633 /*
1634  * ext4_ext_rm_idx:
1635  * removes index from the index block.
1636  * It's used in truncate case only, thus all requests are for
1637  * last index in the block only.
1638  */
1639 int ext4_ext_rm_idx(handle_t *handle, struct inode *inode,
1640                         struct ext4_ext_path *path)
1641 {
1642         struct buffer_head *bh;
1643         int err;
1644         ext4_fsblk_t leaf;
1645
1646         /* free index block */
1647         path--;
1648         leaf = idx_pblock(path->p_idx);
1649         BUG_ON(path->p_hdr->eh_entries == 0);
1650         err = ext4_ext_get_access(handle, inode, path);
1651         if (err)
1652                 return err;
1653         path->p_hdr->eh_entries = cpu_to_le16(le16_to_cpu(path->p_hdr->eh_entries)-1);
1654         err = ext4_ext_dirty(handle, inode, path);
1655         if (err)
1656                 return err;
1657         ext_debug("index is empty, remove it, free block %llu\n", leaf);
1658         bh = sb_find_get_block(inode->i_sb, leaf);
1659         ext4_forget(handle, 1, inode, bh, leaf);
1660         ext4_free_blocks(handle, inode, leaf, 1);
1661         return err;
1662 }
1663
1664 /*
1665  * ext4_ext_calc_credits_for_insert:
1666  * This routine returns max. credits that the extent tree can consume.
1667  * It should be OK for low-performance paths like ->writepage()
1668  * To allow many writing processes to fit into a single transaction,
1669  * the caller should calculate credits under truncate_mutex and
1670  * pass the actual path.
1671  */
1672 int ext4_ext_calc_credits_for_insert(struct inode *inode,
1673                                                 struct ext4_ext_path *path)
1674 {
1675         int depth, needed;
1676
1677         if (path) {
1678                 /* probably there is space in leaf? */
1679                 depth = ext_depth(inode);
1680                 if (le16_to_cpu(path[depth].p_hdr->eh_entries)
1681                                 < le16_to_cpu(path[depth].p_hdr->eh_max))
1682                         return 1;
1683         }
1684
1685         /*
1686          * given 32-bit logical block (4294967296 blocks), max. tree
1687          * can be 4 levels in depth -- 4 * 340^4 == 53453440000.
1688          * Let's also add one more level for imbalance.
1689          */
1690         depth = 5;
1691
1692         /* allocation of new data block(s) */
1693         needed = 2;
1694
1695         /*
1696          * tree can be full, so it would need to grow in depth:
1697          * we need one credit to modify old root, credits for
1698          * new root will be added in split accounting
1699          */
1700         needed += 1;
1701
1702         /*
1703          * Index split can happen, we would need:
1704          *    allocate intermediate indexes (bitmap + group)
1705          *  + change two blocks at each level, but root (already included)
1706          */
1707         needed += (depth * 2) + (depth * 2);
1708
1709         /* any allocation modifies superblock */
1710         needed += 1;
1711
1712         return needed;
1713 }
1714
1715 static int ext4_remove_blocks(handle_t *handle, struct inode *inode,
1716                                 struct ext4_extent *ex,
1717                                 unsigned long from, unsigned long to)
1718 {
1719         struct buffer_head *bh;
1720         unsigned short ee_len =  ext4_ext_get_actual_len(ex);
1721         int i;
1722
1723 #ifdef EXTENTS_STATS
1724         {
1725                 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
1726                 spin_lock(&sbi->s_ext_stats_lock);
1727                 sbi->s_ext_blocks += ee_len;
1728                 sbi->s_ext_extents++;
1729                 if (ee_len < sbi->s_ext_min)
1730                         sbi->s_ext_min = ee_len;
1731                 if (ee_len > sbi->s_ext_max)
1732                         sbi->s_ext_max = ee_len;
1733                 if (ext_depth(inode) > sbi->s_depth_max)
1734                         sbi->s_depth_max = ext_depth(inode);
1735                 spin_unlock(&sbi->s_ext_stats_lock);
1736         }
1737 #endif
1738         if (from >= le32_to_cpu(ex->ee_block)
1739             && to == le32_to_cpu(ex->ee_block) + ee_len - 1) {
1740                 /* tail removal */
1741                 unsigned long num;
1742                 ext4_fsblk_t start;
1743                 num = le32_to_cpu(ex->ee_block) + ee_len - from;
1744                 start = ext_pblock(ex) + ee_len - num;
1745                 ext_debug("free last %lu blocks starting %llu\n", num, start);
1746                 for (i = 0; i < num; i++) {
1747                         bh = sb_find_get_block(inode->i_sb, start + i);
1748                         ext4_forget(handle, 0, inode, bh, start + i);
1749                 }
1750                 ext4_free_blocks(handle, inode, start, num);
1751         } else if (from == le32_to_cpu(ex->ee_block)
1752                    && to <= le32_to_cpu(ex->ee_block) + ee_len - 1) {
1753                 printk("strange request: removal %lu-%lu from %u:%u\n",
1754                         from, to, le32_to_cpu(ex->ee_block), ee_len);
1755         } else {
1756                 printk("strange request: removal(2) %lu-%lu from %u:%u\n",
1757                         from, to, le32_to_cpu(ex->ee_block), ee_len);
1758         }
1759         return 0;
1760 }
1761
1762 static int
1763 ext4_ext_rm_leaf(handle_t *handle, struct inode *inode,
1764                 struct ext4_ext_path *path, unsigned long start)
1765 {
1766         int err = 0, correct_index = 0;
1767         int depth = ext_depth(inode), credits;
1768         struct ext4_extent_header *eh;
1769         unsigned a, b, block, num;
1770         unsigned long ex_ee_block;
1771         unsigned short ex_ee_len;
1772         unsigned uninitialized = 0;
1773         struct ext4_extent *ex;
1774
1775         /* the header must be checked already in ext4_ext_remove_space() */
1776         ext_debug("truncate since %lu in leaf\n", start);
1777         if (!path[depth].p_hdr)
1778                 path[depth].p_hdr = ext_block_hdr(path[depth].p_bh);
1779         eh = path[depth].p_hdr;
1780         BUG_ON(eh == NULL);
1781
1782         /* find where to start removing */
1783         ex = EXT_LAST_EXTENT(eh);
1784
1785         ex_ee_block = le32_to_cpu(ex->ee_block);
1786         if (ext4_ext_is_uninitialized(ex))
1787                 uninitialized = 1;
1788         ex_ee_len = ext4_ext_get_actual_len(ex);
1789
1790         while (ex >= EXT_FIRST_EXTENT(eh) &&
1791                         ex_ee_block + ex_ee_len > start) {
1792                 ext_debug("remove ext %lu:%u\n", ex_ee_block, ex_ee_len);
1793                 path[depth].p_ext = ex;
1794
1795                 a = ex_ee_block > start ? ex_ee_block : start;
1796                 b = ex_ee_block + ex_ee_len - 1 < EXT_MAX_BLOCK ?
1797                         ex_ee_block + ex_ee_len - 1 : EXT_MAX_BLOCK;
1798
1799                 ext_debug("  border %u:%u\n", a, b);
1800
1801                 if (a != ex_ee_block && b != ex_ee_block + ex_ee_len - 1) {
1802                         block = 0;
1803                         num = 0;
1804                         BUG();
1805                 } else if (a != ex_ee_block) {
1806                         /* remove tail of the extent */
1807                         block = ex_ee_block;
1808                         num = a - block;
1809                 } else if (b != ex_ee_block + ex_ee_len - 1) {
1810                         /* remove head of the extent */
1811                         block = a;
1812                         num = b - a;
1813                         /* there is no "make a hole" API yet */
1814                         BUG();
1815                 } else {
1816                         /* remove whole extent: excellent! */
1817                         block = ex_ee_block;
1818                         num = 0;
1819                         BUG_ON(a != ex_ee_block);
1820                         BUG_ON(b != ex_ee_block + ex_ee_len - 1);
1821                 }
1822
1823                 /* at present, extent can't cross block group: */
1824                 /* leaf + bitmap + group desc + sb + inode */
1825                 credits = 5;
1826                 if (ex == EXT_FIRST_EXTENT(eh)) {
1827                         correct_index = 1;
1828                         credits += (ext_depth(inode)) + 1;
1829                 }
1830 #ifdef CONFIG_QUOTA
1831                 credits += 2 * EXT4_QUOTA_TRANS_BLOCKS(inode->i_sb);
1832 #endif
1833
1834                 handle = ext4_ext_journal_restart(handle, credits);
1835                 if (IS_ERR(handle)) {
1836                         err = PTR_ERR(handle);
1837                         goto out;
1838                 }
1839
1840                 err = ext4_ext_get_access(handle, inode, path + depth);
1841                 if (err)
1842                         goto out;
1843
1844                 err = ext4_remove_blocks(handle, inode, ex, a, b);
1845                 if (err)
1846                         goto out;
1847
1848                 if (num == 0) {
1849                         /* this extent is removed; mark slot entirely unused */
1850                         ext4_ext_store_pblock(ex, 0);
1851                         eh->eh_entries = cpu_to_le16(le16_to_cpu(eh->eh_entries)-1);
1852                 }
1853
1854                 ex->ee_block = cpu_to_le32(block);
1855                 ex->ee_len = cpu_to_le16(num);
1856                 /*
1857                  * Do not mark uninitialized if all the blocks in the
1858                  * extent have been removed.
1859                  */
1860                 if (uninitialized && num)
1861                         ext4_ext_mark_uninitialized(ex);
1862
1863                 err = ext4_ext_dirty(handle, inode, path + depth);
1864                 if (err)
1865                         goto out;
1866
1867                 ext_debug("new extent: %u:%u:%llu\n", block, num,
1868                                 ext_pblock(ex));
1869                 ex--;
1870                 ex_ee_block = le32_to_cpu(ex->ee_block);
1871                 ex_ee_len = ext4_ext_get_actual_len(ex);
1872         }
1873
1874         if (correct_index && eh->eh_entries)
1875                 err = ext4_ext_correct_indexes(handle, inode, path);
1876
1877         /* if this leaf is free, then we should
1878          * remove it from index block above */
1879         if (err == 0 && eh->eh_entries == 0 && path[depth].p_bh != NULL)
1880                 err = ext4_ext_rm_idx(handle, inode, path + depth);
1881
1882 out:
1883         return err;
1884 }
1885
1886 /*
1887  * ext4_ext_more_to_rm:
1888  * returns 1 if current index has to be freed (even partial)
1889  */
1890 static int
1891 ext4_ext_more_to_rm(struct ext4_ext_path *path)
1892 {
1893         BUG_ON(path->p_idx == NULL);
1894
1895         if (path->p_idx < EXT_FIRST_INDEX(path->p_hdr))
1896                 return 0;
1897
1898         /*
1899          * if truncate on deeper level happened, it wasn't partial,
1900          * so we have to consider current index for truncation
1901          */
1902         if (le16_to_cpu(path->p_hdr->eh_entries) == path->p_block)
1903                 return 0;
1904         return 1;
1905 }
1906
1907 int ext4_ext_remove_space(struct inode *inode, unsigned long start)
1908 {
1909         struct super_block *sb = inode->i_sb;
1910         int depth = ext_depth(inode);
1911         struct ext4_ext_path *path;
1912         handle_t *handle;
1913         int i = 0, err = 0;
1914
1915         ext_debug("truncate since %lu\n", start);
1916
1917         /* probably first extent we're gonna free will be last in block */
1918         handle = ext4_journal_start(inode, depth + 1);
1919         if (IS_ERR(handle))
1920                 return PTR_ERR(handle);
1921
1922         ext4_ext_invalidate_cache(inode);
1923
1924         /*
1925          * We start scanning from right side, freeing all the blocks
1926          * after i_size and walking into the tree depth-wise.
1927          */
1928         path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 1), GFP_KERNEL);
1929         if (path == NULL) {
1930                 ext4_journal_stop(handle);
1931                 return -ENOMEM;
1932         }
1933         path[0].p_hdr = ext_inode_hdr(inode);
1934         if (ext4_ext_check_header(inode, path[0].p_hdr, depth)) {
1935                 err = -EIO;
1936                 goto out;
1937         }
1938         path[0].p_depth = depth;
1939
1940         while (i >= 0 && err == 0) {
1941                 if (i == depth) {
1942                         /* this is leaf block */
1943                         err = ext4_ext_rm_leaf(handle, inode, path, start);
1944                         /* root level has p_bh == NULL, brelse() eats this */
1945                         brelse(path[i].p_bh);
1946                         path[i].p_bh = NULL;
1947                         i--;
1948                         continue;
1949                 }
1950
1951                 /* this is index block */
1952                 if (!path[i].p_hdr) {
1953                         ext_debug("initialize header\n");
1954                         path[i].p_hdr = ext_block_hdr(path[i].p_bh);
1955                 }
1956
1957                 if (!path[i].p_idx) {
1958                         /* this level hasn't been touched yet */
1959                         path[i].p_idx = EXT_LAST_INDEX(path[i].p_hdr);
1960                         path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries)+1;
1961                         ext_debug("init index ptr: hdr 0x%p, num %d\n",
1962                                   path[i].p_hdr,
1963                                   le16_to_cpu(path[i].p_hdr->eh_entries));
1964                 } else {
1965                         /* we were already here, see at next index */
1966                         path[i].p_idx--;
1967                 }
1968
1969                 ext_debug("level %d - index, first 0x%p, cur 0x%p\n",
1970                                 i, EXT_FIRST_INDEX(path[i].p_hdr),
1971                                 path[i].p_idx);
1972                 if (ext4_ext_more_to_rm(path + i)) {
1973                         struct buffer_head *bh;
1974                         /* go to the next level */
1975                         ext_debug("move to level %d (block %llu)\n",
1976                                   i + 1, idx_pblock(path[i].p_idx));
1977                         memset(path + i + 1, 0, sizeof(*path));
1978                         bh = sb_bread(sb, idx_pblock(path[i].p_idx));
1979                         if (!bh) {
1980                                 /* should we reset i_size? */
1981                                 err = -EIO;
1982                                 break;
1983                         }
1984                         if (WARN_ON(i + 1 > depth)) {
1985                                 err = -EIO;
1986                                 break;
1987                         }
1988                         if (ext4_ext_check_header(inode, ext_block_hdr(bh),
1989                                                         depth - i - 1)) {
1990                                 err = -EIO;
1991                                 break;
1992                         }
1993                         path[i + 1].p_bh = bh;
1994
1995                         /* save actual number of indexes since this
1996                          * number is changed at the next iteration */
1997                         path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries);
1998                         i++;
1999                 } else {
2000                         /* we finished processing this index, go up */
2001                         if (path[i].p_hdr->eh_entries == 0 && i > 0) {
2002                                 /* index is empty, remove it;
2003                                  * handle must be already prepared by the
2004                                  * truncatei_leaf() */
2005                                 err = ext4_ext_rm_idx(handle, inode, path + i);
2006                         }
2007                         /* root level has p_bh == NULL, brelse() eats this */
2008                         brelse(path[i].p_bh);
2009                         path[i].p_bh = NULL;
2010                         i--;
2011                         ext_debug("return to level %d\n", i);
2012                 }
2013         }
2014
2015         /* TODO: flexible tree reduction should be here */
2016         if (path->p_hdr->eh_entries == 0) {
2017                 /*
2018                  * truncate to zero freed all the tree,
2019                  * so we need to correct eh_depth
2020                  */
2021                 err = ext4_ext_get_access(handle, inode, path);
2022                 if (err == 0) {
2023                         ext_inode_hdr(inode)->eh_depth = 0;
2024                         ext_inode_hdr(inode)->eh_max =
2025                                 cpu_to_le16(ext4_ext_space_root(inode));
2026                         err = ext4_ext_dirty(handle, inode, path);
2027                 }
2028         }
2029 out:
2030         ext4_ext_tree_changed(inode);
2031         ext4_ext_drop_refs(path);
2032         kfree(path);
2033         ext4_journal_stop(handle);
2034
2035         return err;
2036 }
2037
2038 /*
2039  * called at mount time
2040  */
2041 void ext4_ext_init(struct super_block *sb)
2042 {
2043         /*
2044          * possible initialization would be here
2045          */
2046
2047         if (test_opt(sb, EXTENTS)) {
2048                 printk("EXT4-fs: file extents enabled");
2049 #ifdef AGGRESSIVE_TEST
2050                 printk(", aggressive tests");
2051 #endif
2052 #ifdef CHECK_BINSEARCH
2053                 printk(", check binsearch");
2054 #endif
2055 #ifdef EXTENTS_STATS
2056                 printk(", stats");
2057 #endif
2058                 printk("\n");
2059 #ifdef EXTENTS_STATS
2060                 spin_lock_init(&EXT4_SB(sb)->s_ext_stats_lock);
2061                 EXT4_SB(sb)->s_ext_min = 1 << 30;
2062                 EXT4_SB(sb)->s_ext_max = 0;
2063 #endif
2064         }
2065 }
2066
2067 /*
2068  * called at umount time
2069  */
2070 void ext4_ext_release(struct super_block *sb)
2071 {
2072         if (!test_opt(sb, EXTENTS))
2073                 return;
2074
2075 #ifdef EXTENTS_STATS
2076         if (EXT4_SB(sb)->s_ext_blocks && EXT4_SB(sb)->s_ext_extents) {
2077                 struct ext4_sb_info *sbi = EXT4_SB(sb);
2078                 printk(KERN_ERR "EXT4-fs: %lu blocks in %lu extents (%lu ave)\n",
2079                         sbi->s_ext_blocks, sbi->s_ext_extents,
2080                         sbi->s_ext_blocks / sbi->s_ext_extents);
2081                 printk(KERN_ERR "EXT4-fs: extents: %lu min, %lu max, max depth %lu\n",
2082                         sbi->s_ext_min, sbi->s_ext_max, sbi->s_depth_max);
2083         }
2084 #endif
2085 }
2086
2087 /*
2088  * This function is called by ext4_ext_get_blocks() if someone tries to write
2089  * to an uninitialized extent. It may result in splitting the uninitialized
2090  * extent into multiple extents (upto three - one initialized and two
2091  * uninitialized).
2092  * There are three possibilities:
2093  *   a> There is no split required: Entire extent should be initialized
2094  *   b> Splits in two extents: Write is happening at either end of the extent
2095  *   c> Splits in three extents: Somone is writing in middle of the extent
2096  */
2097 int ext4_ext_convert_to_initialized(handle_t *handle, struct inode *inode,
2098                                         struct ext4_ext_path *path,
2099                                         ext4_fsblk_t iblock,
2100                                         unsigned long max_blocks)
2101 {
2102         struct ext4_extent *ex, newex;
2103         struct ext4_extent *ex1 = NULL;
2104         struct ext4_extent *ex2 = NULL;
2105         struct ext4_extent *ex3 = NULL;
2106         struct ext4_extent_header *eh;
2107         unsigned int allocated, ee_block, ee_len, depth;
2108         ext4_fsblk_t newblock;
2109         int err = 0;
2110         int ret = 0;
2111
2112         depth = ext_depth(inode);
2113         eh = path[depth].p_hdr;
2114         ex = path[depth].p_ext;
2115         ee_block = le32_to_cpu(ex->ee_block);
2116         ee_len = ext4_ext_get_actual_len(ex);
2117         allocated = ee_len - (iblock - ee_block);
2118         newblock = iblock - ee_block + ext_pblock(ex);
2119         ex2 = ex;
2120
2121         /* ex1: ee_block to iblock - 1 : uninitialized */
2122         if (iblock > ee_block) {
2123                 ex1 = ex;
2124                 ex1->ee_len = cpu_to_le16(iblock - ee_block);
2125                 ext4_ext_mark_uninitialized(ex1);
2126                 ex2 = &newex;
2127         }
2128         /*
2129          * for sanity, update the length of the ex2 extent before
2130          * we insert ex3, if ex1 is NULL. This is to avoid temporary
2131          * overlap of blocks.
2132          */
2133         if (!ex1 && allocated > max_blocks)
2134                 ex2->ee_len = cpu_to_le16(max_blocks);
2135         /* ex3: to ee_block + ee_len : uninitialised */
2136         if (allocated > max_blocks) {
2137                 unsigned int newdepth;
2138                 ex3 = &newex;
2139                 ex3->ee_block = cpu_to_le32(iblock + max_blocks);
2140                 ext4_ext_store_pblock(ex3, newblock + max_blocks);
2141                 ex3->ee_len = cpu_to_le16(allocated - max_blocks);
2142                 ext4_ext_mark_uninitialized(ex3);
2143                 err = ext4_ext_insert_extent(handle, inode, path, ex3);
2144                 if (err)
2145                         goto out;
2146                 /*
2147                  * The depth, and hence eh & ex might change
2148                  * as part of the insert above.
2149                  */
2150                 newdepth = ext_depth(inode);
2151                 if (newdepth != depth) {
2152                         depth = newdepth;
2153                         path = ext4_ext_find_extent(inode, iblock, NULL);
2154                         if (IS_ERR(path)) {
2155                                 err = PTR_ERR(path);
2156                                 path = NULL;
2157                                 goto out;
2158                         }
2159                         eh = path[depth].p_hdr;
2160                         ex = path[depth].p_ext;
2161                         if (ex2 != &newex)
2162                                 ex2 = ex;
2163                 }
2164                 allocated = max_blocks;
2165         }
2166         /*
2167          * If there was a change of depth as part of the
2168          * insertion of ex3 above, we need to update the length
2169          * of the ex1 extent again here
2170          */
2171         if (ex1 && ex1 != ex) {
2172                 ex1 = ex;
2173                 ex1->ee_len = cpu_to_le16(iblock - ee_block);
2174                 ext4_ext_mark_uninitialized(ex1);
2175                 ex2 = &newex;
2176         }
2177         /* ex2: iblock to iblock + maxblocks-1 : initialised */
2178         ex2->ee_block = cpu_to_le32(iblock);
2179         ext4_ext_store_pblock(ex2, newblock);
2180         ex2->ee_len = cpu_to_le16(allocated);
2181         if (ex2 != ex)
2182                 goto insert;
2183         err = ext4_ext_get_access(handle, inode, path + depth);
2184         if (err)
2185                 goto out;
2186         /*
2187          * New (initialized) extent starts from the first block
2188          * in the current extent. i.e., ex2 == ex
2189          * We have to see if it can be merged with the extent
2190          * on the left.
2191          */
2192         if (ex2 > EXT_FIRST_EXTENT(eh)) {
2193                 /*
2194                  * To merge left, pass "ex2 - 1" to try_to_merge(),
2195                  * since it merges towards right _only_.
2196                  */
2197                 ret = ext4_ext_try_to_merge(inode, path, ex2 - 1);
2198                 if (ret) {
2199                         err = ext4_ext_correct_indexes(handle, inode, path);
2200                         if (err)
2201                                 goto out;
2202                         depth = ext_depth(inode);
2203                         ex2--;
2204                 }
2205         }
2206         /*
2207          * Try to Merge towards right. This might be required
2208          * only when the whole extent is being written to.
2209          * i.e. ex2 == ex and ex3 == NULL.
2210          */
2211         if (!ex3) {
2212                 ret = ext4_ext_try_to_merge(inode, path, ex2);
2213                 if (ret) {
2214                         err = ext4_ext_correct_indexes(handle, inode, path);
2215                         if (err)
2216                                 goto out;
2217                 }
2218         }
2219         /* Mark modified extent as dirty */
2220         err = ext4_ext_dirty(handle, inode, path + depth);
2221         goto out;
2222 insert:
2223         err = ext4_ext_insert_extent(handle, inode, path, &newex);
2224 out:
2225         return err ? err : allocated;
2226 }
2227
2228 int ext4_ext_get_blocks(handle_t *handle, struct inode *inode,
2229                         ext4_fsblk_t iblock,
2230                         unsigned long max_blocks, struct buffer_head *bh_result,
2231                         int create, int extend_disksize)
2232 {
2233         struct ext4_ext_path *path = NULL;
2234         struct ext4_extent_header *eh;
2235         struct ext4_extent newex, *ex;
2236         ext4_fsblk_t goal, newblock;
2237         int err = 0, depth, ret;
2238         unsigned long allocated = 0;
2239
2240         __clear_bit(BH_New, &bh_result->b_state);
2241         ext_debug("blocks %d/%lu requested for inode %u\n", (int) iblock,
2242                         max_blocks, (unsigned) inode->i_ino);
2243         mutex_lock(&EXT4_I(inode)->truncate_mutex);
2244
2245         /* check in cache */
2246         goal = ext4_ext_in_cache(inode, iblock, &newex);
2247         if (goal) {
2248                 if (goal == EXT4_EXT_CACHE_GAP) {
2249                         if (!create) {
2250                                 /*
2251                                  * block isn't allocated yet and
2252                                  * user doesn't want to allocate it
2253                                  */
2254                                 goto out2;
2255                         }
2256                         /* we should allocate requested block */
2257                 } else if (goal == EXT4_EXT_CACHE_EXTENT) {
2258                         /* block is already allocated */
2259                         newblock = iblock
2260                                    - le32_to_cpu(newex.ee_block)
2261                                    + ext_pblock(&newex);
2262                         /* number of remaining blocks in the extent */
2263                         allocated = le16_to_cpu(newex.ee_len) -
2264                                         (iblock - le32_to_cpu(newex.ee_block));
2265                         goto out;
2266                 } else {
2267                         BUG();
2268                 }
2269         }
2270
2271         /* find extent for this block */
2272         path = ext4_ext_find_extent(inode, iblock, NULL);
2273         if (IS_ERR(path)) {
2274                 err = PTR_ERR(path);
2275                 path = NULL;
2276                 goto out2;
2277         }
2278
2279         depth = ext_depth(inode);
2280
2281         /*
2282          * consistent leaf must not be empty;
2283          * this situation is possible, though, _during_ tree modification;
2284          * this is why assert can't be put in ext4_ext_find_extent()
2285          */
2286         BUG_ON(path[depth].p_ext == NULL && depth != 0);
2287         eh = path[depth].p_hdr;
2288
2289         ex = path[depth].p_ext;
2290         if (ex) {
2291                 unsigned long ee_block = le32_to_cpu(ex->ee_block);
2292                 ext4_fsblk_t ee_start = ext_pblock(ex);
2293                 unsigned short ee_len;
2294
2295                 /*
2296                  * Uninitialized extents are treated as holes, except that
2297                  * we split out initialized portions during a write.
2298                  */
2299                 ee_len = ext4_ext_get_actual_len(ex);
2300                 /* if found extent covers block, simply return it */
2301                 if (iblock >= ee_block && iblock < ee_block + ee_len) {
2302                         newblock = iblock - ee_block + ee_start;
2303                         /* number of remaining blocks in the extent */
2304                         allocated = ee_len - (iblock - ee_block);
2305                         ext_debug("%d fit into %lu:%d -> %llu\n", (int) iblock,
2306                                         ee_block, ee_len, newblock);
2307
2308                         /* Do not put uninitialized extent in the cache */
2309                         if (!ext4_ext_is_uninitialized(ex)) {
2310                                 ext4_ext_put_in_cache(inode, ee_block,
2311                                                         ee_len, ee_start,
2312                                                         EXT4_EXT_CACHE_EXTENT);
2313                                 goto out;
2314                         }
2315                         if (create == EXT4_CREATE_UNINITIALIZED_EXT)
2316                                 goto out;
2317                         if (!create)
2318                                 goto out2;
2319
2320                         ret = ext4_ext_convert_to_initialized(handle, inode,
2321                                                                 path, iblock,
2322                                                                 max_blocks);
2323                         if (ret <= 0)
2324                                 goto out2;
2325                         else
2326                                 allocated = ret;
2327                         goto outnew;
2328                 }
2329         }
2330
2331         /*
2332          * requested block isn't allocated yet;
2333          * we couldn't try to create block if create flag is zero
2334          */
2335         if (!create) {
2336                 /*
2337                  * put just found gap into cache to speed up
2338                  * subsequent requests
2339                  */
2340                 ext4_ext_put_gap_in_cache(inode, path, iblock);
2341                 goto out2;
2342         }
2343         /*
2344          * Okay, we need to do block allocation.  Lazily initialize the block
2345          * allocation info here if necessary.
2346          */
2347         if (S_ISREG(inode->i_mode) && (!EXT4_I(inode)->i_block_alloc_info))
2348                 ext4_init_block_alloc_info(inode);
2349
2350         /* allocate new block */
2351         goal = ext4_ext_find_goal(inode, path, iblock);
2352
2353         /*
2354          * See if request is beyond maximum number of blocks we can have in
2355          * a single extent. For an initialized extent this limit is
2356          * EXT_INIT_MAX_LEN and for an uninitialized extent this limit is
2357          * EXT_UNINIT_MAX_LEN.
2358          */
2359         if (max_blocks > EXT_INIT_MAX_LEN &&
2360             create != EXT4_CREATE_UNINITIALIZED_EXT)
2361                 max_blocks = EXT_INIT_MAX_LEN;
2362         else if (max_blocks > EXT_UNINIT_MAX_LEN &&
2363                  create == EXT4_CREATE_UNINITIALIZED_EXT)
2364                 max_blocks = EXT_UNINIT_MAX_LEN;
2365
2366         /* Check if we can really insert (iblock)::(iblock+max_blocks) extent */
2367         newex.ee_block = cpu_to_le32(iblock);
2368         newex.ee_len = cpu_to_le16(max_blocks);
2369         err = ext4_ext_check_overlap(inode, &newex, path);
2370         if (err)
2371                 allocated = le16_to_cpu(newex.ee_len);
2372         else
2373                 allocated = max_blocks;
2374         newblock = ext4_new_blocks(handle, inode, goal, &allocated, &err);
2375         if (!newblock)
2376                 goto out2;
2377         ext_debug("allocate new block: goal %llu, found %llu/%lu\n",
2378                         goal, newblock, allocated);
2379
2380         /* try to insert new extent into found leaf and return */
2381         ext4_ext_store_pblock(&newex, newblock);
2382         newex.ee_len = cpu_to_le16(allocated);
2383         if (create == EXT4_CREATE_UNINITIALIZED_EXT)  /* Mark uninitialized */
2384                 ext4_ext_mark_uninitialized(&newex);
2385         err = ext4_ext_insert_extent(handle, inode, path, &newex);
2386         if (err) {
2387                 /* free data blocks we just allocated */
2388                 ext4_free_blocks(handle, inode, ext_pblock(&newex),
2389                                         le16_to_cpu(newex.ee_len));
2390                 goto out2;
2391         }
2392
2393         if (extend_disksize && inode->i_size > EXT4_I(inode)->i_disksize)
2394                 EXT4_I(inode)->i_disksize = inode->i_size;
2395
2396         /* previous routine could use block we allocated */
2397         newblock = ext_pblock(&newex);
2398 outnew:
2399         __set_bit(BH_New, &bh_result->b_state);
2400
2401         /* Cache only when it is _not_ an uninitialized extent */
2402         if (create != EXT4_CREATE_UNINITIALIZED_EXT)
2403                 ext4_ext_put_in_cache(inode, iblock, allocated, newblock,
2404                                                 EXT4_EXT_CACHE_EXTENT);
2405 out:
2406         if (allocated > max_blocks)
2407                 allocated = max_blocks;
2408         ext4_ext_show_leaf(inode, path);
2409         __set_bit(BH_Mapped, &bh_result->b_state);
2410         bh_result->b_bdev = inode->i_sb->s_bdev;
2411         bh_result->b_blocknr = newblock;
2412 out2:
2413         if (path) {
2414                 ext4_ext_drop_refs(path);
2415                 kfree(path);
2416         }
2417         mutex_unlock(&EXT4_I(inode)->truncate_mutex);
2418
2419         return err ? err : allocated;
2420 }
2421
2422 void ext4_ext_truncate(struct inode * inode, struct page *page)
2423 {
2424         struct address_space *mapping = inode->i_mapping;
2425         struct super_block *sb = inode->i_sb;
2426         unsigned long last_block;
2427         handle_t *handle;
2428         int err = 0;
2429
2430         /*
2431          * probably first extent we're gonna free will be last in block
2432          */
2433         err = ext4_writepage_trans_blocks(inode) + 3;
2434         handle = ext4_journal_start(inode, err);
2435         if (IS_ERR(handle)) {
2436                 if (page) {
2437                         clear_highpage(page);
2438                         flush_dcache_page(page);
2439                         unlock_page(page);
2440                         page_cache_release(page);
2441                 }
2442                 return;
2443         }
2444
2445         if (page)
2446                 ext4_block_truncate_page(handle, page, mapping, inode->i_size);
2447
2448         mutex_lock(&EXT4_I(inode)->truncate_mutex);
2449         ext4_ext_invalidate_cache(inode);
2450
2451         /*
2452          * TODO: optimization is possible here.
2453          * Probably we need not scan at all,
2454          * because page truncation is enough.
2455          */
2456         if (ext4_orphan_add(handle, inode))
2457                 goto out_stop;
2458
2459         /* we have to know where to truncate from in crash case */
2460         EXT4_I(inode)->i_disksize = inode->i_size;
2461         ext4_mark_inode_dirty(handle, inode);
2462
2463         last_block = (inode->i_size + sb->s_blocksize - 1)
2464                         >> EXT4_BLOCK_SIZE_BITS(sb);
2465         err = ext4_ext_remove_space(inode, last_block);
2466
2467         /* In a multi-transaction truncate, we only make the final
2468          * transaction synchronous.
2469          */
2470         if (IS_SYNC(inode))
2471                 handle->h_sync = 1;
2472
2473 out_stop:
2474         /*
2475          * If this was a simple ftruncate() and the file will remain alive,
2476          * then we need to clear up the orphan record which we created above.
2477          * However, if this was a real unlink then we were called by
2478          * ext4_delete_inode(), and we allow that function to clean up the
2479          * orphan info for us.
2480          */
2481         if (inode->i_nlink)
2482                 ext4_orphan_del(handle, inode);
2483
2484         mutex_unlock(&EXT4_I(inode)->truncate_mutex);
2485         ext4_journal_stop(handle);
2486 }
2487
2488 /*
2489  * ext4_ext_writepage_trans_blocks:
2490  * calculate max number of blocks we could modify
2491  * in order to allocate new block for an inode
2492  */
2493 int ext4_ext_writepage_trans_blocks(struct inode *inode, int num)
2494 {
2495         int needed;
2496
2497         needed = ext4_ext_calc_credits_for_insert(inode, NULL);
2498
2499         /* caller wants to allocate num blocks, but note it includes sb */
2500         needed = needed * num - (num - 1);
2501
2502 #ifdef CONFIG_QUOTA
2503         needed += 2 * EXT4_QUOTA_TRANS_BLOCKS(inode->i_sb);
2504 #endif
2505
2506         return needed;
2507 }
2508
2509 /*
2510  * preallocate space for a file. This implements ext4's fallocate inode
2511  * operation, which gets called from sys_fallocate system call.
2512  * For block-mapped files, posix_fallocate should fall back to the method
2513  * of writing zeroes to the required new blocks (the same behavior which is
2514  * expected for file systems which do not support fallocate() system call).
2515  */
2516 long ext4_fallocate(struct inode *inode, int mode, loff_t offset, loff_t len)
2517 {
2518         handle_t *handle;
2519         ext4_fsblk_t block, max_blocks;
2520         ext4_fsblk_t nblocks = 0;
2521         int ret = 0;
2522         int ret2 = 0;
2523         int retries = 0;
2524         struct buffer_head map_bh;
2525         unsigned int credits, blkbits = inode->i_blkbits;
2526
2527         /*
2528          * currently supporting (pre)allocate mode for extent-based
2529          * files _only_
2530          */
2531         if (!(EXT4_I(inode)->i_flags & EXT4_EXTENTS_FL))
2532                 return -EOPNOTSUPP;
2533
2534         /* preallocation to directories is currently not supported */
2535         if (S_ISDIR(inode->i_mode))
2536                 return -ENODEV;
2537
2538         block = offset >> blkbits;
2539         max_blocks = (EXT4_BLOCK_ALIGN(len + offset, blkbits) >> blkbits)
2540                         - block;
2541
2542         /*
2543          * credits to insert 1 extent into extent tree + buffers to be able to
2544          * modify 1 super block, 1 block bitmap and 1 group descriptor.
2545          */
2546         credits = EXT4_DATA_TRANS_BLOCKS(inode->i_sb) + 3;
2547 retry:
2548         while (ret >= 0 && ret < max_blocks) {
2549                 block = block + ret;
2550                 max_blocks = max_blocks - ret;
2551                 handle = ext4_journal_start(inode, credits);
2552                 if (IS_ERR(handle)) {
2553                         ret = PTR_ERR(handle);
2554                         break;
2555                 }
2556
2557                 ret = ext4_ext_get_blocks(handle, inode, block,
2558                                           max_blocks, &map_bh,
2559                                           EXT4_CREATE_UNINITIALIZED_EXT, 0);
2560                 WARN_ON(!ret);
2561                 if (!ret) {
2562                         ext4_error(inode->i_sb, "ext4_fallocate",
2563                                    "ext4_ext_get_blocks returned 0! inode#%lu"
2564                                    ", block=%llu, max_blocks=%llu",
2565                                    inode->i_ino, block, max_blocks);
2566                         ret = -EIO;
2567                         ext4_mark_inode_dirty(handle, inode);
2568                         ret2 = ext4_journal_stop(handle);
2569                         break;
2570                 }
2571                 if (ret > 0) {
2572                         /* check wrap through sign-bit/zero here */
2573                         if ((block + ret) < 0 || (block + ret) < block) {
2574                                 ret = -EIO;
2575                                 ext4_mark_inode_dirty(handle, inode);
2576                                 ret2 = ext4_journal_stop(handle);
2577                                 break;
2578                         }
2579                         if (buffer_new(&map_bh) && ((block + ret) >
2580                             (EXT4_BLOCK_ALIGN(i_size_read(inode), blkbits)
2581                             >> blkbits)))
2582                                         nblocks = nblocks + ret;
2583                 }
2584
2585                 /* Update ctime if new blocks get allocated */
2586                 if (nblocks) {
2587                         struct timespec now;
2588
2589                         now = current_fs_time(inode->i_sb);
2590                         if (!timespec_equal(&inode->i_ctime, &now))
2591                                 inode->i_ctime = now;
2592                 }
2593
2594                 ext4_mark_inode_dirty(handle, inode);
2595                 ret2 = ext4_journal_stop(handle);
2596                 if (ret2)
2597                         break;
2598         }
2599
2600         if (ret == -ENOSPC && ext4_should_retry_alloc(inode->i_sb, &retries))
2601                 goto retry;
2602
2603         /*
2604          * Time to update the file size.
2605          * Update only when preallocation was requested beyond the file size.
2606          */
2607         if (!(mode & FALLOC_FL_KEEP_SIZE) &&
2608             (offset + len) > i_size_read(inode)) {
2609                 if (ret > 0) {
2610                         /*
2611                          * if no error, we assume preallocation succeeded
2612                          * completely
2613                          */
2614                         mutex_lock(&inode->i_mutex);
2615                         i_size_write(inode, offset + len);
2616                         EXT4_I(inode)->i_disksize = i_size_read(inode);
2617                         mutex_unlock(&inode->i_mutex);
2618                 } else if (ret < 0 && nblocks) {
2619                         /* Handle partial allocation scenario */
2620                         loff_t newsize;
2621
2622                         mutex_lock(&inode->i_mutex);
2623                         newsize  = (nblocks << blkbits) + i_size_read(inode);
2624                         i_size_write(inode, EXT4_BLOCK_ALIGN(newsize, blkbits));
2625                         EXT4_I(inode)->i_disksize = i_size_read(inode);
2626                         mutex_unlock(&inode->i_mutex);
2627                 }
2628         }
2629
2630         return ret > 0 ? ret2 : ret;
2631 }