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