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