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/iomap.h>
  31 #include <linux/sched/mm.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         __u32 csum;
  54
  55         csum = ext4_chksum(ei->i_csum_seed, (__u8 *)eh,
  56                            EXT4_EXTENT_TAIL_OFFSET(eh));
  57         return cpu_to_le32(csum);
  58 }
  59
  60 static int ext4_extent_block_csum_verify(struct inode *inode,
  61                                          struct ext4_extent_header *eh)
  62 {
  63         struct ext4_extent_tail *et;
  64
  65         if (!ext4_has_feature_metadata_csum(inode->i_sb))
  66                 return 1;
  67
  68         et = find_ext4_extent_tail(eh);
  69         if (et->et_checksum != ext4_extent_block_csum(inode, eh))
  70                 return 0;
  71         return 1;
  72 }
  73
  74 static void ext4_extent_block_csum_set(struct inode *inode,
  75                                        struct ext4_extent_header *eh)
  76 {
  77         struct ext4_extent_tail *et;
  78
  79         if (!ext4_has_feature_metadata_csum(inode->i_sb))
  80                 return;
  81
  82         et = find_ext4_extent_tail(eh);
  83         et->et_checksum = ext4_extent_block_csum(inode, eh);
  84 }
  85
  86 static struct ext4_ext_path *ext4_split_extent_at(handle_t *handle,
  87                                                   struct inode *inode,
  88                                                   struct ext4_ext_path *path,
  89                                                   ext4_lblk_t split,
  90                                                   int split_flag, int flags);
  91
  92 static int ext4_ext_trunc_restart_fn(struct inode *inode, int *dropped)
  93 {
  94         /*
  95          * Drop i_data_sem to avoid deadlock with ext4_map_blocks.  At this
  96          * moment, get_block can be called only for blocks inside i_size since
  97          * page cache has been already dropped and writes are blocked by
  98          * i_rwsem. So we can safely drop the i_data_sem here.
  99          */
 100         BUG_ON(EXT4_JOURNAL(inode) == NULL);
 101         ext4_discard_preallocations(inode);
 102         up_write(&EXT4_I(inode)->i_data_sem);
 103         *dropped = 1;
 104         return 0;
 105 }
 106
 107 static inline void ext4_ext_path_brelse(struct ext4_ext_path *path)
 108 {
 109         brelse(path->p_bh);
 110         path->p_bh = NULL;
 111 }
 112
 113 static void ext4_ext_drop_refs(struct ext4_ext_path *path)
 114 {
 115         int depth, i;
 116
 117         if (IS_ERR_OR_NULL(path))
 118                 return;
 119         depth = path->p_depth;
 120         for (i = 0; i <= depth; i++, path++)
 121                 ext4_ext_path_brelse(path);
 122 }
 123
 124 void ext4_free_ext_path(struct ext4_ext_path *path)
 125 {
 126         if (IS_ERR_OR_NULL(path))
 127                 return;
 128         ext4_ext_drop_refs(path);
 129         kfree(path);
 130 }
 131
 132 /*
 133  * Make sure 'handle' has at least 'check_cred' credits. If not, restart
 134  * transaction with 'restart_cred' credits. The function drops i_data_sem
 135  * when restarting transaction and gets it after transaction is restarted.
 136  *
 137  * The function returns 0 on success, 1 if transaction had to be restarted,
 138  * and < 0 in case of fatal error.
 139  */
 140 int ext4_datasem_ensure_credits(handle_t *handle, struct inode *inode,
 141                                 int check_cred, int restart_cred,
 142                                 int revoke_cred)
 143 {
 144         int ret;
 145         int dropped = 0;
 146
 147         ret = ext4_journal_ensure_credits_fn(handle, check_cred, restart_cred,
 148                 revoke_cred, ext4_ext_trunc_restart_fn(inode, &dropped));
 149         if (dropped)
 150                 down_write(&EXT4_I(inode)->i_data_sem);
 151         return ret;
 152 }
 153
 154 /*
 155  * could return:
 156  *  - EROFS
 157  *  - ENOMEM
 158  */
 159 static int ext4_ext_get_access(handle_t *handle, struct inode *inode,
 160                                 struct ext4_ext_path *path)
 161 {
 162         int err = 0;
 163
 164         if (path->p_bh) {
 165                 /* path points to block */
 166                 BUFFER_TRACE(path->p_bh, "get_write_access");
 167                 err = ext4_journal_get_write_access(handle, inode->i_sb,
 168                                                     path->p_bh, EXT4_JTR_NONE);
 169                 /*
 170                  * The extent buffer's verified bit will be set again in
 171                  * __ext4_ext_dirty(). We could leave an inconsistent
 172                  * buffer if the extents updating procudure break off du
 173                  * to some error happens, force to check it again.
 174                  */
 175                 if (!err)
 176                         clear_buffer_verified(path->p_bh);
 177         }
 178         /* path points to leaf/index in inode body */
 179         /* we use in-core data, no need to protect them */
 180         return err;
 181 }
 182
 183 /*
 184  * could return:
 185  *  - EROFS
 186  *  - ENOMEM
 187  *  - EIO
 188  */
 189 static int __ext4_ext_dirty(const char *where, unsigned int line,
 190                             handle_t *handle, struct inode *inode,
 191                             struct ext4_ext_path *path)
 192 {
 193         int err;
 194
 195         WARN_ON(!rwsem_is_locked(&EXT4_I(inode)->i_data_sem));
 196         if (path->p_bh) {
 197                 ext4_extent_block_csum_set(inode, ext_block_hdr(path->p_bh));
 198                 /* path points to block */
 199                 err = __ext4_handle_dirty_metadata(where, line, handle,
 200                                                    inode, path->p_bh);
 201                 /* Extents updating done, re-set verified flag */
 202                 if (!err)
 203                         set_buffer_verified(path->p_bh);
 204         } else {
 205                 /* path points to leaf/index in inode body */
 206                 err = ext4_mark_inode_dirty(handle, inode);
 207         }
 208         return err;
 209 }
 210
 211 #define ext4_ext_dirty(handle, inode, path) \
 212                 __ext4_ext_dirty(__func__, __LINE__, (handle), (inode), (path))
 213
 214 static ext4_fsblk_t ext4_ext_find_goal(struct inode *inode,
 215                               struct ext4_ext_path *path,
 216                               ext4_lblk_t block)
 217 {
 218         if (path) {
 219                 int depth = path->p_depth;
 220                 struct ext4_extent *ex;
 221
 222                 /*
 223                  * Try to predict block placement assuming that we are
 224                  * filling in a file which will eventually be
 225                  * non-sparse --- i.e., in the case of libbfd writing
 226                  * an ELF object sections out-of-order but in a way
 227                  * the eventually results in a contiguous object or
 228                  * executable file, or some database extending a table
 229                  * space file.  However, this is actually somewhat
 230                  * non-ideal if we are writing a sparse file such as
 231                  * qemu or KVM writing a raw image file that is going
 232                  * to stay fairly sparse, since it will end up
 233                  * fragmenting the file system's free space.  Maybe we
 234                  * should have some hueristics or some way to allow
 235                  * userspace to pass a hint to file system,
 236                  * especially if the latter case turns out to be
 237                  * common.
 238                  */
 239                 ex = path[depth].p_ext;
 240                 if (ex) {
 241                         ext4_fsblk_t ext_pblk = ext4_ext_pblock(ex);
 242                         ext4_lblk_t ext_block = le32_to_cpu(ex->ee_block);
 243
 244                         if (block > ext_block)
 245                                 return ext_pblk + (block - ext_block);
 246                         else
 247                                 return ext_pblk - (ext_block - block);
 248                 }
 249
 250                 /* it looks like index is empty;
 251                  * try to find starting block from index itself */
 252                 if (path[depth].p_bh)
 253                         return path[depth].p_bh->b_blocknr;
 254         }
 255
 256         /* OK. use inode's group */
 257         return ext4_inode_to_goal_block(inode);
 258 }
 259
 260 /*
 261  * Allocation for a meta data block
 262  */
 263 static ext4_fsblk_t
 264 ext4_ext_new_meta_block(handle_t *handle, struct inode *inode,
 265                         struct ext4_ext_path *path,
 266                         struct ext4_extent *ex, int *err, unsigned int flags)
 267 {
 268         ext4_fsblk_t goal, newblock;
 269
 270         goal = ext4_ext_find_goal(inode, path, le32_to_cpu(ex->ee_block));
 271         newblock = ext4_new_meta_blocks(handle, inode, goal, flags,
 272                                         NULL, err);
 273         return newblock;
 274 }
 275
 276 static inline int ext4_ext_space_block(struct inode *inode, int check)
 277 {
 278         int size;
 279
 280         size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
 281                         / sizeof(struct ext4_extent);
 282 #ifdef AGGRESSIVE_TEST
 283         if (!check && size > 6)
 284                 size = 6;
 285 #endif
 286         return size;
 287 }
 288
 289 static inline int ext4_ext_space_block_idx(struct inode *inode, int check)
 290 {
 291         int size;
 292
 293         size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
 294                         / sizeof(struct ext4_extent_idx);
 295 #ifdef AGGRESSIVE_TEST
 296         if (!check && size > 5)
 297                 size = 5;
 298 #endif
 299         return size;
 300 }
 301
 302 static inline int ext4_ext_space_root(struct inode *inode, int check)
 303 {
 304         int size;
 305
 306         size = sizeof(EXT4_I(inode)->i_data);
 307         size -= sizeof(struct ext4_extent_header);
 308         size /= sizeof(struct ext4_extent);
 309 #ifdef AGGRESSIVE_TEST
 310         if (!check && size > 3)
 311                 size = 3;
 312 #endif
 313         return size;
 314 }
 315
 316 static inline int ext4_ext_space_root_idx(struct inode *inode, int check)
 317 {
 318         int size;
 319
 320         size = sizeof(EXT4_I(inode)->i_data);
 321         size -= sizeof(struct ext4_extent_header);
 322         size /= sizeof(struct ext4_extent_idx);
 323 #ifdef AGGRESSIVE_TEST
 324         if (!check && size > 4)
 325                 size = 4;
 326 #endif
 327         return size;
 328 }
 329
 330 static inline struct ext4_ext_path *
 331 ext4_force_split_extent_at(handle_t *handle, struct inode *inode,
 332                            struct ext4_ext_path *path, ext4_lblk_t lblk,
 333                            int nofail)
 334 {
 335         int unwritten = ext4_ext_is_unwritten(path[path->p_depth].p_ext);
 336         int flags = EXT4_EX_NOCACHE | EXT4_GET_BLOCKS_PRE_IO;
 337
 338         if (nofail)
 339                 flags |= EXT4_GET_BLOCKS_METADATA_NOFAIL | EXT4_EX_NOFAIL;
 340
 341         return ext4_split_extent_at(handle, inode, path, lblk, unwritten ?
 342                         EXT4_EXT_MARK_UNWRIT1|EXT4_EXT_MARK_UNWRIT2 : 0,
 343                         flags);
 344 }
 345
 346 static int
 347 ext4_ext_max_entries(struct inode *inode, int depth)
 348 {
 349         int max;
 350
 351         if (depth == ext_depth(inode)) {
 352                 if (depth == 0)
 353                         max = ext4_ext_space_root(inode, 1);
 354                 else
 355                         max = ext4_ext_space_root_idx(inode, 1);
 356         } else {
 357                 if (depth == 0)
 358                         max = ext4_ext_space_block(inode, 1);
 359                 else
 360                         max = ext4_ext_space_block_idx(inode, 1);
 361         }
 362
 363         return max;
 364 }
 365
 366 static int ext4_valid_extent(struct inode *inode, struct ext4_extent *ext)
 367 {
 368         ext4_fsblk_t block = ext4_ext_pblock(ext);
 369         int len = ext4_ext_get_actual_len(ext);
 370         ext4_lblk_t lblock = le32_to_cpu(ext->ee_block);
 371
 372         /*
 373          * We allow neither:
 374          *  - zero length
 375          *  - overflow/wrap-around
 376          */
 377         if (lblock + len <= lblock)
 378                 return 0;
 379         return ext4_inode_block_valid(inode, block, len);
 380 }
 381
 382 static int ext4_valid_extent_idx(struct inode *inode,
 383                                 struct ext4_extent_idx *ext_idx)
 384 {
 385         ext4_fsblk_t block = ext4_idx_pblock(ext_idx);
 386
 387         return ext4_inode_block_valid(inode, block, 1);
 388 }
 389
 390 static int ext4_valid_extent_entries(struct inode *inode,
 391                                      struct ext4_extent_header *eh,
 392                                      ext4_lblk_t lblk, ext4_fsblk_t *pblk,
 393                                      int depth)
 394 {
 395         unsigned short entries;
 396         ext4_lblk_t lblock = 0;
 397         ext4_lblk_t cur = 0;
 398
 399         if (eh->eh_entries == 0)
 400                 return 1;
 401
 402         entries = le16_to_cpu(eh->eh_entries);
 403
 404         if (depth == 0) {
 405                 /* leaf entries */
 406                 struct ext4_extent *ext = EXT_FIRST_EXTENT(eh);
 407
 408                 /*
 409                  * The logical block in the first entry should equal to
 410                  * the number in the index block.
 411                  */
 412                 if (depth != ext_depth(inode) &&
 413                     lblk != le32_to_cpu(ext->ee_block))
 414                         return 0;
 415                 while (entries) {
 416                         if (!ext4_valid_extent(inode, ext))
 417                                 return 0;
 418
 419                         /* Check for overlapping extents */
 420                         lblock = le32_to_cpu(ext->ee_block);
 421                         if (lblock < cur) {
 422                                 *pblk = ext4_ext_pblock(ext);
 423                                 return 0;
 424                         }
 425                         cur = lblock + ext4_ext_get_actual_len(ext);
 426                         ext++;
 427                         entries--;
 428                 }
 429         } else {
 430                 struct ext4_extent_idx *ext_idx = EXT_FIRST_INDEX(eh);
 431
 432                 /*
 433                  * The logical block in the first entry should equal to
 434                  * the number in the parent index block.
 435                  */
 436                 if (depth != ext_depth(inode) &&
 437                     lblk != le32_to_cpu(ext_idx->ei_block))
 438                         return 0;
 439                 while (entries) {
 440                         if (!ext4_valid_extent_idx(inode, ext_idx))
 441                                 return 0;
 442
 443                         /* Check for overlapping index extents */
 444                         lblock = le32_to_cpu(ext_idx->ei_block);
 445                         if (lblock < cur) {
 446                                 *pblk = ext4_idx_pblock(ext_idx);
 447                                 return 0;
 448                         }
 449                         ext_idx++;
 450                         entries--;
 451                         cur = lblock + 1;
 452                 }
 453         }
 454         return 1;
 455 }
 456
 457 static int __ext4_ext_check(const char *function, unsigned int line,
 458                             struct inode *inode, struct ext4_extent_header *eh,
 459                             int depth, ext4_fsblk_t pblk, ext4_lblk_t lblk)
 460 {
 461         const char *error_msg;
 462         int max = 0, err = -EFSCORRUPTED;
 463
 464         if (unlikely(eh->eh_magic != EXT4_EXT_MAGIC)) {
 465                 error_msg = "invalid magic";
 466                 goto corrupted;
 467         }
 468         if (unlikely(le16_to_cpu(eh->eh_depth) != depth)) {
 469                 error_msg = "unexpected eh_depth";
 470                 goto corrupted;
 471         }
 472         if (unlikely(eh->eh_max == 0)) {
 473                 error_msg = "invalid eh_max";
 474                 goto corrupted;
 475         }
 476         max = ext4_ext_max_entries(inode, depth);
 477         if (unlikely(le16_to_cpu(eh->eh_max) > max)) {
 478                 error_msg = "too large eh_max";
 479                 goto corrupted;
 480         }
 481         if (unlikely(le16_to_cpu(eh->eh_entries) > le16_to_cpu(eh->eh_max))) {
 482                 error_msg = "invalid eh_entries";
 483                 goto corrupted;
 484         }
 485         if (unlikely((eh->eh_entries == 0) && (depth > 0))) {
 486                 error_msg = "eh_entries is 0 but eh_depth is > 0";
 487                 goto corrupted;
 488         }
 489         if (!ext4_valid_extent_entries(inode, eh, lblk, &pblk, depth)) {
 490                 error_msg = "invalid extent entries";
 491                 goto corrupted;
 492         }
 493         if (unlikely(depth > 32)) {
 494                 error_msg = "too large eh_depth";
 495                 goto corrupted;
 496         }
 497         /* Verify checksum on non-root extent tree nodes */
 498         if (ext_depth(inode) != depth &&
 499             !ext4_extent_block_csum_verify(inode, eh)) {
 500                 error_msg = "extent tree corrupted";
 501                 err = -EFSBADCRC;
 502                 goto corrupted;
 503         }
 504         return 0;
 505
 506 corrupted:
 507         ext4_error_inode_err(inode, function, line, 0, -err,
 508                              "pblk %llu bad header/extent: %s - magic %x, "
 509                              "entries %u, max %u(%u), depth %u(%u)",
 510                              (unsigned long long) pblk, error_msg,
 511                              le16_to_cpu(eh->eh_magic),
 512                              le16_to_cpu(eh->eh_entries),
 513                              le16_to_cpu(eh->eh_max),
 514                              max, le16_to_cpu(eh->eh_depth), depth);
 515         return err;
 516 }
 517
 518 #define ext4_ext_check(inode, eh, depth, pblk)                  \
 519         __ext4_ext_check(__func__, __LINE__, (inode), (eh), (depth), (pblk), 0)
 520
 521 int ext4_ext_check_inode(struct inode *inode)
 522 {
 523         return ext4_ext_check(inode, ext_inode_hdr(inode), ext_depth(inode), 0);
 524 }
 525
 526 static void ext4_cache_extents(struct inode *inode,
 527                                struct ext4_extent_header *eh)
 528 {
 529         struct ext4_extent *ex = EXT_FIRST_EXTENT(eh);
 530         ext4_lblk_t prev = 0;
 531         int i;
 532
 533         for (i = le16_to_cpu(eh->eh_entries); i > 0; i--, ex++) {
 534                 unsigned int status = EXTENT_STATUS_WRITTEN;
 535                 ext4_lblk_t lblk = le32_to_cpu(ex->ee_block);
 536                 int len = ext4_ext_get_actual_len(ex);
 537
 538                 if (prev && (prev != lblk))
 539                         ext4_es_cache_extent(inode, prev, lblk - prev, ~0,
 540                                              EXTENT_STATUS_HOLE);
 541
 542                 if (ext4_ext_is_unwritten(ex))
 543                         status = EXTENT_STATUS_UNWRITTEN;
 544                 ext4_es_cache_extent(inode, lblk, len,
 545                                      ext4_ext_pblock(ex), status);
 546                 prev = lblk + len;
 547         }
 548 }
 549
 550 static struct buffer_head *
 551 __read_extent_tree_block(const char *function, unsigned int line,
 552                          struct inode *inode, struct ext4_extent_idx *idx,
 553                          int depth, int flags)
 554 {
 555         struct buffer_head              *bh;
 556         int                             err;
 557         gfp_t                           gfp_flags = __GFP_MOVABLE | GFP_NOFS;
 558         ext4_fsblk_t                    pblk;
 559
 560         if (flags & EXT4_EX_NOFAIL)
 561                 gfp_flags |= __GFP_NOFAIL;
 562
 563         pblk = ext4_idx_pblock(idx);
 564         bh = sb_getblk_gfp(inode->i_sb, pblk, gfp_flags);
 565         if (unlikely(!bh))
 566                 return ERR_PTR(-ENOMEM);
 567
 568         if (!bh_uptodate_or_lock(bh)) {
 569                 trace_ext4_ext_load_extent(inode, pblk, _RET_IP_);
 570                 err = ext4_read_bh(bh, 0, NULL, false);
 571                 if (err < 0)
 572                         goto errout;
 573         }
 574         if (buffer_verified(bh) && !(flags & EXT4_EX_FORCE_CACHE))
 575                 return bh;
 576         err = __ext4_ext_check(function, line, inode, ext_block_hdr(bh),
 577                                depth, pblk, le32_to_cpu(idx->ei_block));
 578         if (err)
 579                 goto errout;
 580         set_buffer_verified(bh);
 581         /*
 582          * If this is a leaf block, cache all of its entries
 583          */
 584         if (!(flags & EXT4_EX_NOCACHE) && depth == 0) {
 585                 struct ext4_extent_header *eh = ext_block_hdr(bh);
 586                 ext4_cache_extents(inode, eh);
 587         }
 588         return bh;
 589 errout:
 590         put_bh(bh);
 591         return ERR_PTR(err);
 592
 593 }
 594
 595 #define read_extent_tree_block(inode, idx, depth, flags)                \
 596         __read_extent_tree_block(__func__, __LINE__, (inode), (idx),    \
 597                                  (depth), (flags))
 598
 599 /*
 600  * This function is called to cache a file's extent information in the
 601  * extent status tree
 602  */
 603 int ext4_ext_precache(struct inode *inode)
 604 {
 605         struct ext4_inode_info *ei = EXT4_I(inode);
 606         struct ext4_ext_path *path = NULL;
 607         struct buffer_head *bh;
 608         int i = 0, depth, ret = 0;
 609
 610         if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
 611                 return 0;       /* not an extent-mapped inode */
 612
 613         ext4_check_map_extents_env(inode);
 614
 615         down_read(&ei->i_data_sem);
 616         depth = ext_depth(inode);
 617
 618         /* Don't cache anything if there are no external extent blocks */
 619         if (!depth) {
 620                 up_read(&ei->i_data_sem);
 621                 return ret;
 622         }
 623
 624         path = kcalloc(depth + 1, sizeof(struct ext4_ext_path),
 625                        GFP_NOFS);
 626         if (path == NULL) {
 627                 up_read(&ei->i_data_sem);
 628                 return -ENOMEM;
 629         }
 630
 631         path[0].p_hdr = ext_inode_hdr(inode);
 632         ret = ext4_ext_check(inode, path[0].p_hdr, depth, 0);
 633         if (ret)
 634                 goto out;
 635         path[0].p_idx = EXT_FIRST_INDEX(path[0].p_hdr);
 636         while (i >= 0) {
 637                 /*
 638                  * If this is a leaf block or we've reached the end of
 639                  * the index block, go up
 640                  */
 641                 if ((i == depth) ||
 642                     path[i].p_idx > EXT_LAST_INDEX(path[i].p_hdr)) {
 643                         ext4_ext_path_brelse(path + i);
 644                         i--;
 645                         continue;
 646                 }
 647                 bh = read_extent_tree_block(inode, path[i].p_idx++,
 648                                             depth - i - 1,
 649                                             EXT4_EX_FORCE_CACHE);
 650                 if (IS_ERR(bh)) {
 651                         ret = PTR_ERR(bh);
 652                         break;
 653                 }
 654                 i++;
 655                 path[i].p_bh = bh;
 656                 path[i].p_hdr = ext_block_hdr(bh);
 657                 path[i].p_idx = EXT_FIRST_INDEX(path[i].p_hdr);
 658         }
 659         ext4_set_inode_state(inode, EXT4_STATE_EXT_PRECACHED);
 660 out:
 661         up_read(&ei->i_data_sem);
 662         ext4_free_ext_path(path);
 663         return ret;
 664 }
 665
 666 #ifdef EXT_DEBUG
 667 static void ext4_ext_show_path(struct inode *inode, struct ext4_ext_path *path)
 668 {
 669         int k, l = path->p_depth;
 670
 671         ext_debug(inode, "path:");
 672         for (k = 0; k <= l; k++, path++) {
 673                 if (path->p_idx) {
 674                         ext_debug(inode, "  %d->%llu",
 675                                   le32_to_cpu(path->p_idx->ei_block),
 676                                   ext4_idx_pblock(path->p_idx));
 677                 } else if (path->p_ext) {
 678                         ext_debug(inode, "  %d:[%d]%d:%llu ",
 679                                   le32_to_cpu(path->p_ext->ee_block),
 680                                   ext4_ext_is_unwritten(path->p_ext),
 681                                   ext4_ext_get_actual_len(path->p_ext),
 682                                   ext4_ext_pblock(path->p_ext));
 683                 } else
 684                         ext_debug(inode, "  []");
 685         }
 686         ext_debug(inode, "\n");
 687 }
 688
 689 static void ext4_ext_show_leaf(struct inode *inode, struct ext4_ext_path *path)
 690 {
 691         int depth = ext_depth(inode);
 692         struct ext4_extent_header *eh;
 693         struct ext4_extent *ex;
 694         int i;
 695
 696         if (IS_ERR_OR_NULL(path))
 697                 return;
 698
 699         eh = path[depth].p_hdr;
 700         ex = EXT_FIRST_EXTENT(eh);
 701
 702         ext_debug(inode, "Displaying leaf extents\n");
 703
 704         for (i = 0; i < le16_to_cpu(eh->eh_entries); i++, ex++) {
 705                 ext_debug(inode, "%d:[%d]%d:%llu ", le32_to_cpu(ex->ee_block),
 706                           ext4_ext_is_unwritten(ex),
 707                           ext4_ext_get_actual_len(ex), ext4_ext_pblock(ex));
 708         }
 709         ext_debug(inode, "\n");
 710 }
 711
 712 static void ext4_ext_show_move(struct inode *inode, struct ext4_ext_path *path,
 713                         ext4_fsblk_t newblock, int level)
 714 {
 715         int depth = ext_depth(inode);
 716         struct ext4_extent *ex;
 717
 718         if (depth != level) {
 719                 struct ext4_extent_idx *idx;
 720                 idx = path[level].p_idx;
 721                 while (idx <= EXT_MAX_INDEX(path[level].p_hdr)) {
 722                         ext_debug(inode, "%d: move %d:%llu in new index %llu\n",
 723                                   level, le32_to_cpu(idx->ei_block),
 724                                   ext4_idx_pblock(idx), newblock);
 725                         idx++;
 726                 }
 727
 728                 return;
 729         }
 730
 731         ex = path[depth].p_ext;
 732         while (ex <= EXT_MAX_EXTENT(path[depth].p_hdr)) {
 733                 ext_debug(inode, "move %d:%llu:[%d]%d in new leaf %llu\n",
 734                                 le32_to_cpu(ex->ee_block),
 735                                 ext4_ext_pblock(ex),
 736                                 ext4_ext_is_unwritten(ex),
 737                                 ext4_ext_get_actual_len(ex),
 738                                 newblock);
 739                 ex++;
 740         }
 741 }
 742
 743 #else
 744 #define ext4_ext_show_path(inode, path)
 745 #define ext4_ext_show_leaf(inode, path)
 746 #define ext4_ext_show_move(inode, path, newblock, level)
 747 #endif
 748
 749 /*
 750  * ext4_ext_binsearch_idx:
 751  * binary search for the closest index of the given block
 752  * the header must be checked before calling this
 753  */
 754 static void
 755 ext4_ext_binsearch_idx(struct inode *inode,
 756                         struct ext4_ext_path *path, ext4_lblk_t block)
 757 {
 758         struct ext4_extent_header *eh = path->p_hdr;
 759         struct ext4_extent_idx *r, *l, *m;
 760
 761
 762         ext_debug(inode, "binsearch for %u(idx):  ", block);
 763
 764         l = EXT_FIRST_INDEX(eh) + 1;
 765         r = EXT_LAST_INDEX(eh);
 766         while (l <= r) {
 767                 m = l + (r - l) / 2;
 768                 ext_debug(inode, "%p(%u):%p(%u):%p(%u) ", l,
 769                           le32_to_cpu(l->ei_block), m, le32_to_cpu(m->ei_block),
 770                           r, le32_to_cpu(r->ei_block));
 771
 772                 if (block < le32_to_cpu(m->ei_block))
 773                         r = m - 1;
 774                 else
 775                         l = m + 1;
 776         }
 777
 778         path->p_idx = l - 1;
 779         ext_debug(inode, "  -> %u->%lld ", le32_to_cpu(path->p_idx->ei_block),
 780                   ext4_idx_pblock(path->p_idx));
 781
 782 #ifdef CHECK_BINSEARCH
 783         {
 784                 struct ext4_extent_idx *chix, *ix;
 785                 int k;
 786
 787                 chix = ix = EXT_FIRST_INDEX(eh);
 788                 for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ix++) {
 789                         if (k != 0 && le32_to_cpu(ix->ei_block) <=
 790                             le32_to_cpu(ix[-1].ei_block)) {
 791                                 printk(KERN_DEBUG "k=%d, ix=0x%p, "
 792                                        "first=0x%p\n", k,
 793                                        ix, EXT_FIRST_INDEX(eh));
 794                                 printk(KERN_DEBUG "%u <= %u\n",
 795                                        le32_to_cpu(ix->ei_block),
 796                                        le32_to_cpu(ix[-1].ei_block));
 797                         }
 798                         BUG_ON(k && le32_to_cpu(ix->ei_block)
 799                                            <= le32_to_cpu(ix[-1].ei_block));
 800                         if (block < le32_to_cpu(ix->ei_block))
 801                                 break;
 802                         chix = ix;
 803                 }
 804                 BUG_ON(chix != path->p_idx);
 805         }
 806 #endif
 807
 808 }
 809
 810 /*
 811  * ext4_ext_binsearch:
 812  * binary search for closest extent of the given block
 813  * the header must be checked before calling this
 814  */
 815 static void
 816 ext4_ext_binsearch(struct inode *inode,
 817                 struct ext4_ext_path *path, ext4_lblk_t block)
 818 {
 819         struct ext4_extent_header *eh = path->p_hdr;
 820         struct ext4_extent *r, *l, *m;
 821
 822         if (eh->eh_entries == 0) {
 823                 /*
 824                  * this leaf is empty:
 825                  * we get such a leaf in split/add case
 826                  */
 827                 return;
 828         }
 829
 830         ext_debug(inode, "binsearch for %u:  ", block);
 831
 832         l = EXT_FIRST_EXTENT(eh) + 1;
 833         r = EXT_LAST_EXTENT(eh);
 834
 835         while (l <= r) {
 836                 m = l + (r - l) / 2;
 837                 ext_debug(inode, "%p(%u):%p(%u):%p(%u) ", l,
 838                           le32_to_cpu(l->ee_block), m, le32_to_cpu(m->ee_block),
 839                           r, le32_to_cpu(r->ee_block));
 840
 841                 if (block < le32_to_cpu(m->ee_block))
 842                         r = m - 1;
 843                 else
 844                         l = m + 1;
 845         }
 846
 847         path->p_ext = l - 1;
 848         ext_debug(inode, "  -> %d:%llu:[%d]%d ",
 849                         le32_to_cpu(path->p_ext->ee_block),
 850                         ext4_ext_pblock(path->p_ext),
 851                         ext4_ext_is_unwritten(path->p_ext),
 852                         ext4_ext_get_actual_len(path->p_ext));
 853
 854 #ifdef CHECK_BINSEARCH
 855         {
 856                 struct ext4_extent *chex, *ex;
 857                 int k;
 858
 859                 chex = ex = EXT_FIRST_EXTENT(eh);
 860                 for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ex++) {
 861                         BUG_ON(k && le32_to_cpu(ex->ee_block)
 862                                           <= le32_to_cpu(ex[-1].ee_block));
 863                         if (block < le32_to_cpu(ex->ee_block))
 864                                 break;
 865                         chex = ex;
 866                 }
 867                 BUG_ON(chex != path->p_ext);
 868         }
 869 #endif
 870
 871 }
 872
 873 void ext4_ext_tree_init(handle_t *handle, struct inode *inode)
 874 {
 875         struct ext4_extent_header *eh;
 876
 877         eh = ext_inode_hdr(inode);
 878         eh->eh_depth = 0;
 879         eh->eh_entries = 0;
 880         eh->eh_magic = EXT4_EXT_MAGIC;
 881         eh->eh_max = cpu_to_le16(ext4_ext_space_root(inode, 0));
 882         eh->eh_generation = 0;
 883         ext4_mark_inode_dirty(handle, inode);
 884 }
 885
 886 struct ext4_ext_path *
 887 ext4_find_extent(struct inode *inode, ext4_lblk_t block,
 888                  struct ext4_ext_path *path, int flags)
 889 {
 890         struct ext4_extent_header *eh;
 891         struct buffer_head *bh;
 892         short int depth, i, ppos = 0;
 893         int ret;
 894         gfp_t gfp_flags = GFP_NOFS;
 895
 896         if (flags & EXT4_EX_NOFAIL)
 897                 gfp_flags |= __GFP_NOFAIL;
 898
 899         eh = ext_inode_hdr(inode);
 900         depth = ext_depth(inode);
 901         if (depth < 0 || depth > EXT4_MAX_EXTENT_DEPTH) {
 902                 EXT4_ERROR_INODE(inode, "inode has invalid extent depth: %d",
 903                                  depth);
 904                 ret = -EFSCORRUPTED;
 905                 goto err;
 906         }
 907
 908         if (path) {
 909                 ext4_ext_drop_refs(path);
 910                 if (depth > path[0].p_maxdepth) {
 911                         kfree(path);
 912                         path = NULL;
 913                 }
 914         }
 915         if (!path) {
 916                 /* account possible depth increase */
 917                 path = kcalloc(depth + 2, sizeof(struct ext4_ext_path),
 918                                 gfp_flags);
 919                 if (unlikely(!path))
 920                         return ERR_PTR(-ENOMEM);
 921                 path[0].p_maxdepth = depth + 1;
 922         }
 923         path[0].p_hdr = eh;
 924         path[0].p_bh = NULL;
 925
 926         i = depth;
 927         if (!(flags & EXT4_EX_NOCACHE) && depth == 0)
 928                 ext4_cache_extents(inode, eh);
 929         /* walk through the tree */
 930         while (i) {
 931                 ext_debug(inode, "depth %d: num %d, max %d\n",
 932                           ppos, le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
 933
 934                 ext4_ext_binsearch_idx(inode, path + ppos, block);
 935                 path[ppos].p_block = ext4_idx_pblock(path[ppos].p_idx);
 936                 path[ppos].p_depth = i;
 937                 path[ppos].p_ext = NULL;
 938
 939                 bh = read_extent_tree_block(inode, path[ppos].p_idx, --i, flags);
 940                 if (IS_ERR(bh)) {
 941                         ret = PTR_ERR(bh);
 942                         goto err;
 943                 }
 944
 945                 eh = ext_block_hdr(bh);
 946                 ppos++;
 947                 path[ppos].p_bh = bh;
 948                 path[ppos].p_hdr = eh;
 949         }
 950
 951         path[ppos].p_depth = i;
 952         path[ppos].p_ext = NULL;
 953         path[ppos].p_idx = NULL;
 954
 955         /* find extent */
 956         ext4_ext_binsearch(inode, path + ppos, block);
 957         /* if not an empty leaf */
 958         if (path[ppos].p_ext)
 959                 path[ppos].p_block = ext4_ext_pblock(path[ppos].p_ext);
 960
 961         ext4_ext_show_path(inode, path);
 962
 963         return path;
 964
 965 err:
 966         ext4_free_ext_path(path);
 967         return ERR_PTR(ret);
 968 }
 969
 970 /*
 971  * ext4_ext_insert_index:
 972  * insert new index [@logical;@ptr] into the block at @curp;
 973  * check where to insert: before @curp or after @curp
 974  */
 975 static int ext4_ext_insert_index(handle_t *handle, struct inode *inode,
 976                                  struct ext4_ext_path *curp,
 977                                  int logical, ext4_fsblk_t ptr)
 978 {
 979         struct ext4_extent_idx *ix;
 980         int len, err;
 981
 982         err = ext4_ext_get_access(handle, inode, curp);
 983         if (err)
 984                 return err;
 985
 986         if (unlikely(logical == le32_to_cpu(curp->p_idx->ei_block))) {
 987                 EXT4_ERROR_INODE(inode,
 988                                  "logical %d == ei_block %d!",
 989                                  logical, le32_to_cpu(curp->p_idx->ei_block));
 990                 return -EFSCORRUPTED;
 991         }
 992
 993         if (unlikely(le16_to_cpu(curp->p_hdr->eh_entries)
 994                              >= le16_to_cpu(curp->p_hdr->eh_max))) {
 995                 EXT4_ERROR_INODE(inode,
 996                                  "eh_entries %d >= eh_max %d!",
 997                                  le16_to_cpu(curp->p_hdr->eh_entries),
 998                                  le16_to_cpu(curp->p_hdr->eh_max));
 999                 return -EFSCORRUPTED;
1000         }
1001
1002         if (logical > le32_to_cpu(curp->p_idx->ei_block)) {
1003                 /* insert after */
1004                 ext_debug(inode, "insert new index %d after: %llu\n",
1005                           logical, ptr);
1006                 ix = curp->p_idx + 1;
1007         } else {
1008                 /* insert before */
1009                 ext_debug(inode, "insert new index %d before: %llu\n",
1010                           logical, ptr);
1011                 ix = curp->p_idx;
1012         }
1013
1014         if (unlikely(ix > EXT_MAX_INDEX(curp->p_hdr))) {
1015                 EXT4_ERROR_INODE(inode, "ix > EXT_MAX_INDEX!");
1016                 return -EFSCORRUPTED;
1017         }
1018
1019         len = EXT_LAST_INDEX(curp->p_hdr) - ix + 1;
1020         BUG_ON(len < 0);
1021         if (len > 0) {
1022                 ext_debug(inode, "insert new index %d: "
1023                                 "move %d indices from 0x%p to 0x%p\n",
1024                                 logical, len, ix, ix + 1);
1025                 memmove(ix + 1, ix, len * sizeof(struct ext4_extent_idx));
1026         }
1027
1028         ix->ei_block = cpu_to_le32(logical);
1029         ext4_idx_store_pblock(ix, ptr);
1030         le16_add_cpu(&curp->p_hdr->eh_entries, 1);
1031
1032         if (unlikely(ix > EXT_LAST_INDEX(curp->p_hdr))) {
1033                 EXT4_ERROR_INODE(inode, "ix > EXT_LAST_INDEX!");
1034                 return -EFSCORRUPTED;
1035         }
1036
1037         err = ext4_ext_dirty(handle, inode, curp);
1038         ext4_std_error(inode->i_sb, err);
1039
1040         return err;
1041 }
1042
1043 /*
1044  * ext4_ext_split:
1045  * inserts new subtree into the path, using free index entry
1046  * at depth @at:
1047  * - allocates all needed blocks (new leaf and all intermediate index blocks)
1048  * - makes decision where to split
1049  * - moves remaining extents and index entries (right to the split point)
1050  *   into the newly allocated blocks
1051  * - initializes subtree
1052  */
1053 static int ext4_ext_split(handle_t *handle, struct inode *inode,
1054                           unsigned int flags,
1055                           struct ext4_ext_path *path,
1056                           struct ext4_extent *newext, int at)
1057 {
1058         struct buffer_head *bh = NULL;
1059         int depth = ext_depth(inode);
1060         struct ext4_extent_header *neh;
1061         struct ext4_extent_idx *fidx;
1062         int i = at, k, m, a;
1063         ext4_fsblk_t newblock, oldblock;
1064         __le32 border;
1065         ext4_fsblk_t *ablocks = NULL; /* array of allocated blocks */
1066         gfp_t gfp_flags = GFP_NOFS;
1067         int err = 0;
1068         size_t ext_size = 0;
1069
1070         if (flags & EXT4_EX_NOFAIL)
1071                 gfp_flags |= __GFP_NOFAIL;
1072
1073         /* make decision: where to split? */
1074         /* FIXME: now decision is simplest: at current extent */
1075
1076         /* if current leaf will be split, then we should use
1077          * border from split point */
1078         if (unlikely(path[depth].p_ext > EXT_MAX_EXTENT(path[depth].p_hdr))) {
1079                 EXT4_ERROR_INODE(inode, "p_ext > EXT_MAX_EXTENT!");
1080                 return -EFSCORRUPTED;
1081         }
1082         if (path[depth].p_ext != EXT_MAX_EXTENT(path[depth].p_hdr)) {
1083                 border = path[depth].p_ext[1].ee_block;
1084                 ext_debug(inode, "leaf will be split."
1085                                 " next leaf starts at %d\n",
1086                                   le32_to_cpu(border));
1087         } else {
1088                 border = newext->ee_block;
1089                 ext_debug(inode, "leaf will be added."
1090                                 " next leaf starts at %d\n",
1091                                 le32_to_cpu(border));
1092         }
1093
1094         /*
1095          * If error occurs, then we break processing
1096          * and mark filesystem read-only. index won't
1097          * be inserted and tree will be in consistent
1098          * state. Next mount will repair buffers too.
1099          */
1100
1101         /*
1102          * Get array to track all allocated blocks.
1103          * We need this to handle errors and free blocks
1104          * upon them.
1105          */
1106         ablocks = kcalloc(depth, sizeof(ext4_fsblk_t), gfp_flags);
1107         if (!ablocks)
1108                 return -ENOMEM;
1109
1110         /* allocate all needed blocks */
1111         ext_debug(inode, "allocate %d blocks for indexes/leaf\n", depth - at);
1112         for (a = 0; a < depth - at; a++) {
1113                 newblock = ext4_ext_new_meta_block(handle, inode, path,
1114                                                    newext, &err, flags);
1115                 if (newblock == 0)
1116                         goto cleanup;
1117                 ablocks[a] = newblock;
1118         }
1119
1120         /* initialize new leaf */
1121         newblock = ablocks[--a];
1122         if (unlikely(newblock == 0)) {
1123                 EXT4_ERROR_INODE(inode, "newblock == 0!");
1124                 err = -EFSCORRUPTED;
1125                 goto cleanup;
1126         }
1127         bh = sb_getblk_gfp(inode->i_sb, newblock, __GFP_MOVABLE | GFP_NOFS);
1128         if (unlikely(!bh)) {
1129                 err = -ENOMEM;
1130                 goto cleanup;
1131         }
1132         lock_buffer(bh);
1133
1134         err = ext4_journal_get_create_access(handle, inode->i_sb, bh,
1135                                              EXT4_JTR_NONE);
1136         if (err)
1137                 goto cleanup;
1138
1139         neh = ext_block_hdr(bh);
1140         neh->eh_entries = 0;
1141         neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0));
1142         neh->eh_magic = EXT4_EXT_MAGIC;
1143         neh->eh_depth = 0;
1144         neh->eh_generation = 0;
1145
1146         /* move remainder of path[depth] to the new leaf */
1147         if (unlikely(path[depth].p_hdr->eh_entries !=
1148                      path[depth].p_hdr->eh_max)) {
1149                 EXT4_ERROR_INODE(inode, "eh_entries %d != eh_max %d!",
1150                                  path[depth].p_hdr->eh_entries,
1151                                  path[depth].p_hdr->eh_max);
1152                 err = -EFSCORRUPTED;
1153                 goto cleanup;
1154         }
1155         /* start copy from next extent */
1156         m = EXT_MAX_EXTENT(path[depth].p_hdr) - path[depth].p_ext++;
1157         ext4_ext_show_move(inode, path, newblock, depth);
1158         if (m) {
1159                 struct ext4_extent *ex;
1160                 ex = EXT_FIRST_EXTENT(neh);
1161                 memmove(ex, path[depth].p_ext, sizeof(struct ext4_extent) * m);
1162                 le16_add_cpu(&neh->eh_entries, m);
1163         }
1164
1165         /* zero out unused area in the extent block */
1166         ext_size = sizeof(struct ext4_extent_header) +
1167                 sizeof(struct ext4_extent) * le16_to_cpu(neh->eh_entries);
1168         memset(bh->b_data + ext_size, 0, inode->i_sb->s_blocksize - ext_size);
1169         ext4_extent_block_csum_set(inode, neh);
1170         set_buffer_uptodate(bh);
1171         unlock_buffer(bh);
1172
1173         err = ext4_handle_dirty_metadata(handle, inode, bh);
1174         if (err)
1175                 goto cleanup;
1176         brelse(bh);
1177         bh = NULL;
1178
1179         /* correct old leaf */
1180         if (m) {
1181                 err = ext4_ext_get_access(handle, inode, path + depth);
1182                 if (err)
1183                         goto cleanup;
1184                 le16_add_cpu(&path[depth].p_hdr->eh_entries, -m);
1185                 err = ext4_ext_dirty(handle, inode, path + depth);
1186                 if (err)
1187                         goto cleanup;
1188
1189         }
1190
1191         /* create intermediate indexes */
1192         k = depth - at - 1;
1193         if (unlikely(k < 0)) {
1194                 EXT4_ERROR_INODE(inode, "k %d < 0!", k);
1195                 err = -EFSCORRUPTED;
1196                 goto cleanup;
1197         }
1198         if (k)
1199                 ext_debug(inode, "create %d intermediate indices\n", k);
1200         /* insert new index into current index block */
1201         /* current depth stored in i var */
1202         i = depth - 1;
1203         while (k--) {
1204                 oldblock = newblock;
1205                 newblock = ablocks[--a];
1206                 bh = sb_getblk(inode->i_sb, newblock);
1207                 if (unlikely(!bh)) {
1208                         err = -ENOMEM;
1209                         goto cleanup;
1210                 }
1211                 lock_buffer(bh);
1212
1213                 err = ext4_journal_get_create_access(handle, inode->i_sb, bh,
1214                                                      EXT4_JTR_NONE);
1215                 if (err)
1216                         goto cleanup;
1217
1218                 neh = ext_block_hdr(bh);
1219                 neh->eh_entries = cpu_to_le16(1);
1220                 neh->eh_magic = EXT4_EXT_MAGIC;
1221                 neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0));
1222                 neh->eh_depth = cpu_to_le16(depth - i);
1223                 neh->eh_generation = 0;
1224                 fidx = EXT_FIRST_INDEX(neh);
1225                 fidx->ei_block = border;
1226                 ext4_idx_store_pblock(fidx, oldblock);
1227
1228                 ext_debug(inode, "int.index at %d (block %llu): %u -> %llu\n",
1229                                 i, newblock, le32_to_cpu(border), oldblock);
1230
1231                 /* move remainder of path[i] to the new index block */
1232                 if (unlikely(EXT_MAX_INDEX(path[i].p_hdr) !=
1233                                         EXT_LAST_INDEX(path[i].p_hdr))) {
1234                         EXT4_ERROR_INODE(inode,
1235                                          "EXT_MAX_INDEX != EXT_LAST_INDEX ee_block %d!",
1236                                          le32_to_cpu(path[i].p_ext->ee_block));
1237                         err = -EFSCORRUPTED;
1238                         goto cleanup;
1239                 }
1240                 /* start copy indexes */
1241                 m = EXT_MAX_INDEX(path[i].p_hdr) - path[i].p_idx++;
1242                 ext_debug(inode, "cur 0x%p, last 0x%p\n", path[i].p_idx,
1243                                 EXT_MAX_INDEX(path[i].p_hdr));
1244                 ext4_ext_show_move(inode, path, newblock, i);
1245                 if (m) {
1246                         memmove(++fidx, path[i].p_idx,
1247                                 sizeof(struct ext4_extent_idx) * m);
1248                         le16_add_cpu(&neh->eh_entries, m);
1249                 }
1250                 /* zero out unused area in the extent block */
1251                 ext_size = sizeof(struct ext4_extent_header) +
1252                    (sizeof(struct ext4_extent) * le16_to_cpu(neh->eh_entries));
1253                 memset(bh->b_data + ext_size, 0,
1254                         inode->i_sb->s_blocksize - ext_size);
1255                 ext4_extent_block_csum_set(inode, neh);
1256                 set_buffer_uptodate(bh);
1257                 unlock_buffer(bh);
1258
1259                 err = ext4_handle_dirty_metadata(handle, inode, bh);
1260                 if (err)
1261                         goto cleanup;
1262                 brelse(bh);
1263                 bh = NULL;
1264
1265                 /* correct old index */
1266                 if (m) {
1267                         err = ext4_ext_get_access(handle, inode, path + i);
1268                         if (err)
1269                                 goto cleanup;
1270                         le16_add_cpu(&path[i].p_hdr->eh_entries, -m);
1271                         err = ext4_ext_dirty(handle, inode, path + i);
1272                         if (err)
1273                                 goto cleanup;
1274                 }
1275
1276                 i--;
1277         }
1278
1279         /* insert new index */
1280         err = ext4_ext_insert_index(handle, inode, path + at,
1281                                     le32_to_cpu(border), newblock);
1282
1283 cleanup:
1284         if (bh) {
1285                 if (buffer_locked(bh))
1286                         unlock_buffer(bh);
1287                 brelse(bh);
1288         }
1289
1290         if (err) {
1291                 /* free all allocated blocks in error case */
1292                 for (i = 0; i < depth; i++) {
1293                         if (!ablocks[i])
1294                                 continue;
1295                         ext4_free_blocks(handle, inode, NULL, ablocks[i], 1,
1296                                          EXT4_FREE_BLOCKS_METADATA);
1297                 }
1298         }
1299         kfree(ablocks);
1300
1301         return err;
1302 }
1303
1304 /*
1305  * ext4_ext_grow_indepth:
1306  * implements tree growing procedure:
1307  * - allocates new block
1308  * - moves top-level data (index block or leaf) into the new block
1309  * - initializes new top-level, creating index that points to the
1310  *   just created block
1311  */
1312 static int ext4_ext_grow_indepth(handle_t *handle, struct inode *inode,
1313                                  unsigned int flags)
1314 {
1315         struct ext4_extent_header *neh;
1316         struct buffer_head *bh;
1317         ext4_fsblk_t newblock, goal = 0;
1318         struct ext4_super_block *es = EXT4_SB(inode->i_sb)->s_es;
1319         int err = 0;
1320         size_t ext_size = 0;
1321
1322         /* Try to prepend new index to old one */
1323         if (ext_depth(inode))
1324                 goal = ext4_idx_pblock(EXT_FIRST_INDEX(ext_inode_hdr(inode)));
1325         if (goal > le32_to_cpu(es->s_first_data_block)) {
1326                 flags |= EXT4_MB_HINT_TRY_GOAL;
1327                 goal--;
1328         } else
1329                 goal = ext4_inode_to_goal_block(inode);
1330         newblock = ext4_new_meta_blocks(handle, inode, goal, flags,
1331                                         NULL, &err);
1332         if (newblock == 0)
1333                 return err;
1334
1335         bh = sb_getblk_gfp(inode->i_sb, newblock, __GFP_MOVABLE | GFP_NOFS);
1336         if (unlikely(!bh))
1337                 return -ENOMEM;
1338         lock_buffer(bh);
1339
1340         err = ext4_journal_get_create_access(handle, inode->i_sb, bh,
1341                                              EXT4_JTR_NONE);
1342         if (err) {
1343                 unlock_buffer(bh);
1344                 goto out;
1345         }
1346
1347         ext_size = sizeof(EXT4_I(inode)->i_data);
1348         /* move top-level index/leaf into new block */
1349         memmove(bh->b_data, EXT4_I(inode)->i_data, ext_size);
1350         /* zero out unused area in the extent block */
1351         memset(bh->b_data + ext_size, 0, inode->i_sb->s_blocksize - ext_size);
1352
1353         /* set size of new block */
1354         neh = ext_block_hdr(bh);
1355         /* old root could have indexes or leaves
1356          * so calculate e_max right way */
1357         if (ext_depth(inode))
1358                 neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0));
1359         else
1360                 neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0));
1361         neh->eh_magic = EXT4_EXT_MAGIC;
1362         ext4_extent_block_csum_set(inode, neh);
1363         set_buffer_uptodate(bh);
1364         set_buffer_verified(bh);
1365         unlock_buffer(bh);
1366
1367         err = ext4_handle_dirty_metadata(handle, inode, bh);
1368         if (err)
1369                 goto out;
1370
1371         /* Update top-level index: num,max,pointer */
1372         neh = ext_inode_hdr(inode);
1373         neh->eh_entries = cpu_to_le16(1);
1374         ext4_idx_store_pblock(EXT_FIRST_INDEX(neh), newblock);
1375         if (neh->eh_depth == 0) {
1376                 /* Root extent block becomes index block */
1377                 neh->eh_max = cpu_to_le16(ext4_ext_space_root_idx(inode, 0));
1378                 EXT_FIRST_INDEX(neh)->ei_block =
1379                         EXT_FIRST_EXTENT(neh)->ee_block;
1380         }
1381         ext_debug(inode, "new root: num %d(%d), lblock %d, ptr %llu\n",
1382                   le16_to_cpu(neh->eh_entries), le16_to_cpu(neh->eh_max),
1383                   le32_to_cpu(EXT_FIRST_INDEX(neh)->ei_block),
1384                   ext4_idx_pblock(EXT_FIRST_INDEX(neh)));
1385
1386         le16_add_cpu(&neh->eh_depth, 1);
1387         err = ext4_mark_inode_dirty(handle, inode);
1388 out:
1389         brelse(bh);
1390
1391         return err;
1392 }
1393
1394 /*
1395  * ext4_ext_create_new_leaf:
1396  * finds empty index and adds new leaf.
1397  * if no free index is found, then it requests in-depth growing.
1398  */
1399 static struct ext4_ext_path *
1400 ext4_ext_create_new_leaf(handle_t *handle, struct inode *inode,
1401                          unsigned int mb_flags, unsigned int gb_flags,
1402                          struct ext4_ext_path *path,
1403                          struct ext4_extent *newext)
1404 {
1405         struct ext4_ext_path *curp;
1406         int depth, i, err = 0;
1407         ext4_lblk_t ee_block = le32_to_cpu(newext->ee_block);
1408
1409 repeat:
1410         i = depth = ext_depth(inode);
1411
1412         /* walk up to the tree and look for free index entry */
1413         curp = path + depth;
1414         while (i > 0 && !EXT_HAS_FREE_INDEX(curp)) {
1415                 i--;
1416                 curp--;
1417         }
1418
1419         /* we use already allocated block for index block,
1420          * so subsequent data blocks should be contiguous */
1421         if (EXT_HAS_FREE_INDEX(curp)) {
1422                 /* if we found index with free entry, then use that
1423                  * entry: create all needed subtree and add new leaf */
1424                 err = ext4_ext_split(handle, inode, mb_flags, path, newext, i);
1425                 if (err)
1426                         goto errout;
1427
1428                 /* refill path */
1429                 path = ext4_find_extent(inode, ee_block, path, gb_flags);
1430                 return path;
1431         }
1432
1433         /* tree is full, time to grow in depth */
1434         err = ext4_ext_grow_indepth(handle, inode, mb_flags);
1435         if (err)
1436                 goto errout;
1437
1438         /* refill path */
1439         path = ext4_find_extent(inode, ee_block, path, gb_flags);
1440         if (IS_ERR(path))
1441                 return path;
1442
1443         /*
1444          * only first (depth 0 -> 1) produces free space;
1445          * in all other cases we have to split the grown tree
1446          */
1447         depth = ext_depth(inode);
1448         if (path[depth].p_hdr->eh_entries == path[depth].p_hdr->eh_max) {
1449                 /* now we need to split */
1450                 goto repeat;
1451         }
1452
1453         return path;
1454
1455 errout:
1456         ext4_free_ext_path(path);
1457         return ERR_PTR(err);
1458 }
1459
1460 /*
1461  * search the closest allocated block to the left for *logical
1462  * and returns it at @logical + it's physical address at @phys
1463  * if *logical is the smallest allocated block, the function
1464  * returns 0 at @phys
1465  * return value contains 0 (success) or error code
1466  */
1467 static int ext4_ext_search_left(struct inode *inode,
1468                                 struct ext4_ext_path *path,
1469                                 ext4_lblk_t *logical, ext4_fsblk_t *phys)
1470 {
1471         struct ext4_extent_idx *ix;
1472         struct ext4_extent *ex;
1473         int depth, ee_len;
1474
1475         if (unlikely(path == NULL)) {
1476                 EXT4_ERROR_INODE(inode, "path == NULL *logical %d!", *logical);
1477                 return -EFSCORRUPTED;
1478         }
1479         depth = path->p_depth;
1480         *phys = 0;
1481
1482         if (depth == 0 && path->p_ext == NULL)
1483                 return 0;
1484
1485         /* usually extent in the path covers blocks smaller
1486          * then *logical, but it can be that extent is the
1487          * first one in the file */
1488
1489         ex = path[depth].p_ext;
1490         ee_len = ext4_ext_get_actual_len(ex);
1491         if (*logical < le32_to_cpu(ex->ee_block)) {
1492                 if (unlikely(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex)) {
1493                         EXT4_ERROR_INODE(inode,
1494                                          "EXT_FIRST_EXTENT != ex *logical %d ee_block %d!",
1495                                          *logical, le32_to_cpu(ex->ee_block));
1496                         return -EFSCORRUPTED;
1497                 }
1498                 while (--depth >= 0) {
1499                         ix = path[depth].p_idx;
1500                         if (unlikely(ix != EXT_FIRST_INDEX(path[depth].p_hdr))) {
1501                                 EXT4_ERROR_INODE(inode,
1502                                   "ix (%d) != EXT_FIRST_INDEX (%d) (depth %d)!",
1503                                   ix != NULL ? le32_to_cpu(ix->ei_block) : 0,
1504                                   le32_to_cpu(EXT_FIRST_INDEX(path[depth].p_hdr)->ei_block),
1505                                   depth);
1506                                 return -EFSCORRUPTED;
1507                         }
1508                 }
1509                 return 0;
1510         }
1511
1512         if (unlikely(*logical < (le32_to_cpu(ex->ee_block) + ee_len))) {
1513                 EXT4_ERROR_INODE(inode,
1514                                  "logical %d < ee_block %d + ee_len %d!",
1515                                  *logical, le32_to_cpu(ex->ee_block), ee_len);
1516                 return -EFSCORRUPTED;
1517         }
1518
1519         *logical = le32_to_cpu(ex->ee_block) + ee_len - 1;
1520         *phys = ext4_ext_pblock(ex) + ee_len - 1;
1521         return 0;
1522 }
1523
1524 /*
1525  * Search the closest allocated block to the right for *logical
1526  * and returns it at @logical + it's physical address at @phys.
1527  * If not exists, return 0 and @phys is set to 0. We will return
1528  * 1 which means we found an allocated block and ret_ex is valid.
1529  * Or return a (< 0) error code.
1530  */
1531 static int ext4_ext_search_right(struct inode *inode,
1532                                  struct ext4_ext_path *path,
1533                                  ext4_lblk_t *logical, ext4_fsblk_t *phys,
1534                                  struct ext4_extent *ret_ex, int flags)
1535 {
1536         struct buffer_head *bh = NULL;
1537         struct ext4_extent_header *eh;
1538         struct ext4_extent_idx *ix;
1539         struct ext4_extent *ex;
1540         int depth;      /* Note, NOT eh_depth; depth from top of tree */
1541         int ee_len;
1542
1543         if (unlikely(path == NULL)) {
1544                 EXT4_ERROR_INODE(inode, "path == NULL *logical %d!", *logical);
1545                 return -EFSCORRUPTED;
1546         }
1547         depth = path->p_depth;
1548         *phys = 0;
1549
1550         if (depth == 0 && path->p_ext == NULL)
1551                 return 0;
1552
1553         /* usually extent in the path covers blocks smaller
1554          * then *logical, but it can be that extent is the
1555          * first one in the file */
1556
1557         ex = path[depth].p_ext;
1558         ee_len = ext4_ext_get_actual_len(ex);
1559         if (*logical < le32_to_cpu(ex->ee_block)) {
1560                 if (unlikely(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex)) {
1561                         EXT4_ERROR_INODE(inode,
1562                                          "first_extent(path[%d].p_hdr) != ex",
1563                                          depth);
1564                         return -EFSCORRUPTED;
1565                 }
1566                 while (--depth >= 0) {
1567                         ix = path[depth].p_idx;
1568                         if (unlikely(ix != EXT_FIRST_INDEX(path[depth].p_hdr))) {
1569                                 EXT4_ERROR_INODE(inode,
1570                                                  "ix != EXT_FIRST_INDEX *logical %d!",
1571                                                  *logical);
1572                                 return -EFSCORRUPTED;
1573                         }
1574                 }
1575                 goto found_extent;
1576         }
1577
1578         if (unlikely(*logical < (le32_to_cpu(ex->ee_block) + ee_len))) {
1579                 EXT4_ERROR_INODE(inode,
1580                                  "logical %d < ee_block %d + ee_len %d!",
1581                                  *logical, le32_to_cpu(ex->ee_block), ee_len);
1582                 return -EFSCORRUPTED;
1583         }
1584
1585         if (ex != EXT_LAST_EXTENT(path[depth].p_hdr)) {
1586                 /* next allocated block in this leaf */
1587                 ex++;
1588                 goto found_extent;
1589         }
1590
1591         /* go up and search for index to the right */
1592         while (--depth >= 0) {
1593                 ix = path[depth].p_idx;
1594                 if (ix != EXT_LAST_INDEX(path[depth].p_hdr))
1595                         goto got_index;
1596         }
1597
1598         /* we've gone up to the root and found no index to the right */
1599         return 0;
1600
1601 got_index:
1602         /* we've found index to the right, let's
1603          * follow it and find the closest allocated
1604          * block to the right */
1605         ix++;
1606         while (++depth < path->p_depth) {
1607                 /* subtract from p_depth to get proper eh_depth */
1608                 bh = read_extent_tree_block(inode, ix, path->p_depth - depth,
1609                                             flags);
1610                 if (IS_ERR(bh))
1611                         return PTR_ERR(bh);
1612                 eh = ext_block_hdr(bh);
1613                 ix = EXT_FIRST_INDEX(eh);
1614                 put_bh(bh);
1615         }
1616
1617         bh = read_extent_tree_block(inode, ix, path->p_depth - depth, flags);
1618         if (IS_ERR(bh))
1619                 return PTR_ERR(bh);
1620         eh = ext_block_hdr(bh);
1621         ex = EXT_FIRST_EXTENT(eh);
1622 found_extent:
1623         *logical = le32_to_cpu(ex->ee_block);
1624         *phys = ext4_ext_pblock(ex);
1625         if (ret_ex)
1626                 *ret_ex = *ex;
1627         if (bh)
1628                 put_bh(bh);
1629         return 1;
1630 }
1631
1632 /*
1633  * ext4_ext_next_allocated_block:
1634  * returns allocated block in subsequent extent or EXT_MAX_BLOCKS.
1635  * NOTE: it considers block number from index entry as
1636  * allocated block. Thus, index entries have to be consistent
1637  * with leaves.
1638  */
1639 ext4_lblk_t
1640 ext4_ext_next_allocated_block(struct ext4_ext_path *path)
1641 {
1642         int depth;
1643
1644         BUG_ON(path == NULL);
1645         depth = path->p_depth;
1646
1647         if (depth == 0 && path->p_ext == NULL)
1648                 return EXT_MAX_BLOCKS;
1649
1650         while (depth >= 0) {
1651                 struct ext4_ext_path *p = &path[depth];
1652
1653                 if (depth == path->p_depth) {
1654                         /* leaf */
1655                         if (p->p_ext && p->p_ext != EXT_LAST_EXTENT(p->p_hdr))
1656                                 return le32_to_cpu(p->p_ext[1].ee_block);
1657                 } else {
1658                         /* index */
1659                         if (p->p_idx != EXT_LAST_INDEX(p->p_hdr))
1660                                 return le32_to_cpu(p->p_idx[1].ei_block);
1661                 }
1662                 depth--;
1663         }
1664
1665         return EXT_MAX_BLOCKS;
1666 }
1667
1668 /*
1669  * ext4_ext_next_leaf_block:
1670  * returns first allocated block from next leaf or EXT_MAX_BLOCKS
1671  */
1672 static ext4_lblk_t ext4_ext_next_leaf_block(struct ext4_ext_path *path)
1673 {
1674         int depth;
1675
1676         BUG_ON(path == NULL);
1677         depth = path->p_depth;
1678
1679         /* zero-tree has no leaf blocks at all */
1680         if (depth == 0)
1681                 return EXT_MAX_BLOCKS;
1682
1683         /* go to index block */
1684         depth--;
1685
1686         while (depth >= 0) {
1687                 if (path[depth].p_idx !=
1688                                 EXT_LAST_INDEX(path[depth].p_hdr))
1689                         return (ext4_lblk_t)
1690                                 le32_to_cpu(path[depth].p_idx[1].ei_block);
1691                 depth--;
1692         }
1693
1694         return EXT_MAX_BLOCKS;
1695 }
1696
1697 /*
1698  * ext4_ext_correct_indexes:
1699  * if leaf gets modified and modified extent is first in the leaf,
1700  * then we have to correct all indexes above.
1701  * TODO: do we need to correct tree in all cases?
1702  */
1703 static int ext4_ext_correct_indexes(handle_t *handle, struct inode *inode,
1704                                 struct ext4_ext_path *path)
1705 {
1706         struct ext4_extent_header *eh;
1707         int depth = ext_depth(inode);
1708         struct ext4_extent *ex;
1709         __le32 border;
1710         int k, err = 0;
1711
1712         eh = path[depth].p_hdr;
1713         ex = path[depth].p_ext;
1714
1715         if (unlikely(ex == NULL || eh == NULL)) {
1716                 EXT4_ERROR_INODE(inode,
1717                                  "ex %p == NULL or eh %p == NULL", ex, eh);
1718                 return -EFSCORRUPTED;
1719         }
1720
1721         if (depth == 0) {
1722                 /* there is no tree at all */
1723                 return 0;
1724         }
1725
1726         if (ex != EXT_FIRST_EXTENT(eh)) {
1727                 /* we correct tree if first leaf got modified only */
1728                 return 0;
1729         }
1730
1731         /*
1732          * TODO: we need correction if border is smaller than current one
1733          */
1734         k = depth - 1;
1735         border = path[depth].p_ext->ee_block;
1736         err = ext4_ext_get_access(handle, inode, path + k);
1737         if (err)
1738                 return err;
1739         path[k].p_idx->ei_block = border;
1740         err = ext4_ext_dirty(handle, inode, path + k);
1741         if (err)
1742                 return err;
1743
1744         while (k--) {
1745                 /* change all left-side indexes */
1746                 if (path[k+1].p_idx != EXT_FIRST_INDEX(path[k+1].p_hdr))
1747                         break;
1748                 err = ext4_ext_get_access(handle, inode, path + k);
1749                 if (err)
1750                         goto clean;
1751                 path[k].p_idx->ei_block = border;
1752                 err = ext4_ext_dirty(handle, inode, path + k);
1753                 if (err)
1754                         goto clean;
1755         }
1756         return 0;
1757
1758 clean:
1759         /*
1760          * The path[k].p_bh is either unmodified or with no verified bit
1761          * set (see ext4_ext_get_access()). So just clear the verified bit
1762          * of the successfully modified extents buffers, which will force
1763          * these extents to be checked to avoid using inconsistent data.
1764          */
1765         while (++k < depth)
1766                 clear_buffer_verified(path[k].p_bh);
1767
1768         return err;
1769 }
1770
1771 static int ext4_can_extents_be_merged(struct inode *inode,
1772                                       struct ext4_extent *ex1,
1773                                       struct ext4_extent *ex2)
1774 {
1775         unsigned short ext1_ee_len, ext2_ee_len;
1776
1777         if (ext4_ext_is_unwritten(ex1) != ext4_ext_is_unwritten(ex2))
1778                 return 0;
1779
1780         ext1_ee_len = ext4_ext_get_actual_len(ex1);
1781         ext2_ee_len = ext4_ext_get_actual_len(ex2);
1782
1783         if (le32_to_cpu(ex1->ee_block) + ext1_ee_len !=
1784                         le32_to_cpu(ex2->ee_block))
1785                 return 0;
1786
1787         if (ext1_ee_len + ext2_ee_len > EXT_INIT_MAX_LEN)
1788                 return 0;
1789
1790         if (ext4_ext_is_unwritten(ex1) &&
1791             ext1_ee_len + ext2_ee_len > EXT_UNWRITTEN_MAX_LEN)
1792                 return 0;
1793 #ifdef AGGRESSIVE_TEST
1794         if (ext1_ee_len >= 4)
1795                 return 0;
1796 #endif
1797
1798         if (ext4_ext_pblock(ex1) + ext1_ee_len == ext4_ext_pblock(ex2))
1799                 return 1;
1800         return 0;
1801 }
1802
1803 /*
1804  * This function tries to merge the "ex" extent to the next extent in the tree.
1805  * It always tries to merge towards right. If you want to merge towards
1806  * left, pass "ex - 1" as argument instead of "ex".
1807  * Returns 0 if the extents (ex and ex+1) were _not_ merged and returns
1808  * 1 if they got merged.
1809  */
1810 static int ext4_ext_try_to_merge_right(struct inode *inode,
1811                                  struct ext4_ext_path *path,
1812                                  struct ext4_extent *ex)
1813 {
1814         struct ext4_extent_header *eh;
1815         unsigned int depth, len;
1816         int merge_done = 0, unwritten;
1817
1818         depth = ext_depth(inode);
1819         BUG_ON(path[depth].p_hdr == NULL);
1820         eh = path[depth].p_hdr;
1821
1822         while (ex < EXT_LAST_EXTENT(eh)) {
1823                 if (!ext4_can_extents_be_merged(inode, ex, ex + 1))
1824                         break;
1825                 /* merge with next extent! */
1826                 unwritten = ext4_ext_is_unwritten(ex);
1827                 ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
1828                                 + ext4_ext_get_actual_len(ex + 1));
1829                 if (unwritten)
1830                         ext4_ext_mark_unwritten(ex);
1831
1832                 if (ex + 1 < EXT_LAST_EXTENT(eh)) {
1833                         len = (EXT_LAST_EXTENT(eh) - ex - 1)
1834                                 * sizeof(struct ext4_extent);
1835                         memmove(ex + 1, ex + 2, len);
1836                 }
1837                 le16_add_cpu(&eh->eh_entries, -1);
1838                 merge_done = 1;
1839                 WARN_ON(eh->eh_entries == 0);
1840                 if (!eh->eh_entries)
1841                         EXT4_ERROR_INODE(inode, "eh->eh_entries = 0!");
1842         }
1843
1844         return merge_done;
1845 }
1846
1847 /*
1848  * This function does a very simple check to see if we can collapse
1849  * an extent tree with a single extent tree leaf block into the inode.
1850  */
1851 static void ext4_ext_try_to_merge_up(handle_t *handle,
1852                                      struct inode *inode,
1853                                      struct ext4_ext_path *path)
1854 {
1855         size_t s;
1856         unsigned max_root = ext4_ext_space_root(inode, 0);
1857         ext4_fsblk_t blk;
1858
1859         if ((path[0].p_depth != 1) ||
1860             (le16_to_cpu(path[0].p_hdr->eh_entries) != 1) ||
1861             (le16_to_cpu(path[1].p_hdr->eh_entries) > max_root))
1862                 return;
1863
1864         /*
1865          * We need to modify the block allocation bitmap and the block
1866          * group descriptor to release the extent tree block.  If we
1867          * can't get the journal credits, give up.
1868          */
1869         if (ext4_journal_extend(handle, 2,
1870                         ext4_free_metadata_revoke_credits(inode->i_sb, 1)))
1871                 return;
1872
1873         /*
1874          * Copy the extent data up to the inode
1875          */
1876         blk = ext4_idx_pblock(path[0].p_idx);
1877         s = le16_to_cpu(path[1].p_hdr->eh_entries) *
1878                 sizeof(struct ext4_extent_idx);
1879         s += sizeof(struct ext4_extent_header);
1880
1881         path[1].p_maxdepth = path[0].p_maxdepth;
1882         memcpy(path[0].p_hdr, path[1].p_hdr, s);
1883         path[0].p_depth = 0;
1884         path[0].p_ext = EXT_FIRST_EXTENT(path[0].p_hdr) +
1885                 (path[1].p_ext - EXT_FIRST_EXTENT(path[1].p_hdr));
1886         path[0].p_hdr->eh_max = cpu_to_le16(max_root);
1887
1888         ext4_ext_path_brelse(path + 1);
1889         ext4_free_blocks(handle, inode, NULL, blk, 1,
1890                          EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET);
1891 }
1892
1893 /*
1894  * This function tries to merge the @ex extent to neighbours in the tree, then
1895  * tries to collapse the extent tree into the inode.
1896  */
1897 static void ext4_ext_try_to_merge(handle_t *handle,
1898                                   struct inode *inode,
1899                                   struct ext4_ext_path *path,
1900                                   struct ext4_extent *ex)
1901 {
1902         struct ext4_extent_header *eh;
1903         unsigned int depth;
1904         int merge_done = 0;
1905
1906         depth = ext_depth(inode);
1907         BUG_ON(path[depth].p_hdr == NULL);
1908         eh = path[depth].p_hdr;
1909
1910         if (ex > EXT_FIRST_EXTENT(eh))
1911                 merge_done = ext4_ext_try_to_merge_right(inode, path, ex - 1);
1912
1913         if (!merge_done)
1914                 (void) ext4_ext_try_to_merge_right(inode, path, ex);
1915
1916         ext4_ext_try_to_merge_up(handle, inode, path);
1917 }
1918
1919 /*
1920  * check if a portion of the "newext" extent overlaps with an
1921  * existing extent.
1922  *
1923  * If there is an overlap discovered, it updates the length of the newext
1924  * such that there will be no overlap, and then returns 1.
1925  * If there is no overlap found, it returns 0.
1926  */
1927 static unsigned int ext4_ext_check_overlap(struct ext4_sb_info *sbi,
1928                                            struct inode *inode,
1929                                            struct ext4_extent *newext,
1930                                            struct ext4_ext_path *path)
1931 {
1932         ext4_lblk_t b1, b2;
1933         unsigned int depth, len1;
1934         unsigned int ret = 0;
1935
1936         b1 = le32_to_cpu(newext->ee_block);
1937         len1 = ext4_ext_get_actual_len(newext);
1938         depth = ext_depth(inode);
1939         if (!path[depth].p_ext)
1940                 goto out;
1941         b2 = EXT4_LBLK_CMASK(sbi, le32_to_cpu(path[depth].p_ext->ee_block));
1942
1943         /*
1944          * get the next allocated block if the extent in the path
1945          * is before the requested block(s)
1946          */
1947         if (b2 < b1) {
1948                 b2 = ext4_ext_next_allocated_block(path);
1949                 if (b2 == EXT_MAX_BLOCKS)
1950                         goto out;
1951                 b2 = EXT4_LBLK_CMASK(sbi, b2);
1952         }
1953
1954         /* check for wrap through zero on extent logical start block*/
1955         if (b1 + len1 < b1) {
1956                 len1 = EXT_MAX_BLOCKS - b1;
1957                 newext->ee_len = cpu_to_le16(len1);
1958                 ret = 1;
1959         }
1960
1961         /* check for overlap */
1962         if (b1 + len1 > b2) {
1963                 newext->ee_len = cpu_to_le16(b2 - b1);
1964                 ret = 1;
1965         }
1966 out:
1967         return ret;
1968 }
1969
1970 /*
1971  * ext4_ext_insert_extent:
1972  * tries to merge requested extent into the existing extent or
1973  * inserts requested extent as new one into the tree,
1974  * creating new leaf in the no-space case.
1975  */
1976 struct ext4_ext_path *
1977 ext4_ext_insert_extent(handle_t *handle, struct inode *inode,
1978                        struct ext4_ext_path *path,
1979                        struct ext4_extent *newext, int gb_flags)
1980 {
1981         struct ext4_extent_header *eh;
1982         struct ext4_extent *ex, *fex;
1983         struct ext4_extent *nearex; /* nearest extent */
1984         int depth, len, err = 0;
1985         ext4_lblk_t next;
1986         int mb_flags = 0, unwritten;
1987
1988         if (gb_flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE)
1989                 mb_flags |= EXT4_MB_DELALLOC_RESERVED;
1990         if (unlikely(ext4_ext_get_actual_len(newext) == 0)) {
1991                 EXT4_ERROR_INODE(inode, "ext4_ext_get_actual_len(newext) == 0");
1992                 err = -EFSCORRUPTED;
1993                 goto errout;
1994         }
1995         depth = ext_depth(inode);
1996         ex = path[depth].p_ext;
1997         eh = path[depth].p_hdr;
1998         if (unlikely(path[depth].p_hdr == NULL)) {
1999                 EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
2000                 err = -EFSCORRUPTED;
2001                 goto errout;
2002         }
2003
2004         /* try to insert block into found extent and return */
2005         if (ex && !(gb_flags & EXT4_GET_BLOCKS_PRE_IO)) {
2006
2007                 /*
2008                  * Try to see whether we should rather test the extent on
2009                  * right from ex, or from the left of ex. This is because
2010                  * ext4_find_extent() can return either extent on the
2011                  * left, or on the right from the searched position. This
2012                  * will make merging more effective.
2013                  */
2014                 if (ex < EXT_LAST_EXTENT(eh) &&
2015                     (le32_to_cpu(ex->ee_block) +
2016                     ext4_ext_get_actual_len(ex) <
2017                     le32_to_cpu(newext->ee_block))) {
2018                         ex += 1;
2019                         goto prepend;
2020                 } else if ((ex > EXT_FIRST_EXTENT(eh)) &&
2021                            (le32_to_cpu(newext->ee_block) +
2022                            ext4_ext_get_actual_len(newext) <
2023                            le32_to_cpu(ex->ee_block)))
2024                         ex -= 1;
2025
2026                 /* Try to append newex to the ex */
2027                 if (ext4_can_extents_be_merged(inode, ex, newext)) {
2028                         ext_debug(inode, "append [%d]%d block to %u:[%d]%d"
2029                                   "(from %llu)\n",
2030                                   ext4_ext_is_unwritten(newext),
2031                                   ext4_ext_get_actual_len(newext),
2032                                   le32_to_cpu(ex->ee_block),
2033                                   ext4_ext_is_unwritten(ex),
2034                                   ext4_ext_get_actual_len(ex),
2035                                   ext4_ext_pblock(ex));
2036                         err = ext4_ext_get_access(handle, inode,
2037                                                   path + depth);
2038                         if (err)
2039                                 goto errout;
2040                         unwritten = ext4_ext_is_unwritten(ex);
2041                         ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
2042                                         + ext4_ext_get_actual_len(newext));
2043                         if (unwritten)
2044                                 ext4_ext_mark_unwritten(ex);
2045                         nearex = ex;
2046                         goto merge;
2047                 }
2048
2049 prepend:
2050                 /* Try to prepend newex to the ex */
2051                 if (ext4_can_extents_be_merged(inode, newext, ex)) {
2052                         ext_debug(inode, "prepend %u[%d]%d block to %u:[%d]%d"
2053                                   "(from %llu)\n",
2054                                   le32_to_cpu(newext->ee_block),
2055                                   ext4_ext_is_unwritten(newext),
2056                                   ext4_ext_get_actual_len(newext),
2057                                   le32_to_cpu(ex->ee_block),
2058                                   ext4_ext_is_unwritten(ex),
2059                                   ext4_ext_get_actual_len(ex),
2060                                   ext4_ext_pblock(ex));
2061                         err = ext4_ext_get_access(handle, inode,
2062                                                   path + depth);
2063                         if (err)
2064                                 goto errout;
2065
2066                         unwritten = ext4_ext_is_unwritten(ex);
2067                         ex->ee_block = newext->ee_block;
2068                         ext4_ext_store_pblock(ex, ext4_ext_pblock(newext));
2069                         ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
2070                                         + ext4_ext_get_actual_len(newext));
2071                         if (unwritten)
2072                                 ext4_ext_mark_unwritten(ex);
2073                         nearex = ex;
2074                         goto merge;
2075                 }
2076         }
2077
2078         depth = ext_depth(inode);
2079         eh = path[depth].p_hdr;
2080         if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))
2081                 goto has_space;
2082
2083         /* probably next leaf has space for us? */
2084         fex = EXT_LAST_EXTENT(eh);
2085         next = EXT_MAX_BLOCKS;
2086         if (le32_to_cpu(newext->ee_block) > le32_to_cpu(fex->ee_block))
2087                 next = ext4_ext_next_leaf_block(path);
2088         if (next != EXT_MAX_BLOCKS) {
2089                 struct ext4_ext_path *npath;
2090
2091                 ext_debug(inode, "next leaf block - %u\n", next);
2092                 npath = ext4_find_extent(inode, next, NULL, gb_flags);
2093                 if (IS_ERR(npath)) {
2094                         err = PTR_ERR(npath);
2095                         goto errout;
2096                 }
2097                 BUG_ON(npath->p_depth != path->p_depth);
2098                 eh = npath[depth].p_hdr;
2099                 if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max)) {
2100                         ext_debug(inode, "next leaf isn't full(%d)\n",
2101                                   le16_to_cpu(eh->eh_entries));
2102                         ext4_free_ext_path(path);
2103                         path = npath;
2104                         goto has_space;
2105                 }
2106                 ext_debug(inode, "next leaf has no free space(%d,%d)\n",
2107                           le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
2108                 ext4_free_ext_path(npath);
2109         }
2110
2111         /*
2112          * There is no free space in the found leaf.
2113          * We're gonna add a new leaf in the tree.
2114          */
2115         if (gb_flags & EXT4_GET_BLOCKS_METADATA_NOFAIL)
2116                 mb_flags |= EXT4_MB_USE_RESERVED;
2117         path = ext4_ext_create_new_leaf(handle, inode, mb_flags, gb_flags,
2118                                         path, newext);
2119         if (IS_ERR(path))
2120                 return path;
2121         depth = ext_depth(inode);
2122         eh = path[depth].p_hdr;
2123
2124 has_space:
2125         nearex = path[depth].p_ext;
2126
2127         err = ext4_ext_get_access(handle, inode, path + depth);
2128         if (err)
2129                 goto errout;
2130
2131         if (!nearex) {
2132                 /* there is no extent in this leaf, create first one */
2133                 ext_debug(inode, "first extent in the leaf: %u:%llu:[%d]%d\n",
2134                                 le32_to_cpu(newext->ee_block),
2135                                 ext4_ext_pblock(newext),
2136                                 ext4_ext_is_unwritten(newext),
2137                                 ext4_ext_get_actual_len(newext));
2138                 nearex = EXT_FIRST_EXTENT(eh);
2139         } else {
2140                 if (le32_to_cpu(newext->ee_block)
2141                            > le32_to_cpu(nearex->ee_block)) {
2142                         /* Insert after */
2143                         ext_debug(inode, "insert %u:%llu:[%d]%d before: "
2144                                         "nearest %p\n",
2145                                         le32_to_cpu(newext->ee_block),
2146                                         ext4_ext_pblock(newext),
2147                                         ext4_ext_is_unwritten(newext),
2148                                         ext4_ext_get_actual_len(newext),
2149                                         nearex);
2150                         nearex++;
2151                 } else {
2152                         /* Insert before */
2153                         BUG_ON(newext->ee_block == nearex->ee_block);
2154                         ext_debug(inode, "insert %u:%llu:[%d]%d after: "
2155                                         "nearest %p\n",
2156                                         le32_to_cpu(newext->ee_block),
2157                                         ext4_ext_pblock(newext),
2158                                         ext4_ext_is_unwritten(newext),
2159                                         ext4_ext_get_actual_len(newext),
2160                                         nearex);
2161                 }
2162                 len = EXT_LAST_EXTENT(eh) - nearex + 1;
2163                 if (len > 0) {
2164                         ext_debug(inode, "insert %u:%llu:[%d]%d: "
2165                                         "move %d extents from 0x%p to 0x%p\n",
2166                                         le32_to_cpu(newext->ee_block),
2167                                         ext4_ext_pblock(newext),
2168                                         ext4_ext_is_unwritten(newext),
2169                                         ext4_ext_get_actual_len(newext),
2170                                         len, nearex, nearex + 1);
2171                         memmove(nearex + 1, nearex,
2172                                 len * sizeof(struct ext4_extent));
2173                 }
2174         }
2175
2176         le16_add_cpu(&eh->eh_entries, 1);
2177         path[depth].p_ext = nearex;
2178         nearex->ee_block = newext->ee_block;
2179         ext4_ext_store_pblock(nearex, ext4_ext_pblock(newext));
2180         nearex->ee_len = newext->ee_len;
2181
2182 merge:
2183         /* try to merge extents */
2184         if (!(gb_flags & EXT4_GET_BLOCKS_PRE_IO))
2185                 ext4_ext_try_to_merge(handle, inode, path, nearex);
2186
2187         /* time to correct all indexes above */
2188         err = ext4_ext_correct_indexes(handle, inode, path);
2189         if (err)
2190                 goto errout;
2191
2192         err = ext4_ext_dirty(handle, inode, path + path->p_depth);
2193         if (err)
2194                 goto errout;
2195
2196         return path;
2197
2198 errout:
2199         ext4_free_ext_path(path);
2200         return ERR_PTR(err);
2201 }
2202
2203 static int ext4_fill_es_cache_info(struct inode *inode,
2204                                    ext4_lblk_t block, ext4_lblk_t num,
2205                                    struct fiemap_extent_info *fieinfo)
2206 {
2207         ext4_lblk_t next, end = block + num - 1;
2208         struct extent_status es;
2209         unsigned char blksize_bits = inode->i_sb->s_blocksize_bits;
2210         unsigned int flags;
2211         int err;
2212
2213         while (block <= end) {
2214                 next = 0;
2215                 flags = 0;
2216                 if (!ext4_es_lookup_extent(inode, block, &next, &es))
2217                         break;
2218                 if (ext4_es_is_unwritten(&es))
2219                         flags |= FIEMAP_EXTENT_UNWRITTEN;
2220                 if (ext4_es_is_delayed(&es))
2221                         flags |= (FIEMAP_EXTENT_DELALLOC |
2222                                   FIEMAP_EXTENT_UNKNOWN);
2223                 if (ext4_es_is_hole(&es))
2224                         flags |= EXT4_FIEMAP_EXTENT_HOLE;
2225                 if (next == 0)
2226                         flags |= FIEMAP_EXTENT_LAST;
2227                 if (flags & (FIEMAP_EXTENT_DELALLOC|
2228                              EXT4_FIEMAP_EXTENT_HOLE))
2229                         es.es_pblk = 0;
2230                 else
2231                         es.es_pblk = ext4_es_pblock(&es);
2232                 err = fiemap_fill_next_extent(fieinfo,
2233                                 (__u64)es.es_lblk << blksize_bits,
2234                                 (__u64)es.es_pblk << blksize_bits,
2235                                 (__u64)es.es_len << blksize_bits,
2236                                 flags);
2237                 if (next == 0)
2238                         break;
2239                 block = next;
2240                 if (err < 0)
2241                         return err;
2242                 if (err == 1)
2243                         return 0;
2244         }
2245         return 0;
2246 }
2247
2248
2249 /*
2250  * ext4_ext_find_hole - find hole around given block according to the given path
2251  * @inode:      inode we lookup in
2252  * @path:       path in extent tree to @lblk
2253  * @lblk:       pointer to logical block around which we want to determine hole
2254  *
2255  * Determine hole length (and start if easily possible) around given logical
2256  * block. We don't try too hard to find the beginning of the hole but @path
2257  * actually points to extent before @lblk, we provide it.
2258  *
2259  * The function returns the length of a hole starting at @lblk. We update @lblk
2260  * to the beginning of the hole if we managed to find it.
2261  */
2262 static ext4_lblk_t ext4_ext_find_hole(struct inode *inode,
2263                                       struct ext4_ext_path *path,
2264                                       ext4_lblk_t *lblk)
2265 {
2266         int depth = ext_depth(inode);
2267         struct ext4_extent *ex;
2268         ext4_lblk_t len;
2269
2270         ex = path[depth].p_ext;
2271         if (ex == NULL) {
2272                 /* there is no extent yet, so gap is [0;-] */
2273                 *lblk = 0;
2274                 len = EXT_MAX_BLOCKS;
2275         } else if (*lblk < le32_to_cpu(ex->ee_block)) {
2276                 len = le32_to_cpu(ex->ee_block) - *lblk;
2277         } else if (*lblk >= le32_to_cpu(ex->ee_block)
2278                         + ext4_ext_get_actual_len(ex)) {
2279                 ext4_lblk_t next;
2280
2281                 *lblk = le32_to_cpu(ex->ee_block) + ext4_ext_get_actual_len(ex);
2282                 next = ext4_ext_next_allocated_block(path);
2283                 BUG_ON(next == *lblk);
2284                 len = next - *lblk;
2285         } else {
2286                 BUG();
2287         }
2288         return len;
2289 }
2290
2291 /*
2292  * ext4_ext_rm_idx:
2293  * removes index from the index block.
2294  */
2295 static int ext4_ext_rm_idx(handle_t *handle, struct inode *inode,
2296                         struct ext4_ext_path *path, int depth)
2297 {
2298         int err;
2299         ext4_fsblk_t leaf;
2300         int k = depth - 1;
2301
2302         /* free index block */
2303         leaf = ext4_idx_pblock(path[k].p_idx);
2304         if (unlikely(path[k].p_hdr->eh_entries == 0)) {
2305                 EXT4_ERROR_INODE(inode, "path[%d].p_hdr->eh_entries == 0", k);
2306                 return -EFSCORRUPTED;
2307         }
2308         err = ext4_ext_get_access(handle, inode, path + k);
2309         if (err)
2310                 return err;
2311
2312         if (path[k].p_idx != EXT_LAST_INDEX(path[k].p_hdr)) {
2313                 int len = EXT_LAST_INDEX(path[k].p_hdr) - path[k].p_idx;
2314                 len *= sizeof(struct ext4_extent_idx);
2315                 memmove(path[k].p_idx, path[k].p_idx + 1, len);
2316         }
2317
2318         le16_add_cpu(&path[k].p_hdr->eh_entries, -1);
2319         err = ext4_ext_dirty(handle, inode, path + k);
2320         if (err)
2321                 return err;
2322         ext_debug(inode, "index is empty, remove it, free block %llu\n", leaf);
2323         trace_ext4_ext_rm_idx(inode, leaf);
2324
2325         ext4_free_blocks(handle, inode, NULL, leaf, 1,
2326                          EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET);
2327
2328         while (--k >= 0) {
2329                 if (path[k + 1].p_idx != EXT_FIRST_INDEX(path[k + 1].p_hdr))
2330                         break;
2331                 err = ext4_ext_get_access(handle, inode, path + k);
2332                 if (err)
2333                         goto clean;
2334                 path[k].p_idx->ei_block = path[k + 1].p_idx->ei_block;
2335                 err = ext4_ext_dirty(handle, inode, path + k);
2336                 if (err)
2337                         goto clean;
2338         }
2339         return 0;
2340
2341 clean:
2342         /*
2343          * The path[k].p_bh is either unmodified or with no verified bit
2344          * set (see ext4_ext_get_access()). So just clear the verified bit
2345          * of the successfully modified extents buffers, which will force
2346          * these extents to be checked to avoid using inconsistent data.
2347          */
2348         while (++k < depth)
2349                 clear_buffer_verified(path[k].p_bh);
2350
2351         return err;
2352 }
2353
2354 /*
2355  * ext4_ext_calc_credits_for_single_extent:
2356  * This routine returns max. credits that needed to insert an extent
2357  * to the extent tree.
2358  * When pass the actual path, the caller should calculate credits
2359  * under i_data_sem.
2360  */
2361 int ext4_ext_calc_credits_for_single_extent(struct inode *inode, int nrblocks,
2362                                                 struct ext4_ext_path *path)
2363 {
2364         if (path) {
2365                 int depth = ext_depth(inode);
2366                 int ret = 0;
2367
2368                 /* probably there is space in leaf? */
2369                 if (le16_to_cpu(path[depth].p_hdr->eh_entries)
2370                                 < le16_to_cpu(path[depth].p_hdr->eh_max)) {
2371
2372                         /*
2373                          *  There are some space in the leaf tree, no
2374                          *  need to account for leaf block credit
2375                          *
2376                          *  bitmaps and block group descriptor blocks
2377                          *  and other metadata blocks still need to be
2378                          *  accounted.
2379                          */
2380                         /* 1 bitmap, 1 block group descriptor */
2381                         ret = 2 + EXT4_META_TRANS_BLOCKS(inode->i_sb);
2382                         return ret;
2383                 }
2384         }
2385
2386         return ext4_chunk_trans_blocks(inode, nrblocks);
2387 }
2388
2389 /*
2390  * How many index/leaf blocks need to change/allocate to add @extents extents?
2391  *
2392  * If we add a single extent, then in the worse case, each tree level
2393  * index/leaf need to be changed in case of the tree split.
2394  *
2395  * If more extents are inserted, they could cause the whole tree split more
2396  * than once, but this is really rare.
2397  */
2398 int ext4_ext_index_trans_blocks(struct inode *inode, int extents)
2399 {
2400         int index;
2401
2402         /* If we are converting the inline data, only one is needed here. */
2403         if (ext4_has_inline_data(inode))
2404                 return 1;
2405
2406         /*
2407          * Extent tree can change between the time we estimate credits and
2408          * the time we actually modify the tree. Assume the worst case.
2409          */
2410         if (extents <= 1)
2411                 index = (EXT4_MAX_EXTENT_DEPTH * 2) + extents;
2412         else
2413                 index = (EXT4_MAX_EXTENT_DEPTH * 3) +
2414                         DIV_ROUND_UP(extents, ext4_ext_space_block(inode, 0));
2415
2416         return index;
2417 }
2418
2419 static inline int get_default_free_blocks_flags(struct inode *inode)
2420 {
2421         if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode) ||
2422             ext4_test_inode_flag(inode, EXT4_INODE_EA_INODE))
2423                 return EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET;
2424         else if (ext4_should_journal_data(inode))
2425                 return EXT4_FREE_BLOCKS_FORGET;
2426         return 0;
2427 }
2428
2429 /*
2430  * ext4_rereserve_cluster - increment the reserved cluster count when
2431  *                          freeing a cluster with a pending reservation
2432  *
2433  * @inode - file containing the cluster
2434  * @lblk - logical block in cluster to be reserved
2435  *
2436  * Increments the reserved cluster count and adjusts quota in a bigalloc
2437  * file system when freeing a partial cluster containing at least one
2438  * delayed and unwritten block.  A partial cluster meeting that
2439  * requirement will have a pending reservation.  If so, the
2440  * RERESERVE_CLUSTER flag is used when calling ext4_free_blocks() to
2441  * defer reserved and allocated space accounting to a subsequent call
2442  * to this function.
2443  */
2444 static void ext4_rereserve_cluster(struct inode *inode, ext4_lblk_t lblk)
2445 {
2446         struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2447         struct ext4_inode_info *ei = EXT4_I(inode);
2448
2449         dquot_reclaim_block(inode, EXT4_C2B(sbi, 1));
2450
2451         spin_lock(&ei->i_block_reservation_lock);
2452         ei->i_reserved_data_blocks++;
2453         percpu_counter_add(&sbi->s_dirtyclusters_counter, 1);
2454         spin_unlock(&ei->i_block_reservation_lock);
2455
2456         percpu_counter_add(&sbi->s_freeclusters_counter, 1);
2457         ext4_remove_pending(inode, lblk);
2458 }
2459
2460 static int ext4_remove_blocks(handle_t *handle, struct inode *inode,
2461                               struct ext4_extent *ex,
2462                               struct partial_cluster *partial,
2463                               ext4_lblk_t from, ext4_lblk_t to)
2464 {
2465         struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2466         unsigned short ee_len = ext4_ext_get_actual_len(ex);
2467         ext4_fsblk_t last_pblk, pblk;
2468         ext4_lblk_t num;
2469         int flags;
2470
2471         /* only extent tail removal is allowed */
2472         if (from < le32_to_cpu(ex->ee_block) ||
2473             to != le32_to_cpu(ex->ee_block) + ee_len - 1) {
2474                 ext4_error(sbi->s_sb,
2475                            "strange request: removal(2) %u-%u from %u:%u",
2476                            from, to, le32_to_cpu(ex->ee_block), ee_len);
2477                 return 0;
2478         }
2479
2480 #ifdef EXTENTS_STATS
2481         spin_lock(&sbi->s_ext_stats_lock);
2482         sbi->s_ext_blocks += ee_len;
2483         sbi->s_ext_extents++;
2484         if (ee_len < sbi->s_ext_min)
2485                 sbi->s_ext_min = ee_len;
2486         if (ee_len > sbi->s_ext_max)
2487                 sbi->s_ext_max = ee_len;
2488         if (ext_depth(inode) > sbi->s_depth_max)
2489                 sbi->s_depth_max = ext_depth(inode);
2490         spin_unlock(&sbi->s_ext_stats_lock);
2491 #endif
2492
2493         trace_ext4_remove_blocks(inode, ex, from, to, partial);
2494
2495         /*
2496          * if we have a partial cluster, and it's different from the
2497          * cluster of the last block in the extent, we free it
2498          */
2499         last_pblk = ext4_ext_pblock(ex) + ee_len - 1;
2500
2501         if (partial->state != initial &&
2502             partial->pclu != EXT4_B2C(sbi, last_pblk)) {
2503                 if (partial->state == tofree) {
2504                         flags = get_default_free_blocks_flags(inode);
2505                         if (ext4_is_pending(inode, partial->lblk))
2506                                 flags |= EXT4_FREE_BLOCKS_RERESERVE_CLUSTER;
2507                         ext4_free_blocks(handle, inode, NULL,
2508                                          EXT4_C2B(sbi, partial->pclu),
2509                                          sbi->s_cluster_ratio, flags);
2510                         if (flags & EXT4_FREE_BLOCKS_RERESERVE_CLUSTER)
2511                                 ext4_rereserve_cluster(inode, partial->lblk);
2512                 }
2513                 partial->state = initial;
2514         }
2515
2516         num = le32_to_cpu(ex->ee_block) + ee_len - from;
2517         pblk = ext4_ext_pblock(ex) + ee_len - num;
2518
2519         /*
2520          * We free the partial cluster at the end of the extent (if any),
2521          * unless the cluster is used by another extent (partial_cluster
2522          * state is nofree).  If a partial cluster exists here, it must be
2523          * shared with the last block in the extent.
2524          */
2525         flags = get_default_free_blocks_flags(inode);
2526
2527         /* partial, left end cluster aligned, right end unaligned */
2528         if ((EXT4_LBLK_COFF(sbi, to) != sbi->s_cluster_ratio - 1) &&
2529             (EXT4_LBLK_CMASK(sbi, to) >= from) &&
2530             (partial->state != nofree)) {
2531                 if (ext4_is_pending(inode, to))
2532                         flags |= EXT4_FREE_BLOCKS_RERESERVE_CLUSTER;
2533                 ext4_free_blocks(handle, inode, NULL,
2534                                  EXT4_PBLK_CMASK(sbi, last_pblk),
2535                                  sbi->s_cluster_ratio, flags);
2536                 if (flags & EXT4_FREE_BLOCKS_RERESERVE_CLUSTER)
2537                         ext4_rereserve_cluster(inode, to);
2538                 partial->state = initial;
2539                 flags = get_default_free_blocks_flags(inode);
2540         }
2541
2542         flags |= EXT4_FREE_BLOCKS_NOFREE_LAST_CLUSTER;
2543
2544         /*
2545          * For bigalloc file systems, we never free a partial cluster
2546          * at the beginning of the extent.  Instead, we check to see if we
2547          * need to free it on a subsequent call to ext4_remove_blocks,
2548          * or at the end of ext4_ext_rm_leaf or ext4_ext_remove_space.
2549          */
2550         flags |= EXT4_FREE_BLOCKS_NOFREE_FIRST_CLUSTER;
2551         ext4_free_blocks(handle, inode, NULL, pblk, num, flags);
2552
2553         /* reset the partial cluster if we've freed past it */
2554         if (partial->state != initial && partial->pclu != EXT4_B2C(sbi, pblk))
2555                 partial->state = initial;
2556
2557         /*
2558          * If we've freed the entire extent but the beginning is not left
2559          * cluster aligned and is not marked as ineligible for freeing we
2560          * record the partial cluster at the beginning of the extent.  It
2561          * wasn't freed by the preceding ext4_free_blocks() call, and we
2562          * need to look farther to the left to determine if it's to be freed
2563          * (not shared with another extent). Else, reset the partial
2564          * cluster - we're either  done freeing or the beginning of the
2565          * extent is left cluster aligned.
2566          */
2567         if (EXT4_LBLK_COFF(sbi, from) && num == ee_len) {
2568                 if (partial->state == initial) {
2569                         partial->pclu = EXT4_B2C(sbi, pblk);
2570                         partial->lblk = from;
2571                         partial->state = tofree;
2572                 }
2573         } else {
2574                 partial->state = initial;
2575         }
2576
2577         return 0;
2578 }
2579
2580 /*
2581  * ext4_ext_rm_leaf() Removes the extents associated with the
2582  * blocks appearing between "start" and "end".  Both "start"
2583  * and "end" must appear in the same extent or EIO is returned.
2584  *
2585  * @handle: The journal handle
2586  * @inode:  The files inode
2587  * @path:   The path to the leaf
2588  * @partial_cluster: The cluster which we'll have to free if all extents
2589  *                   has been released from it.  However, if this value is
2590  *                   negative, it's a cluster just to the right of the
2591  *                   punched region and it must not be freed.
2592  * @start:  The first block to remove
2593  * @end:   The last block to remove
2594  */
2595 static int
2596 ext4_ext_rm_leaf(handle_t *handle, struct inode *inode,
2597                  struct ext4_ext_path *path,
2598                  struct partial_cluster *partial,
2599                  ext4_lblk_t start, ext4_lblk_t end)
2600 {
2601         struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2602         int err = 0, correct_index = 0;
2603         int depth = ext_depth(inode), credits, revoke_credits;
2604         struct ext4_extent_header *eh;
2605         ext4_lblk_t a, b;
2606         unsigned num;
2607         ext4_lblk_t ex_ee_block;
2608         unsigned short ex_ee_len;
2609         unsigned unwritten = 0;
2610         struct ext4_extent *ex;
2611         ext4_fsblk_t pblk;
2612
2613         /* the header must be checked already in ext4_ext_remove_space() */
2614         ext_debug(inode, "truncate since %u in leaf to %u\n", start, end);
2615         if (!path[depth].p_hdr)
2616                 path[depth].p_hdr = ext_block_hdr(path[depth].p_bh);
2617         eh = path[depth].p_hdr;
2618         if (unlikely(path[depth].p_hdr == NULL)) {
2619                 EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
2620                 return -EFSCORRUPTED;
2621         }
2622         /* find where to start removing */
2623         ex = path[depth].p_ext;
2624         if (!ex)
2625                 ex = EXT_LAST_EXTENT(eh);
2626
2627         ex_ee_block = le32_to_cpu(ex->ee_block);
2628         ex_ee_len = ext4_ext_get_actual_len(ex);
2629
2630         trace_ext4_ext_rm_leaf(inode, start, ex, partial);
2631
2632         while (ex >= EXT_FIRST_EXTENT(eh) &&
2633                         ex_ee_block + ex_ee_len > start) {
2634
2635                 if (ext4_ext_is_unwritten(ex))
2636                         unwritten = 1;
2637                 else
2638                         unwritten = 0;
2639
2640                 ext_debug(inode, "remove ext %u:[%d]%d\n", ex_ee_block,
2641                           unwritten, ex_ee_len);
2642                 path[depth].p_ext = ex;
2643
2644                 a = max(ex_ee_block, start);
2645                 b = min(ex_ee_block + ex_ee_len - 1, end);
2646
2647                 ext_debug(inode, "  border %u:%u\n", a, b);
2648
2649                 /* If this extent is beyond the end of the hole, skip it */
2650                 if (end < ex_ee_block) {
2651                         /*
2652                          * We're going to skip this extent and move to another,
2653                          * so note that its first cluster is in use to avoid
2654                          * freeing it when removing blocks.  Eventually, the
2655                          * right edge of the truncated/punched region will
2656                          * be just to the left.
2657                          */
2658                         if (sbi->s_cluster_ratio > 1) {
2659                                 pblk = ext4_ext_pblock(ex);
2660                                 partial->pclu = EXT4_B2C(sbi, pblk);
2661                                 partial->state = nofree;
2662                         }
2663                         ex--;
2664                         ex_ee_block = le32_to_cpu(ex->ee_block);
2665                         ex_ee_len = ext4_ext_get_actual_len(ex);
2666                         continue;
2667                 } else if (b != ex_ee_block + ex_ee_len - 1) {
2668                         EXT4_ERROR_INODE(inode,
2669                                          "can not handle truncate %u:%u "
2670                                          "on extent %u:%u",
2671                                          start, end, ex_ee_block,
2672                                          ex_ee_block + ex_ee_len - 1);
2673                         err = -EFSCORRUPTED;
2674                         goto out;
2675                 } else if (a != ex_ee_block) {
2676                         /* remove tail of the extent */
2677                         num = a - ex_ee_block;
2678                 } else {
2679                         /* remove whole extent: excellent! */
2680                         num = 0;
2681                 }
2682                 /*
2683                  * 3 for leaf, sb, and inode plus 2 (bmap and group
2684                  * descriptor) for each block group; assume two block
2685                  * groups plus ex_ee_len/blocks_per_block_group for
2686                  * the worst case
2687                  */
2688                 credits = 7 + 2*(ex_ee_len/EXT4_BLOCKS_PER_GROUP(inode->i_sb));
2689                 if (ex == EXT_FIRST_EXTENT(eh)) {
2690                         correct_index = 1;
2691                         credits += (ext_depth(inode)) + 1;
2692                 }
2693                 credits += EXT4_MAXQUOTAS_TRANS_BLOCKS(inode->i_sb);
2694                 /*
2695                  * We may end up freeing some index blocks and data from the
2696                  * punched range. Note that partial clusters are accounted for
2697                  * by ext4_free_data_revoke_credits().
2698                  */
2699                 revoke_credits =
2700                         ext4_free_metadata_revoke_credits(inode->i_sb,
2701                                                           ext_depth(inode)) +
2702                         ext4_free_data_revoke_credits(inode, b - a + 1);
2703
2704                 err = ext4_datasem_ensure_credits(handle, inode, credits,
2705                                                   credits, revoke_credits);
2706                 if (err) {
2707                         if (err > 0)
2708                                 err = -EAGAIN;
2709                         goto out;
2710                 }
2711
2712                 err = ext4_ext_get_access(handle, inode, path + depth);
2713                 if (err)
2714                         goto out;
2715
2716                 err = ext4_remove_blocks(handle, inode, ex, partial, a, b);
2717                 if (err)
2718                         goto out;
2719
2720                 if (num == 0)
2721                         /* this extent is removed; mark slot entirely unused */
2722                         ext4_ext_store_pblock(ex, 0);
2723
2724                 ex->ee_len = cpu_to_le16(num);
2725                 /*
2726                  * Do not mark unwritten if all the blocks in the
2727                  * extent have been removed.
2728                  */
2729                 if (unwritten && num)
2730                         ext4_ext_mark_unwritten(ex);
2731                 /*
2732                  * If the extent was completely released,
2733                  * we need to remove it from the leaf
2734                  */
2735                 if (num == 0) {
2736                         if (end != EXT_MAX_BLOCKS - 1) {
2737                                 /*
2738                                  * For hole punching, we need to scoot all the
2739                                  * extents up when an extent is removed so that
2740                                  * we dont have blank extents in the middle
2741                                  */
2742                                 memmove(ex, ex+1, (EXT_LAST_EXTENT(eh) - ex) *
2743                                         sizeof(struct ext4_extent));
2744
2745                                 /* Now get rid of the one at the end */
2746                                 memset(EXT_LAST_EXTENT(eh), 0,
2747                                         sizeof(struct ext4_extent));
2748                         }
2749                         le16_add_cpu(&eh->eh_entries, -1);
2750                 }
2751
2752                 err = ext4_ext_dirty(handle, inode, path + depth);
2753                 if (err)
2754                         goto out;
2755
2756                 ext_debug(inode, "new extent: %u:%u:%llu\n", ex_ee_block, num,
2757                                 ext4_ext_pblock(ex));
2758                 ex--;
2759                 ex_ee_block = le32_to_cpu(ex->ee_block);
2760                 ex_ee_len = ext4_ext_get_actual_len(ex);
2761         }
2762
2763         if (correct_index && eh->eh_entries)
2764                 err = ext4_ext_correct_indexes(handle, inode, path);
2765
2766         /*
2767          * If there's a partial cluster and at least one extent remains in
2768          * the leaf, free the partial cluster if it isn't shared with the
2769          * current extent.  If it is shared with the current extent
2770          * we reset the partial cluster because we've reached the start of the
2771          * truncated/punched region and we're done removing blocks.
2772          */
2773         if (partial->state == tofree && ex >= EXT_FIRST_EXTENT(eh)) {
2774                 pblk = ext4_ext_pblock(ex) + ex_ee_len - 1;
2775                 if (partial->pclu != EXT4_B2C(sbi, pblk)) {
2776                         int flags = get_default_free_blocks_flags(inode);
2777
2778                         if (ext4_is_pending(inode, partial->lblk))
2779                                 flags |= EXT4_FREE_BLOCKS_RERESERVE_CLUSTER;
2780                         ext4_free_blocks(handle, inode, NULL,
2781                                          EXT4_C2B(sbi, partial->pclu),
2782                                          sbi->s_cluster_ratio, flags);
2783                         if (flags & EXT4_FREE_BLOCKS_RERESERVE_CLUSTER)
2784                                 ext4_rereserve_cluster(inode, partial->lblk);
2785                 }
2786                 partial->state = initial;
2787         }
2788
2789         /* if this leaf is free, then we should
2790          * remove it from index block above */
2791         if (err == 0 && eh->eh_entries == 0 && path[depth].p_bh != NULL)
2792                 err = ext4_ext_rm_idx(handle, inode, path, depth);
2793
2794 out:
2795         return err;
2796 }
2797
2798 /*
2799  * ext4_ext_more_to_rm:
2800  * returns 1 if current index has to be freed (even partial)
2801  */
2802 static int
2803 ext4_ext_more_to_rm(struct ext4_ext_path *path)
2804 {
2805         BUG_ON(path->p_idx == NULL);
2806
2807         if (path->p_idx < EXT_FIRST_INDEX(path->p_hdr))
2808                 return 0;
2809
2810         /*
2811          * if truncate on deeper level happened, it wasn't partial,
2812          * so we have to consider current index for truncation
2813          */
2814         if (le16_to_cpu(path->p_hdr->eh_entries) == path->p_block)
2815                 return 0;
2816         return 1;
2817 }
2818
2819 int ext4_ext_remove_space(struct inode *inode, ext4_lblk_t start,
2820                           ext4_lblk_t end)
2821 {
2822         struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2823         int depth = ext_depth(inode);
2824         struct ext4_ext_path *path = NULL;
2825         struct partial_cluster partial;
2826         handle_t *handle;
2827         int i = 0, err = 0;
2828         int flags = EXT4_EX_NOCACHE | EXT4_EX_NOFAIL;
2829
2830         partial.pclu = 0;
2831         partial.lblk = 0;
2832         partial.state = initial;
2833
2834         ext_debug(inode, "truncate since %u to %u\n", start, end);
2835
2836         /* probably first extent we're gonna free will be last in block */
2837         handle = ext4_journal_start_with_revoke(inode, EXT4_HT_TRUNCATE,
2838                         depth + 1,
2839                         ext4_free_metadata_revoke_credits(inode->i_sb, depth));
2840         if (IS_ERR(handle))
2841                 return PTR_ERR(handle);
2842
2843 again:
2844         trace_ext4_ext_remove_space(inode, start, end, depth);
2845
2846         /*
2847          * Check if we are removing extents inside the extent tree. If that
2848          * is the case, we are going to punch a hole inside the extent tree
2849          * so we have to check whether we need to split the extent covering
2850          * the last block to remove so we can easily remove the part of it
2851          * in ext4_ext_rm_leaf().
2852          */
2853         if (end < EXT_MAX_BLOCKS - 1) {
2854                 struct ext4_extent *ex;
2855                 ext4_lblk_t ee_block, ex_end, lblk;
2856                 ext4_fsblk_t pblk;
2857
2858                 /* find extent for or closest extent to this block */
2859                 path = ext4_find_extent(inode, end, NULL, flags);
2860                 if (IS_ERR(path)) {
2861                         ext4_journal_stop(handle);
2862                         return PTR_ERR(path);
2863                 }
2864                 depth = ext_depth(inode);
2865                 /* Leaf not may not exist only if inode has no blocks at all */
2866                 ex = path[depth].p_ext;
2867                 if (!ex) {
2868                         if (depth) {
2869                                 EXT4_ERROR_INODE(inode,
2870                                                  "path[%d].p_hdr == NULL",
2871                                                  depth);
2872                                 err = -EFSCORRUPTED;
2873                         }
2874                         goto out;
2875                 }
2876
2877                 ee_block = le32_to_cpu(ex->ee_block);
2878                 ex_end = ee_block + ext4_ext_get_actual_len(ex) - 1;
2879
2880                 /*
2881                  * See if the last block is inside the extent, if so split
2882                  * the extent at 'end' block so we can easily remove the
2883                  * tail of the first part of the split extent in
2884                  * ext4_ext_rm_leaf().
2885                  */
2886                 if (end >= ee_block && end < ex_end) {
2887
2888                         /*
2889                          * If we're going to split the extent, note that
2890                          * the cluster containing the block after 'end' is
2891                          * in use to avoid freeing it when removing blocks.
2892                          */
2893                         if (sbi->s_cluster_ratio > 1) {
2894                                 pblk = ext4_ext_pblock(ex) + end - ee_block + 1;
2895                                 partial.pclu = EXT4_B2C(sbi, pblk);
2896                                 partial.state = nofree;
2897                         }
2898
2899                         /*
2900                          * Split the extent in two so that 'end' is the last
2901                          * block in the first new extent. Also we should not
2902                          * fail removing space due to ENOSPC so try to use
2903                          * reserved block if that happens.
2904                          */
2905                         path = ext4_force_split_extent_at(handle, inode, path,
2906                                                           end + 1, 1);
2907                         if (IS_ERR(path)) {
2908                                 err = PTR_ERR(path);
2909                                 goto out;
2910                         }
2911                 } else if (sbi->s_cluster_ratio > 1 && end >= ex_end &&
2912                            partial.state == initial) {
2913                         /*
2914                          * If we're punching, there's an extent to the right.
2915                          * If the partial cluster hasn't been set, set it to
2916                          * that extent's first cluster and its state to nofree
2917                          * so it won't be freed should it contain blocks to be
2918                          * removed. If it's already set (tofree/nofree), we're
2919                          * retrying and keep the original partial cluster info
2920                          * so a cluster marked tofree as a result of earlier
2921                          * extent removal is not lost.
2922                          */
2923                         lblk = ex_end + 1;
2924                         err = ext4_ext_search_right(inode, path, &lblk, &pblk,
2925                                                     NULL, flags);
2926                         if (err < 0)
2927                                 goto out;
2928                         if (pblk) {
2929                                 partial.pclu = EXT4_B2C(sbi, pblk);
2930                                 partial.state = nofree;
2931                         }
2932                 }
2933         }
2934         /*
2935          * We start scanning from right side, freeing all the blocks
2936          * after i_size and walking into the tree depth-wise.
2937          */
2938         depth = ext_depth(inode);
2939         if (path) {
2940                 int k = i = depth;
2941                 while (--k > 0)
2942                         path[k].p_block =
2943                                 le16_to_cpu(path[k].p_hdr->eh_entries)+1;
2944         } else {
2945                 path = kcalloc(depth + 1, sizeof(struct ext4_ext_path),
2946                                GFP_NOFS | __GFP_NOFAIL);
2947                 if (path == NULL) {
2948                         ext4_journal_stop(handle);
2949                         return -ENOMEM;
2950                 }
2951                 path[0].p_maxdepth = path[0].p_depth = depth;
2952                 path[0].p_hdr = ext_inode_hdr(inode);
2953                 i = 0;
2954
2955                 if (ext4_ext_check(inode, path[0].p_hdr, depth, 0)) {
2956                         err = -EFSCORRUPTED;
2957                         goto out;
2958                 }
2959         }
2960         err = 0;
2961
2962         while (i >= 0 && err == 0) {
2963                 if (i == depth) {
2964                         /* this is leaf block */
2965                         err = ext4_ext_rm_leaf(handle, inode, path,
2966                                                &partial, start, end);
2967                         /* root level has p_bh == NULL, brelse() eats this */
2968                         ext4_ext_path_brelse(path + i);
2969                         i--;
2970                         continue;
2971                 }
2972
2973                 /* this is index block */
2974                 if (!path[i].p_hdr) {
2975                         ext_debug(inode, "initialize header\n");
2976                         path[i].p_hdr = ext_block_hdr(path[i].p_bh);
2977                 }
2978
2979                 if (!path[i].p_idx) {
2980                         /* this level hasn't been touched yet */
2981                         path[i].p_idx = EXT_LAST_INDEX(path[i].p_hdr);
2982                         path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries)+1;
2983                         ext_debug(inode, "init index ptr: hdr 0x%p, num %d\n",
2984                                   path[i].p_hdr,
2985                                   le16_to_cpu(path[i].p_hdr->eh_entries));
2986                 } else {
2987                         /* we were already here, see at next index */
2988                         path[i].p_idx--;
2989                 }
2990
2991                 ext_debug(inode, "level %d - index, first 0x%p, cur 0x%p\n",
2992                                 i, EXT_FIRST_INDEX(path[i].p_hdr),
2993                                 path[i].p_idx);
2994                 if (ext4_ext_more_to_rm(path + i)) {
2995                         struct buffer_head *bh;
2996                         /* go to the next level */
2997                         ext_debug(inode, "move to level %d (block %llu)\n",
2998                                   i + 1, ext4_idx_pblock(path[i].p_idx));
2999                         memset(path + i + 1, 0, sizeof(*path));
3000                         bh = read_extent_tree_block(inode, path[i].p_idx,
3001                                                     depth - i - 1, flags);
3002                         if (IS_ERR(bh)) {
3003                                 /* should we reset i_size? */
3004                                 err = PTR_ERR(bh);
3005                                 break;
3006                         }
3007                         /* Yield here to deal with large extent trees.
3008                          * Should be a no-op if we did IO above. */
3009                         cond_resched();
3010                         if (WARN_ON(i + 1 > depth)) {
3011                                 err = -EFSCORRUPTED;
3012                                 break;
3013                         }
3014                         path[i + 1].p_bh = bh;
3015
3016                         /* save actual number of indexes since this
3017                          * number is changed at the next iteration */
3018                         path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries);
3019                         i++;
3020                 } else {
3021                         /* we finished processing this index, go up */
3022                         if (path[i].p_hdr->eh_entries == 0 && i > 0) {
3023                                 /* index is empty, remove it;
3024                                  * handle must be already prepared by the
3025                                  * truncatei_leaf() */
3026                                 err = ext4_ext_rm_idx(handle, inode, path, i);
3027                         }
3028                         /* root level has p_bh == NULL, brelse() eats this */
3029                         ext4_ext_path_brelse(path + i);
3030                         i--;
3031                         ext_debug(inode, "return to level %d\n", i);
3032                 }
3033         }
3034
3035         trace_ext4_ext_remove_space_done(inode, start, end, depth, &partial,
3036                                          path->p_hdr->eh_entries);
3037
3038         /*
3039          * if there's a partial cluster and we have removed the first extent
3040          * in the file, then we also free the partial cluster, if any
3041          */
3042         if (partial.state == tofree && err == 0) {
3043                 int flags = get_default_free_blocks_flags(inode);
3044
3045                 if (ext4_is_pending(inode, partial.lblk))
3046                         flags |= EXT4_FREE_BLOCKS_RERESERVE_CLUSTER;
3047                 ext4_free_blocks(handle, inode, NULL,
3048                                  EXT4_C2B(sbi, partial.pclu),
3049                                  sbi->s_cluster_ratio, flags);
3050                 if (flags & EXT4_FREE_BLOCKS_RERESERVE_CLUSTER)
3051                         ext4_rereserve_cluster(inode, partial.lblk);
3052                 partial.state = initial;
3053         }
3054
3055         /* TODO: flexible tree reduction should be here */
3056         if (path->p_hdr->eh_entries == 0) {
3057                 /*
3058                  * truncate to zero freed all the tree,
3059                  * so we need to correct eh_depth
3060                  */
3061                 err = ext4_ext_get_access(handle, inode, path);
3062                 if (err == 0) {
3063                         ext_inode_hdr(inode)->eh_depth = 0;
3064                         ext_inode_hdr(inode)->eh_max =
3065                                 cpu_to_le16(ext4_ext_space_root(inode, 0));
3066                         err = ext4_ext_dirty(handle, inode, path);
3067                 }
3068         }
3069 out:
3070         ext4_free_ext_path(path);
3071         path = NULL;
3072         if (err == -EAGAIN)
3073                 goto again;
3074         ext4_journal_stop(handle);
3075
3076         return err;
3077 }
3078
3079 /*
3080  * called at mount time
3081  */
3082 void ext4_ext_init(struct super_block *sb)
3083 {
3084         /*
3085          * possible initialization would be here
3086          */
3087
3088         if (ext4_has_feature_extents(sb)) {
3089 #if defined(AGGRESSIVE_TEST) || defined(CHECK_BINSEARCH) || defined(EXTENTS_STATS)
3090                 printk(KERN_INFO "EXT4-fs: file extents enabled"
3091 #ifdef AGGRESSIVE_TEST
3092                        ", aggressive tests"
3093 #endif
3094 #ifdef CHECK_BINSEARCH
3095                        ", check binsearch"
3096 #endif
3097 #ifdef EXTENTS_STATS
3098                        ", stats"
3099 #endif
3100                        "\n");
3101 #endif
3102 #ifdef EXTENTS_STATS
3103                 spin_lock_init(&EXT4_SB(sb)->s_ext_stats_lock);
3104                 EXT4_SB(sb)->s_ext_min = 1 << 30;
3105                 EXT4_SB(sb)->s_ext_max = 0;
3106 #endif
3107         }
3108 }
3109
3110 /*
3111  * called at umount time
3112  */
3113 void ext4_ext_release(struct super_block *sb)
3114 {
3115         if (!ext4_has_feature_extents(sb))
3116                 return;
3117
3118 #ifdef EXTENTS_STATS
3119         if (EXT4_SB(sb)->s_ext_blocks && EXT4_SB(sb)->s_ext_extents) {
3120                 struct ext4_sb_info *sbi = EXT4_SB(sb);
3121                 printk(KERN_ERR "EXT4-fs: %lu blocks in %lu extents (%lu ave)\n",
3122                         sbi->s_ext_blocks, sbi->s_ext_extents,
3123                         sbi->s_ext_blocks / sbi->s_ext_extents);
3124                 printk(KERN_ERR "EXT4-fs: extents: %lu min, %lu max, max depth %lu\n",
3125                         sbi->s_ext_min, sbi->s_ext_max, sbi->s_depth_max);
3126         }
3127 #endif
3128 }
3129
3130 static void ext4_zeroout_es(struct inode *inode, struct ext4_extent *ex)
3131 {
3132         ext4_lblk_t  ee_block;
3133         ext4_fsblk_t ee_pblock;
3134         unsigned int ee_len;
3135
3136         ee_block  = le32_to_cpu(ex->ee_block);
3137         ee_len    = ext4_ext_get_actual_len(ex);
3138         ee_pblock = ext4_ext_pblock(ex);
3139
3140         if (ee_len == 0)
3141                 return;
3142
3143         ext4_es_insert_extent(inode, ee_block, ee_len, ee_pblock,
3144                               EXTENT_STATUS_WRITTEN, false);
3145 }
3146
3147 /* FIXME!! we need to try to merge to left or right after zero-out  */
3148 static int ext4_ext_zeroout(struct inode *inode, struct ext4_extent *ex)
3149 {
3150         ext4_fsblk_t ee_pblock;
3151         unsigned int ee_len;
3152
3153         ee_len    = ext4_ext_get_actual_len(ex);
3154         ee_pblock = ext4_ext_pblock(ex);
3155         return ext4_issue_zeroout(inode, le32_to_cpu(ex->ee_block), ee_pblock,
3156                                   ee_len);
3157 }
3158
3159 /*
3160  * ext4_split_extent_at() splits an extent at given block.
3161  *
3162  * @handle: the journal handle
3163  * @inode: the file inode
3164  * @path: the path to the extent
3165  * @split: the logical block where the extent is splitted.
3166  * @split_flags: indicates if the extent could be zeroout if split fails, and
3167  *               the states(init or unwritten) of new extents.
3168  * @flags: flags used to insert new extent to extent tree.
3169  *
3170  *
3171  * Splits extent [a, b] into two extents [a, @split) and [@split, b], states
3172  * of which are determined by split_flag.
3173  *
3174  * There are two cases:
3175  *  a> the extent are splitted into two extent.
3176  *  b> split is not needed, and just mark the extent.
3177  *
3178  * Return an extent path pointer on success, or an error pointer on failure.
3179  */
3180 static struct ext4_ext_path *ext4_split_extent_at(handle_t *handle,
3181                                                   struct inode *inode,
3182                                                   struct ext4_ext_path *path,
3183                                                   ext4_lblk_t split,
3184                                                   int split_flag, int flags)
3185 {
3186         ext4_fsblk_t newblock;
3187         ext4_lblk_t ee_block;
3188         struct ext4_extent *ex, newex, orig_ex, zero_ex;
3189         struct ext4_extent *ex2 = NULL;
3190         unsigned int ee_len, depth;
3191         int err = 0;
3192
3193         BUG_ON((split_flag & (EXT4_EXT_DATA_VALID1 | EXT4_EXT_DATA_VALID2)) ==
3194                (EXT4_EXT_DATA_VALID1 | EXT4_EXT_DATA_VALID2));
3195
3196         ext_debug(inode, "logical block %llu\n", (unsigned long long)split);
3197
3198         ext4_ext_show_leaf(inode, path);
3199
3200         depth = ext_depth(inode);
3201         ex = path[depth].p_ext;
3202         ee_block = le32_to_cpu(ex->ee_block);
3203         ee_len = ext4_ext_get_actual_len(ex);
3204         newblock = split - ee_block + ext4_ext_pblock(ex);
3205
3206         BUG_ON(split < ee_block || split >= (ee_block + ee_len));
3207         BUG_ON(!ext4_ext_is_unwritten(ex) &&
3208                split_flag & (EXT4_EXT_MAY_ZEROOUT |
3209                              EXT4_EXT_MARK_UNWRIT1 |
3210                              EXT4_EXT_MARK_UNWRIT2));
3211
3212         err = ext4_ext_get_access(handle, inode, path + depth);
3213         if (err)
3214                 goto out;
3215
3216         if (split == ee_block) {
3217                 /*
3218                  * case b: block @split is the block that the extent begins with
3219                  * then we just change the state of the extent, and splitting
3220                  * is not needed.
3221                  */
3222                 if (split_flag & EXT4_EXT_MARK_UNWRIT2)
3223                         ext4_ext_mark_unwritten(ex);
3224                 else
3225                         ext4_ext_mark_initialized(ex);
3226
3227                 if (!(flags & EXT4_GET_BLOCKS_PRE_IO))
3228                         ext4_ext_try_to_merge(handle, inode, path, ex);
3229
3230                 err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3231                 goto out;
3232         }
3233
3234         /* case a */
3235         memcpy(&orig_ex, ex, sizeof(orig_ex));
3236         ex->ee_len = cpu_to_le16(split - ee_block);
3237         if (split_flag & EXT4_EXT_MARK_UNWRIT1)
3238                 ext4_ext_mark_unwritten(ex);
3239
3240         /*
3241          * path may lead to new leaf, not to original leaf any more
3242          * after ext4_ext_insert_extent() returns,
3243          */
3244         err = ext4_ext_dirty(handle, inode, path + depth);
3245         if (err)
3246                 goto fix_extent_len;
3247
3248         ex2 = &newex;
3249         ex2->ee_block = cpu_to_le32(split);
3250         ex2->ee_len   = cpu_to_le16(ee_len - (split - ee_block));
3251         ext4_ext_store_pblock(ex2, newblock);
3252         if (split_flag & EXT4_EXT_MARK_UNWRIT2)
3253                 ext4_ext_mark_unwritten(ex2);
3254
3255         path = ext4_ext_insert_extent(handle, inode, path, &newex, flags);
3256         if (!IS_ERR(path))
3257                 goto out;
3258
3259         err = PTR_ERR(path);
3260         if (err != -ENOSPC && err != -EDQUOT && err != -ENOMEM)
3261                 return path;
3262
3263         /*
3264          * Get a new path to try to zeroout or fix the extent length.
3265          * Using EXT4_EX_NOFAIL guarantees that ext4_find_extent()
3266          * will not return -ENOMEM, otherwise -ENOMEM will cause a
3267          * retry in do_writepages(), and a WARN_ON may be triggered
3268          * in ext4_da_update_reserve_space() due to an incorrect
3269          * ee_len causing the i_reserved_data_blocks exception.
3270          */
3271         path = ext4_find_extent(inode, ee_block, NULL, flags | EXT4_EX_NOFAIL);
3272         if (IS_ERR(path)) {
3273                 EXT4_ERROR_INODE(inode, "Failed split extent on %u, err %ld",
3274                                  split, PTR_ERR(path));
3275                 return path;
3276         }
3277         depth = ext_depth(inode);
3278         ex = path[depth].p_ext;
3279
3280         if (EXT4_EXT_MAY_ZEROOUT & split_flag) {
3281                 if (split_flag & (EXT4_EXT_DATA_VALID1|EXT4_EXT_DATA_VALID2)) {
3282                         if (split_flag & EXT4_EXT_DATA_VALID1) {
3283                                 err = ext4_ext_zeroout(inode, ex2);
3284                                 zero_ex.ee_block = ex2->ee_block;
3285                                 zero_ex.ee_len = cpu_to_le16(
3286                                                 ext4_ext_get_actual_len(ex2));
3287                                 ext4_ext_store_pblock(&zero_ex,
3288                                                       ext4_ext_pblock(ex2));
3289                         } else {
3290                                 err = ext4_ext_zeroout(inode, ex);
3291                                 zero_ex.ee_block = ex->ee_block;
3292                                 zero_ex.ee_len = cpu_to_le16(
3293                                                 ext4_ext_get_actual_len(ex));
3294                                 ext4_ext_store_pblock(&zero_ex,
3295                                                       ext4_ext_pblock(ex));
3296                         }
3297                 } else {
3298                         err = ext4_ext_zeroout(inode, &orig_ex);
3299                         zero_ex.ee_block = orig_ex.ee_block;
3300                         zero_ex.ee_len = cpu_to_le16(
3301                                                 ext4_ext_get_actual_len(&orig_ex));
3302                         ext4_ext_store_pblock(&zero_ex,
3303                                               ext4_ext_pblock(&orig_ex));
3304                 }
3305
3306                 if (!err) {
3307                         /* update the extent length and mark as initialized */
3308                         ex->ee_len = cpu_to_le16(ee_len);
3309                         ext4_ext_try_to_merge(handle, inode, path, ex);
3310                         err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3311                         if (!err)
3312                                 /* update extent status tree */
3313                                 ext4_zeroout_es(inode, &zero_ex);
3314                         /* If we failed at this point, we don't know in which
3315                          * state the extent tree exactly is so don't try to fix
3316                          * length of the original extent as it may do even more
3317                          * damage.
3318                          */
3319                         goto out;
3320                 }
3321         }
3322
3323 fix_extent_len:
3324         ex->ee_len = orig_ex.ee_len;
3325         /*
3326          * Ignore ext4_ext_dirty return value since we are already in error path
3327          * and err is a non-zero error code.
3328          */
3329         ext4_ext_dirty(handle, inode, path + path->p_depth);
3330 out:
3331         if (err) {
3332                 ext4_free_ext_path(path);
3333                 path = ERR_PTR(err);
3334         }
3335         ext4_ext_show_leaf(inode, path);
3336         return path;
3337 }
3338
3339 /*
3340  * ext4_split_extent() splits an extent and mark extent which is covered
3341  * by @map as split_flags indicates
3342  *
3343  * It may result in splitting the extent into multiple extents (up to three)
3344  * There are three possibilities:
3345  *   a> There is no split required
3346  *   b> Splits in two extents: Split is happening at either end of the extent
3347  *   c> Splits in three extents: Somone is splitting in middle of the extent
3348  *
3349  */
3350 static struct ext4_ext_path *ext4_split_extent(handle_t *handle,
3351                                                struct inode *inode,
3352                                                struct ext4_ext_path *path,
3353                                                struct ext4_map_blocks *map,
3354                                                int split_flag, int flags,
3355                                                unsigned int *allocated)
3356 {
3357         ext4_lblk_t ee_block;
3358         struct ext4_extent *ex;
3359         unsigned int ee_len, depth;
3360         int unwritten;
3361         int split_flag1, flags1;
3362
3363         depth = ext_depth(inode);
3364         ex = path[depth].p_ext;
3365         ee_block = le32_to_cpu(ex->ee_block);
3366         ee_len = ext4_ext_get_actual_len(ex);
3367         unwritten = ext4_ext_is_unwritten(ex);
3368
3369         if (map->m_lblk + map->m_len < ee_block + ee_len) {
3370                 split_flag1 = split_flag & EXT4_EXT_MAY_ZEROOUT;
3371                 flags1 = flags | EXT4_GET_BLOCKS_PRE_IO;
3372                 if (unwritten)
3373                         split_flag1 |= EXT4_EXT_MARK_UNWRIT1 |
3374                                        EXT4_EXT_MARK_UNWRIT2;
3375                 if (split_flag & EXT4_EXT_DATA_VALID2)
3376                         split_flag1 |= EXT4_EXT_DATA_VALID1;
3377                 path = ext4_split_extent_at(handle, inode, path,
3378                                 map->m_lblk + map->m_len, split_flag1, flags1);
3379                 if (IS_ERR(path))
3380                         return path;
3381                 /*
3382                  * Update path is required because previous ext4_split_extent_at
3383                  * may result in split of original leaf or extent zeroout.
3384                  */
3385                 path = ext4_find_extent(inode, map->m_lblk, path, flags);
3386                 if (IS_ERR(path))
3387                         return path;
3388                 depth = ext_depth(inode);
3389                 ex = path[depth].p_ext;
3390                 if (!ex) {
3391                         EXT4_ERROR_INODE(inode, "unexpected hole at %lu",
3392                                         (unsigned long) map->m_lblk);
3393                         ext4_free_ext_path(path);
3394                         return ERR_PTR(-EFSCORRUPTED);
3395                 }
3396                 unwritten = ext4_ext_is_unwritten(ex);
3397         }
3398
3399         if (map->m_lblk >= ee_block) {
3400                 split_flag1 = split_flag & EXT4_EXT_DATA_VALID2;
3401                 if (unwritten) {
3402                         split_flag1 |= EXT4_EXT_MARK_UNWRIT1;
3403                         split_flag1 |= split_flag & (EXT4_EXT_MAY_ZEROOUT |
3404                                                      EXT4_EXT_MARK_UNWRIT2);
3405                 }
3406                 path = ext4_split_extent_at(handle, inode, path,
3407                                 map->m_lblk, split_flag1, flags);
3408                 if (IS_ERR(path))
3409                         return path;
3410         }
3411
3412         if (allocated) {
3413                 if (map->m_lblk + map->m_len > ee_block + ee_len)
3414                         *allocated = ee_len - (map->m_lblk - ee_block);
3415                 else
3416                         *allocated = map->m_len;
3417         }
3418         ext4_ext_show_leaf(inode, path);
3419         return path;
3420 }
3421
3422 /*
3423  * This function is called by ext4_ext_map_blocks() if someone tries to write
3424  * to an unwritten extent. It may result in splitting the unwritten
3425  * extent into multiple extents (up to three - one initialized and two
3426  * unwritten).
3427  * There are three possibilities:
3428  *   a> There is no split required: Entire extent should be initialized
3429  *   b> Splits in two extents: Write is happening at either end of the extent
3430  *   c> Splits in three extents: Somone is writing in middle of the extent
3431  *
3432  * Pre-conditions:
3433  *  - The extent pointed to by 'path' is unwritten.
3434  *  - The extent pointed to by 'path' contains a superset
3435  *    of the logical span [map->m_lblk, map->m_lblk + map->m_len).
3436  *
3437  * Post-conditions on success:
3438  *  - the returned value is the number of blocks beyond map->l_lblk
3439  *    that are allocated and initialized.
3440  *    It is guaranteed to be >= map->m_len.
3441  */
3442 static struct ext4_ext_path *
3443 ext4_ext_convert_to_initialized(handle_t *handle, struct inode *inode,
3444                         struct ext4_map_blocks *map, struct ext4_ext_path *path,
3445                         int flags, unsigned int *allocated)
3446 {
3447         struct ext4_sb_info *sbi;
3448         struct ext4_extent_header *eh;
3449         struct ext4_map_blocks split_map;
3450         struct ext4_extent zero_ex1, zero_ex2;
3451         struct ext4_extent *ex, *abut_ex;
3452         ext4_lblk_t ee_block, eof_block;
3453         unsigned int ee_len, depth, map_len = map->m_len;
3454         int err = 0;
3455         int split_flag = EXT4_EXT_DATA_VALID2;
3456         unsigned int max_zeroout = 0;
3457
3458         ext_debug(inode, "logical block %llu, max_blocks %u\n",
3459                   (unsigned long long)map->m_lblk, map_len);
3460
3461         sbi = EXT4_SB(inode->i_sb);
3462         eof_block = (EXT4_I(inode)->i_disksize + inode->i_sb->s_blocksize - 1)
3463                         >> inode->i_sb->s_blocksize_bits;
3464         if (eof_block < map->m_lblk + map_len)
3465                 eof_block = map->m_lblk + map_len;
3466
3467         depth = ext_depth(inode);
3468         eh = path[depth].p_hdr;
3469         ex = path[depth].p_ext;
3470         ee_block = le32_to_cpu(ex->ee_block);
3471         ee_len = ext4_ext_get_actual_len(ex);
3472         zero_ex1.ee_len = 0;
3473         zero_ex2.ee_len = 0;
3474
3475         trace_ext4_ext_convert_to_initialized_enter(inode, map, ex);
3476
3477         /* Pre-conditions */
3478         BUG_ON(!ext4_ext_is_unwritten(ex));
3479         BUG_ON(!in_range(map->m_lblk, ee_block, ee_len));
3480
3481         /*
3482          * Attempt to transfer newly initialized blocks from the currently
3483          * unwritten extent to its neighbor. This is much cheaper
3484          * than an insertion followed by a merge as those involve costly
3485          * memmove() calls. Transferring to the left is the common case in
3486          * steady state for workloads doing fallocate(FALLOC_FL_KEEP_SIZE)
3487          * followed by append writes.
3488          *
3489          * Limitations of the current logic:
3490          *  - L1: we do not deal with writes covering the whole extent.
3491          *    This would require removing the extent if the transfer
3492          *    is possible.
3493          *  - L2: we only attempt to merge with an extent stored in the
3494          *    same extent tree node.
3495          */
3496         *allocated = 0;
3497         if ((map->m_lblk == ee_block) &&
3498                 /* See if we can merge left */
3499                 (map_len < ee_len) &&           /*L1*/
3500                 (ex > EXT_FIRST_EXTENT(eh))) {  /*L2*/
3501                 ext4_lblk_t prev_lblk;
3502                 ext4_fsblk_t prev_pblk, ee_pblk;
3503                 unsigned int prev_len;
3504
3505                 abut_ex = ex - 1;
3506                 prev_lblk = le32_to_cpu(abut_ex->ee_block);
3507                 prev_len = ext4_ext_get_actual_len(abut_ex);
3508                 prev_pblk = ext4_ext_pblock(abut_ex);
3509                 ee_pblk = ext4_ext_pblock(ex);
3510
3511                 /*
3512                  * A transfer of blocks from 'ex' to 'abut_ex' is allowed
3513                  * upon those conditions:
3514                  * - C1: abut_ex is initialized,
3515                  * - C2: abut_ex is logically abutting ex,
3516                  * - C3: abut_ex is physically abutting ex,
3517                  * - C4: abut_ex can receive the additional blocks without
3518                  *   overflowing the (initialized) length limit.
3519                  */
3520                 if ((!ext4_ext_is_unwritten(abut_ex)) &&                /*C1*/
3521                         ((prev_lblk + prev_len) == ee_block) &&         /*C2*/
3522                         ((prev_pblk + prev_len) == ee_pblk) &&          /*C3*/
3523                         (prev_len < (EXT_INIT_MAX_LEN - map_len))) {    /*C4*/
3524                         err = ext4_ext_get_access(handle, inode, path + depth);
3525                         if (err)
3526                                 goto errout;
3527
3528                         trace_ext4_ext_convert_to_initialized_fastpath(inode,
3529                                 map, ex, abut_ex);
3530
3531                         /* Shift the start of ex by 'map_len' blocks */
3532                         ex->ee_block = cpu_to_le32(ee_block + map_len);
3533                         ext4_ext_store_pblock(ex, ee_pblk + map_len);
3534                         ex->ee_len = cpu_to_le16(ee_len - map_len);
3535                         ext4_ext_mark_unwritten(ex); /* Restore the flag */
3536
3537                         /* Extend abut_ex by 'map_len' blocks */
3538                         abut_ex->ee_len = cpu_to_le16(prev_len + map_len);
3539
3540                         /* Result: number of initialized blocks past m_lblk */
3541                         *allocated = map_len;
3542                 }
3543         } else if (((map->m_lblk + map_len) == (ee_block + ee_len)) &&
3544                    (map_len < ee_len) &&        /*L1*/
3545                    ex < EXT_LAST_EXTENT(eh)) {  /*L2*/
3546                 /* See if we can merge right */
3547                 ext4_lblk_t next_lblk;
3548                 ext4_fsblk_t next_pblk, ee_pblk;
3549                 unsigned int next_len;
3550
3551                 abut_ex = ex + 1;
3552                 next_lblk = le32_to_cpu(abut_ex->ee_block);
3553                 next_len = ext4_ext_get_actual_len(abut_ex);
3554                 next_pblk = ext4_ext_pblock(abut_ex);
3555                 ee_pblk = ext4_ext_pblock(ex);
3556
3557                 /*
3558                  * A transfer of blocks from 'ex' to 'abut_ex' is allowed
3559                  * upon those conditions:
3560                  * - C1: abut_ex is initialized,
3561                  * - C2: abut_ex is logically abutting ex,
3562                  * - C3: abut_ex is physically abutting ex,
3563                  * - C4: abut_ex can receive the additional blocks without
3564                  *   overflowing the (initialized) length limit.
3565                  */
3566                 if ((!ext4_ext_is_unwritten(abut_ex)) &&                /*C1*/
3567                     ((map->m_lblk + map_len) == next_lblk) &&           /*C2*/
3568                     ((ee_pblk + ee_len) == next_pblk) &&                /*C3*/
3569                     (next_len < (EXT_INIT_MAX_LEN - map_len))) {        /*C4*/
3570                         err = ext4_ext_get_access(handle, inode, path + depth);
3571                         if (err)
3572                                 goto errout;
3573
3574                         trace_ext4_ext_convert_to_initialized_fastpath(inode,
3575                                 map, ex, abut_ex);
3576
3577                         /* Shift the start of abut_ex by 'map_len' blocks */
3578                         abut_ex->ee_block = cpu_to_le32(next_lblk - map_len);
3579                         ext4_ext_store_pblock(abut_ex, next_pblk - map_len);
3580                         ex->ee_len = cpu_to_le16(ee_len - map_len);
3581                         ext4_ext_mark_unwritten(ex); /* Restore the flag */
3582
3583                         /* Extend abut_ex by 'map_len' blocks */
3584                         abut_ex->ee_len = cpu_to_le16(next_len + map_len);
3585
3586                         /* Result: number of initialized blocks past m_lblk */
3587                         *allocated = map_len;
3588                 }
3589         }
3590         if (*allocated) {
3591                 /* Mark the block containing both extents as dirty */
3592                 err = ext4_ext_dirty(handle, inode, path + depth);
3593
3594                 /* Update path to point to the right extent */
3595                 path[depth].p_ext = abut_ex;
3596                 if (err)
3597                         goto errout;
3598                 goto out;
3599         } else
3600                 *allocated = ee_len - (map->m_lblk - ee_block);
3601
3602         WARN_ON(map->m_lblk < ee_block);
3603         /*
3604          * It is safe to convert extent to initialized via explicit
3605          * zeroout only if extent is fully inside i_size or new_size.
3606          */
3607         split_flag |= ee_block + ee_len <= eof_block ? EXT4_EXT_MAY_ZEROOUT : 0;
3608
3609         if (EXT4_EXT_MAY_ZEROOUT & split_flag)
3610                 max_zeroout = sbi->s_extent_max_zeroout_kb >>
3611                         (inode->i_sb->s_blocksize_bits - 10);
3612
3613         /*
3614          * five cases:
3615          * 1. split the extent into three extents.
3616          * 2. split the extent into two extents, zeroout the head of the first
3617          *    extent.
3618          * 3. split the extent into two extents, zeroout the tail of the second
3619          *    extent.
3620          * 4. split the extent into two extents with out zeroout.
3621          * 5. no splitting needed, just possibly zeroout the head and / or the
3622          *    tail of the extent.
3623          */
3624         split_map.m_lblk = map->m_lblk;
3625         split_map.m_len = map->m_len;
3626
3627         if (max_zeroout && (*allocated > split_map.m_len)) {
3628                 if (*allocated <= max_zeroout) {
3629                         /* case 3 or 5 */
3630                         zero_ex1.ee_block =
3631                                  cpu_to_le32(split_map.m_lblk +
3632                                              split_map.m_len);
3633                         zero_ex1.ee_len =
3634                                 cpu_to_le16(*allocated - split_map.m_len);
3635                         ext4_ext_store_pblock(&zero_ex1,
3636                                 ext4_ext_pblock(ex) + split_map.m_lblk +
3637                                 split_map.m_len - ee_block);
3638                         err = ext4_ext_zeroout(inode, &zero_ex1);
3639                         if (err)
3640                                 goto fallback;
3641                         split_map.m_len = *allocated;
3642                 }
3643                 if (split_map.m_lblk - ee_block + split_map.m_len <
3644                                                                 max_zeroout) {
3645                         /* case 2 or 5 */
3646                         if (split_map.m_lblk != ee_block) {
3647                                 zero_ex2.ee_block = ex->ee_block;
3648                                 zero_ex2.ee_len = cpu_to_le16(split_map.m_lblk -
3649                                                         ee_block);
3650                                 ext4_ext_store_pblock(&zero_ex2,
3651                                                       ext4_ext_pblock(ex));
3652                                 err = ext4_ext_zeroout(inode, &zero_ex2);
3653                                 if (err)
3654                                         goto fallback;
3655                         }
3656
3657                         split_map.m_len += split_map.m_lblk - ee_block;
3658                         split_map.m_lblk = ee_block;
3659                         *allocated = map->m_len;
3660                 }
3661         }
3662
3663 fallback:
3664         path = ext4_split_extent(handle, inode, path, &split_map, split_flag,
3665                                  flags, NULL);
3666         if (IS_ERR(path))
3667                 return path;
3668 out:
3669         /* If we have gotten a failure, don't zero out status tree */
3670         ext4_zeroout_es(inode, &zero_ex1);
3671         ext4_zeroout_es(inode, &zero_ex2);
3672         return path;
3673
3674 errout:
3675         ext4_free_ext_path(path);
3676         return ERR_PTR(err);
3677 }
3678
3679 /*
3680  * This function is called by ext4_ext_map_blocks() from
3681  * ext4_get_blocks_dio_write() when DIO to write
3682  * to an unwritten extent.
3683  *
3684  * Writing to an unwritten extent may result in splitting the unwritten
3685  * extent into multiple initialized/unwritten extents (up to three)
3686  * There are three possibilities:
3687  *   a> There is no split required: Entire extent should be unwritten
3688  *   b> Splits in two extents: Write is happening at either end of the extent
3689  *   c> Splits in three extents: Somone is writing in middle of the extent
3690  *
3691  * This works the same way in the case of initialized -> unwritten conversion.
3692  *
3693  * One of more index blocks maybe needed if the extent tree grow after
3694  * the unwritten extent split. To prevent ENOSPC occur at the IO
3695  * complete, we need to split the unwritten extent before DIO submit
3696  * the IO. The unwritten extent called at this time will be split
3697  * into three unwritten extent(at most). After IO complete, the part
3698  * being filled will be convert to initialized by the end_io callback function
3699  * via ext4_convert_unwritten_extents().
3700  *
3701  * The size of unwritten extent to be written is passed to the caller via the
3702  * allocated pointer. Return an extent path pointer on success, or an error
3703  * pointer on failure.
3704  */
3705 static struct ext4_ext_path *ext4_split_convert_extents(handle_t *handle,
3706                                         struct inode *inode,
3707                                         struct ext4_map_blocks *map,
3708                                         struct ext4_ext_path *path,
3709                                         int flags, unsigned int *allocated)
3710 {
3711         ext4_lblk_t eof_block;
3712         ext4_lblk_t ee_block;
3713         struct ext4_extent *ex;
3714         unsigned int ee_len;
3715         int split_flag = 0, depth;
3716
3717         ext_debug(inode, "logical block %llu, max_blocks %u\n",
3718                   (unsigned long long)map->m_lblk, map->m_len);
3719
3720         eof_block = (EXT4_I(inode)->i_disksize + inode->i_sb->s_blocksize - 1)
3721                         >> inode->i_sb->s_blocksize_bits;
3722         if (eof_block < map->m_lblk + map->m_len)
3723                 eof_block = map->m_lblk + map->m_len;
3724         /*
3725          * It is safe to convert extent to initialized via explicit
3726          * zeroout only if extent is fully inside i_size or new_size.
3727          */
3728         depth = ext_depth(inode);
3729         ex = path[depth].p_ext;
3730         ee_block = le32_to_cpu(ex->ee_block);
3731         ee_len = ext4_ext_get_actual_len(ex);
3732
3733         /* Convert to unwritten */
3734         if (flags & EXT4_GET_BLOCKS_CONVERT_UNWRITTEN) {
3735                 split_flag |= EXT4_EXT_DATA_VALID1;
3736         /* Convert to initialized */
3737         } else if (flags & EXT4_GET_BLOCKS_CONVERT) {
3738                 split_flag |= ee_block + ee_len <= eof_block ?
3739                               EXT4_EXT_MAY_ZEROOUT : 0;
3740                 split_flag |= (EXT4_EXT_MARK_UNWRIT2 | EXT4_EXT_DATA_VALID2);
3741         }
3742         flags |= EXT4_GET_BLOCKS_PRE_IO;
3743         return ext4_split_extent(handle, inode, path, map, split_flag, flags,
3744                                  allocated);
3745 }
3746
3747 static struct ext4_ext_path *
3748 ext4_convert_unwritten_extents_endio(handle_t *handle, struct inode *inode,
3749                                      struct ext4_map_blocks *map,
3750                                      struct ext4_ext_path *path)
3751 {
3752         struct ext4_extent *ex;
3753         ext4_lblk_t ee_block;
3754         unsigned int ee_len;
3755         int depth;
3756         int err = 0;
3757
3758         depth = ext_depth(inode);
3759         ex = path[depth].p_ext;
3760         ee_block = le32_to_cpu(ex->ee_block);
3761         ee_len = ext4_ext_get_actual_len(ex);
3762
3763         ext_debug(inode, "logical block %llu, max_blocks %u\n",
3764                   (unsigned long long)ee_block, ee_len);
3765
3766         /* If extent is larger than requested it is a clear sign that we still
3767          * have some extent state machine issues left. So extent_split is still
3768          * required.
3769          * TODO: Once all related issues will be fixed this situation should be
3770          * illegal.
3771          */
3772         if (ee_block != map->m_lblk || ee_len > map->m_len) {
3773 #ifdef CONFIG_EXT4_DEBUG
3774                 ext4_warning(inode->i_sb, "Inode (%ld) finished: extent logical block %llu,"
3775                              " len %u; IO logical block %llu, len %u",
3776                              inode->i_ino, (unsigned long long)ee_block, ee_len,
3777                              (unsigned long long)map->m_lblk, map->m_len);
3778 #endif
3779                 path = ext4_split_convert_extents(handle, inode, map, path,
3780                                                 EXT4_GET_BLOCKS_CONVERT, NULL);
3781                 if (IS_ERR(path))
3782                         return path;
3783
3784                 path = ext4_find_extent(inode, map->m_lblk, path, 0);
3785                 if (IS_ERR(path))
3786                         return path;
3787                 depth = ext_depth(inode);
3788                 ex = path[depth].p_ext;
3789         }
3790
3791         err = ext4_ext_get_access(handle, inode, path + depth);
3792         if (err)
3793                 goto errout;
3794         /* first mark the extent as initialized */
3795         ext4_ext_mark_initialized(ex);
3796
3797         /* note: ext4_ext_correct_indexes() isn't needed here because
3798          * borders are not changed
3799          */
3800         ext4_ext_try_to_merge(handle, inode, path, ex);
3801
3802         /* Mark modified extent as dirty */
3803         err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3804         if (err)
3805                 goto errout;
3806
3807         ext4_ext_show_leaf(inode, path);
3808         return path;
3809
3810 errout:
3811         ext4_free_ext_path(path);
3812         return ERR_PTR(err);
3813 }
3814
3815 static struct ext4_ext_path *
3816 convert_initialized_extent(handle_t *handle, struct inode *inode,
3817                            struct ext4_map_blocks *map,
3818                            struct ext4_ext_path *path,
3819                            unsigned int *allocated)
3820 {
3821         struct ext4_extent *ex;
3822         ext4_lblk_t ee_block;
3823         unsigned int ee_len;
3824         int depth;
3825         int err = 0;
3826
3827         /*
3828          * Make sure that the extent is no bigger than we support with
3829          * unwritten extent
3830          */
3831         if (map->m_len > EXT_UNWRITTEN_MAX_LEN)
3832                 map->m_len = EXT_UNWRITTEN_MAX_LEN / 2;
3833
3834         depth = ext_depth(inode);
3835         ex = path[depth].p_ext;
3836         ee_block = le32_to_cpu(ex->ee_block);
3837         ee_len = ext4_ext_get_actual_len(ex);
3838
3839         ext_debug(inode, "logical block %llu, max_blocks %u\n",
3840                   (unsigned long long)ee_block, ee_len);
3841
3842         if (ee_block != map->m_lblk || ee_len > map->m_len) {
3843                 path = ext4_split_convert_extents(handle, inode, map, path,
3844                                 EXT4_GET_BLOCKS_CONVERT_UNWRITTEN, NULL);
3845                 if (IS_ERR(path))
3846                         return path;
3847
3848                 path = ext4_find_extent(inode, map->m_lblk, path, 0);
3849                 if (IS_ERR(path))
3850                         return path;
3851                 depth = ext_depth(inode);
3852                 ex = path[depth].p_ext;
3853                 if (!ex) {
3854                         EXT4_ERROR_INODE(inode, "unexpected hole at %lu",
3855                                          (unsigned long) map->m_lblk);
3856                         err = -EFSCORRUPTED;
3857                         goto errout;
3858                 }
3859         }
3860
3861         err = ext4_ext_get_access(handle, inode, path + depth);
3862         if (err)
3863                 goto errout;
3864         /* first mark the extent as unwritten */
3865         ext4_ext_mark_unwritten(ex);
3866
3867         /* note: ext4_ext_correct_indexes() isn't needed here because
3868          * borders are not changed
3869          */
3870         ext4_ext_try_to_merge(handle, inode, path, ex);
3871
3872         /* Mark modified extent as dirty */
3873         err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3874         if (err)
3875                 goto errout;
3876         ext4_ext_show_leaf(inode, path);
3877
3878         ext4_update_inode_fsync_trans(handle, inode, 1);
3879
3880         map->m_flags |= EXT4_MAP_UNWRITTEN;
3881         if (*allocated > map->m_len)
3882                 *allocated = map->m_len;
3883         map->m_len = *allocated;
3884         return path;
3885
3886 errout:
3887         ext4_free_ext_path(path);
3888         return ERR_PTR(err);
3889 }
3890
3891 static struct ext4_ext_path *
3892 ext4_ext_handle_unwritten_extents(handle_t *handle, struct inode *inode,
3893                         struct ext4_map_blocks *map,
3894                         struct ext4_ext_path *path, int flags,
3895                         unsigned int *allocated, ext4_fsblk_t newblock)
3896 {
3897         int err = 0;
3898
3899         ext_debug(inode, "logical block %llu, max_blocks %u, flags 0x%x, allocated %u\n",
3900                   (unsigned long long)map->m_lblk, map->m_len, flags,
3901                   *allocated);
3902         ext4_ext_show_leaf(inode, path);
3903
3904         /*
3905          * When writing into unwritten space, we should not fail to
3906          * allocate metadata blocks for the new extent block if needed.
3907          */
3908         flags |= EXT4_GET_BLOCKS_METADATA_NOFAIL;
3909
3910         trace_ext4_ext_handle_unwritten_extents(inode, map, flags,
3911                                                 *allocated, newblock);
3912
3913         /* get_block() before submitting IO, split the extent */
3914         if (flags & EXT4_GET_BLOCKS_PRE_IO) {
3915                 path = ext4_split_convert_extents(handle, inode, map, path,
3916                                 flags | EXT4_GET_BLOCKS_CONVERT, allocated);
3917                 if (IS_ERR(path))
3918                         return path;
3919                 /*
3920                  * shouldn't get a 0 allocated when splitting an extent unless
3921                  * m_len is 0 (bug) or extent has been corrupted
3922                  */
3923                 if (unlikely(*allocated == 0)) {
3924                         EXT4_ERROR_INODE(inode,
3925                                          "unexpected allocated == 0, m_len = %u",
3926                                          map->m_len);
3927                         err = -EFSCORRUPTED;
3928                         goto errout;
3929                 }
3930                 map->m_flags |= EXT4_MAP_UNWRITTEN;
3931                 goto out;
3932         }
3933         /* IO end_io complete, convert the filled extent to written */
3934         if (flags & EXT4_GET_BLOCKS_CONVERT) {
3935                 path = ext4_convert_unwritten_extents_endio(handle, inode,
3936                                                             map, path);
3937                 if (IS_ERR(path))
3938                         return path;
3939                 ext4_update_inode_fsync_trans(handle, inode, 1);
3940                 goto map_out;
3941         }
3942         /* buffered IO cases */
3943         /*
3944          * repeat fallocate creation request
3945          * we already have an unwritten extent
3946          */
3947         if (flags & EXT4_GET_BLOCKS_UNWRIT_EXT) {
3948                 map->m_flags |= EXT4_MAP_UNWRITTEN;
3949                 goto map_out;
3950         }
3951
3952         /* buffered READ or buffered write_begin() lookup */
3953         if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
3954                 /*
3955                  * We have blocks reserved already.  We
3956                  * return allocated blocks so that delalloc
3957                  * won't do block reservation for us.  But
3958                  * the buffer head will be unmapped so that
3959                  * a read from the block returns 0s.
3960                  */
3961                 map->m_flags |= EXT4_MAP_UNWRITTEN;
3962                 goto out1;
3963         }
3964
3965         /*
3966          * Default case when (flags & EXT4_GET_BLOCKS_CREATE) == 1.
3967          * For buffered writes, at writepage time, etc.  Convert a
3968          * discovered unwritten extent to written.
3969          */
3970         path = ext4_ext_convert_to_initialized(handle, inode, map, path,
3971                                                flags, allocated);
3972         if (IS_ERR(path))
3973                 return path;
3974         ext4_update_inode_fsync_trans(handle, inode, 1);
3975         /*
3976          * shouldn't get a 0 allocated when converting an unwritten extent
3977          * unless m_len is 0 (bug) or extent has been corrupted
3978          */
3979         if (unlikely(*allocated == 0)) {
3980                 EXT4_ERROR_INODE(inode, "unexpected allocated == 0, m_len = %u",
3981                                  map->m_len);
3982                 err = -EFSCORRUPTED;
3983                 goto errout;
3984         }
3985
3986 out:
3987         map->m_flags |= EXT4_MAP_NEW;
3988 map_out:
3989         map->m_flags |= EXT4_MAP_MAPPED;
3990 out1:
3991         map->m_pblk = newblock;
3992         if (*allocated > map->m_len)
3993                 *allocated = map->m_len;
3994         map->m_len = *allocated;
3995         ext4_ext_show_leaf(inode, path);
3996         return path;
3997
3998 errout:
3999         ext4_free_ext_path(path);
4000         return ERR_PTR(err);
4001 }
4002
4003 /*
4004  * get_implied_cluster_alloc - check to see if the requested
4005  * allocation (in the map structure) overlaps with a cluster already
4006  * allocated in an extent.
4007  *      @sb     The filesystem superblock structure
4008  *      @map    The requested lblk->pblk mapping
4009  *      @ex     The extent structure which might contain an implied
4010  *                      cluster allocation
4011  *
4012  * This function is called by ext4_ext_map_blocks() after we failed to
4013  * find blocks that were already in the inode's extent tree.  Hence,
4014  * we know that the beginning of the requested region cannot overlap
4015  * the extent from the inode's extent tree.  There are three cases we
4016  * want to catch.  The first is this case:
4017  *
4018  *               |--- cluster # N--|
4019  *    |--- extent ---|  |---- requested region ---|
4020  *                      |==========|
4021  *
4022  * The second case that we need to test for is this one:
4023  *
4024  *   |--------- cluster # N ----------------|
4025  *         |--- requested region --|   |------- extent ----|
4026  *         |=======================|
4027  *
4028  * The third case is when the requested region lies between two extents
4029  * within the same cluster:
4030  *          |------------- cluster # N-------------|
4031  * |----- ex -----|                  |---- ex_right ----|
4032  *                  |------ requested region ------|
4033  *                  |================|
4034  *
4035  * In each of the above cases, we need to set the map->m_pblk and
4036  * map->m_len so it corresponds to the return the extent labelled as
4037  * "|====|" from cluster #N, since it is already in use for data in
4038  * cluster EXT4_B2C(sbi, map->m_lblk).  We will then return 1 to
4039  * signal to ext4_ext_map_blocks() that map->m_pblk should be treated
4040  * as a new "allocated" block region.  Otherwise, we will return 0 and
4041  * ext4_ext_map_blocks() will then allocate one or more new clusters
4042  * by calling ext4_mb_new_blocks().
4043  */
4044 static int get_implied_cluster_alloc(struct super_block *sb,
4045                                      struct ext4_map_blocks *map,
4046                                      struct ext4_extent *ex,
4047                                      struct ext4_ext_path *path)
4048 {
4049         struct ext4_sb_info *sbi = EXT4_SB(sb);
4050         ext4_lblk_t c_offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
4051         ext4_lblk_t ex_cluster_start, ex_cluster_end;
4052         ext4_lblk_t rr_cluster_start;
4053         ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block);
4054         ext4_fsblk_t ee_start = ext4_ext_pblock(ex);
4055         unsigned short ee_len = ext4_ext_get_actual_len(ex);
4056
4057         /* The extent passed in that we are trying to match */
4058         ex_cluster_start = EXT4_B2C(sbi, ee_block);
4059         ex_cluster_end = EXT4_B2C(sbi, ee_block + ee_len - 1);
4060
4061         /* The requested region passed into ext4_map_blocks() */
4062         rr_cluster_start = EXT4_B2C(sbi, map->m_lblk);
4063
4064         if ((rr_cluster_start == ex_cluster_end) ||
4065             (rr_cluster_start == ex_cluster_start)) {
4066                 if (rr_cluster_start == ex_cluster_end)
4067                         ee_start += ee_len - 1;
4068                 map->m_pblk = EXT4_PBLK_CMASK(sbi, ee_start) + c_offset;
4069                 map->m_len = min(map->m_len,
4070                                  (unsigned) sbi->s_cluster_ratio - c_offset);
4071                 /*
4072                  * Check for and handle this case:
4073                  *
4074                  *   |--------- cluster # N-------------|
4075                  *                     |------- extent ----|
4076                  *         |--- requested region ---|
4077                  *         |===========|
4078                  */
4079
4080                 if (map->m_lblk < ee_block)
4081                         map->m_len = min(map->m_len, ee_block - map->m_lblk);
4082
4083                 /*
4084                  * Check for the case where there is already another allocated
4085                  * block to the right of 'ex' but before the end of the cluster.
4086                  *
4087                  *          |------------- cluster # N-------------|
4088                  * |----- ex -----|                  |---- ex_right ----|
4089                  *                  |------ requested region ------|
4090                  *                  |================|
4091                  */
4092                 if (map->m_lblk > ee_block) {
4093                         ext4_lblk_t next = ext4_ext_next_allocated_block(path);
4094                         map->m_len = min(map->m_len, next - map->m_lblk);
4095                 }
4096
4097                 trace_ext4_get_implied_cluster_alloc_exit(sb, map, 1);
4098                 return 1;
4099         }
4100
4101         trace_ext4_get_implied_cluster_alloc_exit(sb, map, 0);
4102         return 0;
4103 }
4104
4105 /*
4106  * Determine hole length around the given logical block, first try to
4107  * locate and expand the hole from the given @path, and then adjust it
4108  * if it's partially or completely converted to delayed extents, insert
4109  * it into the extent cache tree if it's indeed a hole, finally return
4110  * the length of the determined extent.
4111  */
4112 static ext4_lblk_t ext4_ext_determine_insert_hole(struct inode *inode,
4113                                                   struct ext4_ext_path *path,
4114                                                   ext4_lblk_t lblk)
4115 {
4116         ext4_lblk_t hole_start, len;
4117         struct extent_status es;
4118
4119         hole_start = lblk;
4120         len = ext4_ext_find_hole(inode, path, &hole_start);
4121 again:
4122         ext4_es_find_extent_range(inode, &ext4_es_is_delayed, hole_start,
4123                                   hole_start + len - 1, &es);
4124         if (!es.es_len)
4125                 goto insert_hole;
4126
4127         /*
4128          * There's a delalloc extent in the hole, handle it if the delalloc
4129          * extent is in front of, behind and straddle the queried range.
4130          */
4131         if (lblk >= es.es_lblk + es.es_len) {
4132                 /*
4133                  * The delalloc extent is in front of the queried range,
4134                  * find again from the queried start block.
4135                  */
4136                 len -= lblk - hole_start;
4137                 hole_start = lblk;
4138                 goto again;
4139         } else if (in_range(lblk, es.es_lblk, es.es_len)) {
4140                 /*
4141                  * The delalloc extent containing lblk, it must have been
4142                  * added after ext4_map_blocks() checked the extent status
4143                  * tree so we are not holding i_rwsem and delalloc info is
4144                  * only stabilized by i_data_sem we are going to release
4145                  * soon. Don't modify the extent status tree and report
4146                  * extent as a hole, just adjust the length to the delalloc
4147                  * extent's after lblk.
4148                  */
4149                 len = es.es_lblk + es.es_len - lblk;
4150                 return len;
4151         } else {
4152                 /*
4153                  * The delalloc extent is partially or completely behind
4154                  * the queried range, update hole length until the
4155                  * beginning of the delalloc extent.
4156                  */
4157                 len = min(es.es_lblk - hole_start, len);
4158         }
4159
4160 insert_hole:
4161         /* Put just found gap into cache to speed up subsequent requests */
4162         ext_debug(inode, " -> %u:%u\n", hole_start, len);
4163         ext4_es_insert_extent(inode, hole_start, len, ~0,
4164                               EXTENT_STATUS_HOLE, false);
4165
4166         /* Update hole_len to reflect hole size after lblk */
4167         if (hole_start != lblk)
4168                 len -= lblk - hole_start;
4169
4170         return len;
4171 }
4172
4173 /*
4174  * Block allocation/map/preallocation routine for extents based files
4175  *
4176  *
4177  * Need to be called with
4178  * down_read(&EXT4_I(inode)->i_data_sem) if not allocating file system block
4179  * (ie, flags is zero). Otherwise down_write(&EXT4_I(inode)->i_data_sem)
4180  *
4181  * return > 0, number of blocks already mapped/allocated
4182  *          if flags doesn't contain EXT4_GET_BLOCKS_CREATE and these are pre-allocated blocks
4183  *              buffer head is unmapped
4184  *          otherwise blocks are mapped
4185  *
4186  * return = 0, if plain look up failed (blocks have not been allocated)
4187  *          buffer head is unmapped
4188  *
4189  * return < 0, error case.
4190  */
4191 int ext4_ext_map_blocks(handle_t *handle, struct inode *inode,
4192                         struct ext4_map_blocks *map, int flags)
4193 {
4194         struct ext4_ext_path *path = NULL;
4195         struct ext4_extent newex, *ex, ex2;
4196         struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
4197         ext4_fsblk_t newblock = 0, pblk;
4198         int err = 0, depth;
4199         unsigned int allocated = 0, offset = 0;
4200         unsigned int allocated_clusters = 0;
4201         struct ext4_allocation_request ar;
4202         ext4_lblk_t cluster_offset;
4203
4204         ext_debug(inode, "blocks %u/%u requested\n", map->m_lblk, map->m_len);
4205         trace_ext4_ext_map_blocks_enter(inode, map->m_lblk, map->m_len, flags);
4206
4207         /* find extent for this block */
4208         path = ext4_find_extent(inode, map->m_lblk, NULL, flags);
4209         if (IS_ERR(path)) {
4210                 err = PTR_ERR(path);
4211                 goto out;
4212         }
4213
4214         depth = ext_depth(inode);
4215
4216         /*
4217          * consistent leaf must not be empty;
4218          * this situation is possible, though, _during_ tree modification;
4219          * this is why assert can't be put in ext4_find_extent()
4220          */
4221         if (unlikely(path[depth].p_ext == NULL && depth != 0)) {
4222                 EXT4_ERROR_INODE(inode, "bad extent address "
4223                                  "lblock: %lu, depth: %d pblock %lld",
4224                                  (unsigned long) map->m_lblk, depth,
4225                                  path[depth].p_block);
4226                 err = -EFSCORRUPTED;
4227                 goto out;
4228         }
4229
4230         ex = path[depth].p_ext;
4231         if (ex) {
4232                 ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block);
4233                 ext4_fsblk_t ee_start = ext4_ext_pblock(ex);
4234                 unsigned short ee_len;
4235
4236
4237                 /*
4238                  * unwritten extents are treated as holes, except that
4239                  * we split out initialized portions during a write.
4240                  */
4241                 ee_len = ext4_ext_get_actual_len(ex);
4242
4243                 trace_ext4_ext_show_extent(inode, ee_block, ee_start, ee_len);
4244
4245                 /* if found extent covers block, simply return it */
4246                 if (in_range(map->m_lblk, ee_block, ee_len)) {
4247                         newblock = map->m_lblk - ee_block + ee_start;
4248                         /* number of remaining blocks in the extent */
4249                         allocated = ee_len - (map->m_lblk - ee_block);
4250                         ext_debug(inode, "%u fit into %u:%d -> %llu\n",
4251                                   map->m_lblk, ee_block, ee_len, newblock);
4252
4253                         /*
4254                          * If the extent is initialized check whether the
4255                          * caller wants to convert it to unwritten.
4256                          */
4257                         if ((!ext4_ext_is_unwritten(ex)) &&
4258                             (flags & EXT4_GET_BLOCKS_CONVERT_UNWRITTEN)) {
4259                                 path = convert_initialized_extent(handle,
4260                                         inode, map, path, &allocated);
4261                                 if (IS_ERR(path))
4262                                         err = PTR_ERR(path);
4263                                 goto out;
4264                         } else if (!ext4_ext_is_unwritten(ex)) {
4265                                 map->m_flags |= EXT4_MAP_MAPPED;
4266                                 map->m_pblk = newblock;
4267                                 if (allocated > map->m_len)
4268                                         allocated = map->m_len;
4269                                 map->m_len = allocated;
4270                                 ext4_ext_show_leaf(inode, path);
4271                                 goto out;
4272                         }
4273
4274                         path = ext4_ext_handle_unwritten_extents(
4275                                 handle, inode, map, path, flags,
4276                                 &allocated, newblock);
4277                         if (IS_ERR(path))
4278                                 err = PTR_ERR(path);
4279                         goto out;
4280                 }
4281         }
4282
4283         /*
4284          * requested block isn't allocated yet;
4285          * we couldn't try to create block if flags doesn't contain EXT4_GET_BLOCKS_CREATE
4286          */
4287         if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
4288                 ext4_lblk_t len;
4289
4290                 len = ext4_ext_determine_insert_hole(inode, path, map->m_lblk);
4291
4292                 map->m_pblk = 0;
4293                 map->m_len = min_t(unsigned int, map->m_len, len);
4294                 goto out;
4295         }
4296
4297         /*
4298          * Okay, we need to do block allocation.
4299          */
4300         newex.ee_block = cpu_to_le32(map->m_lblk);
4301         cluster_offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
4302
4303         /*
4304          * If we are doing bigalloc, check to see if the extent returned
4305          * by ext4_find_extent() implies a cluster we can use.
4306          */
4307         if (cluster_offset && ex &&
4308             get_implied_cluster_alloc(inode->i_sb, map, ex, path)) {
4309                 ar.len = allocated = map->m_len;
4310                 newblock = map->m_pblk;
4311                 goto got_allocated_blocks;
4312         }
4313
4314         /* find neighbour allocated blocks */
4315         ar.lleft = map->m_lblk;
4316         err = ext4_ext_search_left(inode, path, &ar.lleft, &ar.pleft);
4317         if (err)
4318                 goto out;
4319         ar.lright = map->m_lblk;
4320         err = ext4_ext_search_right(inode, path, &ar.lright, &ar.pright,
4321                                     &ex2, flags);
4322         if (err < 0)
4323                 goto out;
4324
4325         /* Check if the extent after searching to the right implies a
4326          * cluster we can use. */
4327         if ((sbi->s_cluster_ratio > 1) && err &&
4328             get_implied_cluster_alloc(inode->i_sb, map, &ex2, path)) {
4329                 ar.len = allocated = map->m_len;
4330                 newblock = map->m_pblk;
4331                 err = 0;
4332                 goto got_allocated_blocks;
4333         }
4334
4335         /*
4336          * See if request is beyond maximum number of blocks we can have in
4337          * a single extent. For an initialized extent this limit is
4338          * EXT_INIT_MAX_LEN and for an unwritten extent this limit is
4339          * EXT_UNWRITTEN_MAX_LEN.
4340          */
4341         if (map->m_len > EXT_INIT_MAX_LEN &&
4342             !(flags & EXT4_GET_BLOCKS_UNWRIT_EXT))
4343                 map->m_len = EXT_INIT_MAX_LEN;
4344         else if (map->m_len > EXT_UNWRITTEN_MAX_LEN &&
4345                  (flags & EXT4_GET_BLOCKS_UNWRIT_EXT))
4346                 map->m_len = EXT_UNWRITTEN_MAX_LEN;
4347
4348         /* Check if we can really insert (m_lblk)::(m_lblk + m_len) extent */
4349         newex.ee_len = cpu_to_le16(map->m_len);
4350         err = ext4_ext_check_overlap(sbi, inode, &newex, path);
4351         if (err)
4352                 allocated = ext4_ext_get_actual_len(&newex);
4353         else
4354                 allocated = map->m_len;
4355
4356         /* allocate new block */
4357         ar.inode = inode;
4358         ar.goal = ext4_ext_find_goal(inode, path, map->m_lblk);
4359         ar.logical = map->m_lblk;
4360         /*
4361          * We calculate the offset from the beginning of the cluster
4362          * for the logical block number, since when we allocate a
4363          * physical cluster, the physical block should start at the
4364          * same offset from the beginning of the cluster.  This is
4365          * needed so that future calls to get_implied_cluster_alloc()
4366          * work correctly.
4367          */
4368         offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
4369         ar.len = EXT4_NUM_B2C(sbi, offset+allocated);
4370         ar.goal -= offset;
4371         ar.logical -= offset;
4372         if (S_ISREG(inode->i_mode))
4373                 ar.flags = EXT4_MB_HINT_DATA;
4374         else
4375                 /* disable in-core preallocation for non-regular files */
4376                 ar.flags = 0;
4377         if (flags & EXT4_GET_BLOCKS_NO_NORMALIZE)
4378                 ar.flags |= EXT4_MB_HINT_NOPREALLOC;
4379         if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE)
4380                 ar.flags |= EXT4_MB_DELALLOC_RESERVED;
4381         if (flags & EXT4_GET_BLOCKS_METADATA_NOFAIL)
4382                 ar.flags |= EXT4_MB_USE_RESERVED;
4383         newblock = ext4_mb_new_blocks(handle, &ar, &err);
4384         if (!newblock)
4385                 goto out;
4386         allocated_clusters = ar.len;
4387         ar.len = EXT4_C2B(sbi, ar.len) - offset;
4388         ext_debug(inode, "allocate new block: goal %llu, found %llu/%u, requested %u\n",
4389                   ar.goal, newblock, ar.len, allocated);
4390         if (ar.len > allocated)
4391                 ar.len = allocated;
4392
4393 got_allocated_blocks:
4394         /* try to insert new extent into found leaf and return */
4395         pblk = newblock + offset;
4396         ext4_ext_store_pblock(&newex, pblk);
4397         newex.ee_len = cpu_to_le16(ar.len);
4398         /* Mark unwritten */
4399         if (flags & EXT4_GET_BLOCKS_UNWRIT_EXT) {
4400                 ext4_ext_mark_unwritten(&newex);
4401                 map->m_flags |= EXT4_MAP_UNWRITTEN;
4402         }
4403
4404         path = ext4_ext_insert_extent(handle, inode, path, &newex, flags);
4405         if (IS_ERR(path)) {
4406                 err = PTR_ERR(path);
4407                 if (allocated_clusters) {
4408                         int fb_flags = 0;
4409
4410                         /*
4411                          * free data blocks we just allocated.
4412                          * not a good idea to call discard here directly,
4413                          * but otherwise we'd need to call it every free().
4414                          */
4415                         ext4_discard_preallocations(inode);
4416                         if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE)
4417                                 fb_flags = EXT4_FREE_BLOCKS_NO_QUOT_UPDATE;
4418                         ext4_free_blocks(handle, inode, NULL, newblock,
4419                                          EXT4_C2B(sbi, allocated_clusters),
4420                                          fb_flags);
4421                 }
4422                 goto out;
4423         }
4424
4425         /*
4426          * Cache the extent and update transaction to commit on fdatasync only
4427          * when it is _not_ an unwritten extent.
4428          */
4429         if ((flags & EXT4_GET_BLOCKS_UNWRIT_EXT) == 0)
4430                 ext4_update_inode_fsync_trans(handle, inode, 1);
4431         else
4432                 ext4_update_inode_fsync_trans(handle, inode, 0);
4433
4434         map->m_flags |= (EXT4_MAP_NEW | EXT4_MAP_MAPPED);
4435         map->m_pblk = pblk;
4436         map->m_len = ar.len;
4437         allocated = map->m_len;
4438         ext4_ext_show_leaf(inode, path);
4439 out:
4440         /*
4441          * We never use EXT4_GET_BLOCKS_QUERY_LAST_IN_LEAF with CREATE flag.
4442          * So we know that the depth used here is correct, since there was no
4443          * block allocation done if EXT4_GET_BLOCKS_QUERY_LAST_IN_LEAF is set.
4444          * If tomorrow we start using this QUERY flag with CREATE, then we will
4445          * need to re-calculate the depth as it might have changed due to block
4446          * allocation.
4447          */
4448         if (flags & EXT4_GET_BLOCKS_QUERY_LAST_IN_LEAF) {
4449                 WARN_ON_ONCE(flags & EXT4_GET_BLOCKS_CREATE);
4450                 if (!err && ex && (ex == EXT_LAST_EXTENT(path[depth].p_hdr)))
4451                         map->m_flags |= EXT4_MAP_QUERY_LAST_IN_LEAF;
4452         }
4453
4454         ext4_free_ext_path(path);
4455
4456         trace_ext4_ext_map_blocks_exit(inode, flags, map,
4457                                        err ? err : allocated);
4458         return err ? err : allocated;
4459 }
4460
4461 int ext4_ext_truncate(handle_t *handle, struct inode *inode)
4462 {
4463         struct super_block *sb = inode->i_sb;
4464         ext4_lblk_t last_block;
4465         int err = 0;
4466
4467         /*
4468          * TODO: optimization is possible here.
4469          * Probably we need not scan at all,
4470          * because page truncation is enough.
4471          */
4472
4473         /* we have to know where to truncate from in crash case */
4474         EXT4_I(inode)->i_disksize = inode->i_size;
4475         err = ext4_mark_inode_dirty(handle, inode);
4476         if (err)
4477                 return err;
4478
4479         last_block = (inode->i_size + sb->s_blocksize - 1)
4480                         >> EXT4_BLOCK_SIZE_BITS(sb);
4481         ext4_es_remove_extent(inode, last_block, EXT_MAX_BLOCKS - last_block);
4482
4483 retry_remove_space:
4484         err = ext4_ext_remove_space(inode, last_block, EXT_MAX_BLOCKS - 1);
4485         if (err == -ENOMEM) {
4486                 memalloc_retry_wait(GFP_ATOMIC);
4487                 goto retry_remove_space;
4488         }
4489         return err;
4490 }
4491
4492 static int ext4_alloc_file_blocks(struct file *file, ext4_lblk_t offset,
4493                                   ext4_lblk_t len, loff_t new_size,
4494                                   int flags)
4495 {
4496         struct inode *inode = file_inode(file);
4497         handle_t *handle;
4498         int ret = 0, ret2 = 0, ret3 = 0;
4499         int retries = 0;
4500         int depth = 0;
4501         struct ext4_map_blocks map;
4502         unsigned int credits;
4503         loff_t epos, old_size = i_size_read(inode);
4504
4505         BUG_ON(!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS));
4506         map.m_lblk = offset;
4507         map.m_len = len;
4508         /*
4509          * Don't normalize the request if it can fit in one extent so
4510          * that it doesn't get unnecessarily split into multiple
4511          * extents.
4512          */
4513         if (len <= EXT_UNWRITTEN_MAX_LEN)
4514                 flags |= EXT4_GET_BLOCKS_NO_NORMALIZE;
4515
4516         /*
4517          * credits to insert 1 extent into extent tree
4518          */
4519         credits = ext4_chunk_trans_blocks(inode, len);
4520         depth = ext_depth(inode);
4521
4522 retry:
4523         while (len) {
4524                 /*
4525                  * Recalculate credits when extent tree depth changes.
4526                  */
4527                 if (depth != ext_depth(inode)) {
4528                         credits = ext4_chunk_trans_blocks(inode, len);
4529                         depth = ext_depth(inode);
4530                 }
4531
4532                 handle = ext4_journal_start(inode, EXT4_HT_MAP_BLOCKS,
4533                                             credits);
4534                 if (IS_ERR(handle)) {
4535                         ret = PTR_ERR(handle);
4536                         break;
4537                 }
4538                 ret = ext4_map_blocks(handle, inode, &map, flags);
4539                 if (ret <= 0) {
4540                         ext4_debug("inode #%lu: block %u: len %u: "
4541                                    "ext4_ext_map_blocks returned %d",
4542                                    inode->i_ino, map.m_lblk,
4543                                    map.m_len, ret);
4544                         ext4_mark_inode_dirty(handle, inode);
4545                         ext4_journal_stop(handle);
4546                         break;
4547                 }
4548                 /*
4549                  * allow a full retry cycle for any remaining allocations
4550                  */
4551                 retries = 0;
4552                 map.m_lblk += ret;
4553                 map.m_len = len = len - ret;
4554                 epos = (loff_t)map.m_lblk << inode->i_blkbits;
4555                 inode_set_ctime_current(inode);
4556                 if (new_size) {
4557                         if (epos > new_size)
4558                                 epos = new_size;
4559                         if (ext4_update_inode_size(inode, epos) & 0x1)
4560                                 inode_set_mtime_to_ts(inode,
4561                                                       inode_get_ctime(inode));
4562                         if (epos > old_size) {
4563                                 pagecache_isize_extended(inode, old_size, epos);
4564                                 ext4_zero_partial_blocks(handle, inode,
4565                                                      old_size, epos - old_size);
4566                         }
4567                 }
4568                 ret2 = ext4_mark_inode_dirty(handle, inode);
4569                 ext4_update_inode_fsync_trans(handle, inode, 1);
4570                 ret3 = ext4_journal_stop(handle);
4571                 ret2 = ret3 ? ret3 : ret2;
4572                 if (unlikely(ret2))
4573                         break;
4574         }
4575         if (ret == -ENOSPC && ext4_should_retry_alloc(inode->i_sb, &retries))
4576                 goto retry;
4577
4578         return ret > 0 ? ret2 : ret;
4579 }
4580
4581 static int ext4_collapse_range(struct file *file, loff_t offset, loff_t len);
4582
4583 static int ext4_insert_range(struct file *file, loff_t offset, loff_t len);
4584
4585 static long ext4_zero_range(struct file *file, loff_t offset,
4586                             loff_t len, int mode)
4587 {
4588         struct inode *inode = file_inode(file);
4589         handle_t *handle = NULL;
4590         loff_t new_size = 0;
4591         loff_t end = offset + len;
4592         ext4_lblk_t start_lblk, end_lblk;
4593         unsigned int blocksize = i_blocksize(inode);
4594         unsigned int blkbits = inode->i_blkbits;
4595         int ret, flags, credits;
4596
4597         trace_ext4_zero_range(inode, offset, len, mode);
4598         WARN_ON_ONCE(!inode_is_locked(inode));
4599
4600         /* Indirect files do not support unwritten extents */
4601         if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)))
4602                 return -EOPNOTSUPP;
4603
4604         if (!(mode & FALLOC_FL_KEEP_SIZE) &&
4605             (end > inode->i_size || end > EXT4_I(inode)->i_disksize)) {
4606                 new_size = end;
4607                 ret = inode_newsize_ok(inode, new_size);
4608                 if (ret)
4609                         return ret;
4610         }
4611
4612         flags = EXT4_GET_BLOCKS_CREATE_UNWRIT_EXT;
4613         /* Preallocate the range including the unaligned edges */
4614         if (!IS_ALIGNED(offset | end, blocksize)) {
4615                 ext4_lblk_t alloc_lblk = offset >> blkbits;
4616                 ext4_lblk_t len_lblk = EXT4_MAX_BLOCKS(len, offset, blkbits);
4617
4618                 ret = ext4_alloc_file_blocks(file, alloc_lblk, len_lblk,
4619                                              new_size, flags);
4620                 if (ret)
4621                         return ret;
4622         }
4623
4624         ret = ext4_update_disksize_before_punch(inode, offset, len);
4625         if (ret)
4626                 return ret;
4627
4628         /* Now release the pages and zero block aligned part of pages */
4629         ret = ext4_truncate_page_cache_block_range(inode, offset, end);
4630         if (ret)
4631                 return ret;
4632
4633         /* Zero range excluding the unaligned edges */
4634         start_lblk = EXT4_B_TO_LBLK(inode, offset);
4635         end_lblk = end >> blkbits;
4636         if (end_lblk > start_lblk) {
4637                 ext4_lblk_t zero_blks = end_lblk - start_lblk;
4638
4639                 flags |= (EXT4_GET_BLOCKS_CONVERT_UNWRITTEN | EXT4_EX_NOCACHE);
4640                 ret = ext4_alloc_file_blocks(file, start_lblk, zero_blks,
4641                                              new_size, flags);
4642                 if (ret)
4643                         return ret;
4644         }
4645         /* Finish zeroing out if it doesn't contain partial block */
4646         if (IS_ALIGNED(offset | end, blocksize))
4647                 return ret;
4648
4649         /*
4650          * In worst case we have to writeout two nonadjacent unwritten
4651          * blocks and update the inode
4652          */
4653         credits = (2 * ext4_ext_index_trans_blocks(inode, 2)) + 1;
4654         if (ext4_should_journal_data(inode))
4655                 credits += 2;
4656         handle = ext4_journal_start(inode, EXT4_HT_MISC, credits);
4657         if (IS_ERR(handle)) {
4658                 ret = PTR_ERR(handle);
4659                 ext4_std_error(inode->i_sb, ret);
4660                 return ret;
4661         }
4662
4663         /* Zero out partial block at the edges of the range */
4664         ret = ext4_zero_partial_blocks(handle, inode, offset, len);
4665         if (ret)
4666                 goto out_handle;
4667
4668         if (new_size)
4669                 ext4_update_inode_size(inode, new_size);
4670         ret = ext4_mark_inode_dirty(handle, inode);
4671         if (unlikely(ret))
4672                 goto out_handle;
4673
4674         ext4_update_inode_fsync_trans(handle, inode, 1);
4675         if (file->f_flags & O_SYNC)
4676                 ext4_handle_sync(handle);
4677
4678 out_handle:
4679         ext4_journal_stop(handle);
4680         return ret;
4681 }
4682
4683 static long ext4_do_fallocate(struct file *file, loff_t offset,
4684                               loff_t len, int mode)
4685 {
4686         struct inode *inode = file_inode(file);
4687         loff_t end = offset + len;
4688         loff_t new_size = 0;
4689         ext4_lblk_t start_lblk, len_lblk;
4690         int ret;
4691
4692         trace_ext4_fallocate_enter(inode, offset, len, mode);
4693         WARN_ON_ONCE(!inode_is_locked(inode));
4694
4695         start_lblk = offset >> inode->i_blkbits;
4696         len_lblk = EXT4_MAX_BLOCKS(len, offset, inode->i_blkbits);
4697
4698         /* We only support preallocation for extent-based files only. */
4699         if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))) {
4700                 ret = -EOPNOTSUPP;
4701                 goto out;
4702         }
4703
4704         if (!(mode & FALLOC_FL_KEEP_SIZE) &&
4705             (end > inode->i_size || end > EXT4_I(inode)->i_disksize)) {
4706                 new_size = end;
4707                 ret = inode_newsize_ok(inode, new_size);
4708                 if (ret)
4709                         goto out;
4710         }
4711
4712         ret = ext4_alloc_file_blocks(file, start_lblk, len_lblk, new_size,
4713                                      EXT4_GET_BLOCKS_CREATE_UNWRIT_EXT);
4714         if (ret)
4715                 goto out;
4716
4717         if (file->f_flags & O_SYNC && EXT4_SB(inode->i_sb)->s_journal) {
4718                 ret = ext4_fc_commit(EXT4_SB(inode->i_sb)->s_journal,
4719                                         EXT4_I(inode)->i_sync_tid);
4720         }
4721 out:
4722         trace_ext4_fallocate_exit(inode, offset, len_lblk, ret);
4723         return ret;
4724 }
4725
4726 /*
4727  * preallocate space for a file. This implements ext4's fallocate file
4728  * operation, which gets called from sys_fallocate system call.
4729  * For block-mapped files, posix_fallocate should fall back to the method
4730  * of writing zeroes to the required new blocks (the same behavior which is
4731  * expected for file systems which do not support fallocate() system call).
4732  */
4733 long ext4_fallocate(struct file *file, int mode, loff_t offset, loff_t len)
4734 {
4735         struct inode *inode = file_inode(file);
4736         struct address_space *mapping = file->f_mapping;
4737         int ret;
4738
4739         /*
4740          * Encrypted inodes can't handle collapse range or insert
4741          * range since we would need to re-encrypt blocks with a
4742          * different IV or XTS tweak (which are based on the logical
4743          * block number).
4744          */
4745         if (IS_ENCRYPTED(inode) &&
4746             (mode & (FALLOC_FL_COLLAPSE_RANGE | FALLOC_FL_INSERT_RANGE)))
4747                 return -EOPNOTSUPP;
4748
4749         /* Return error if mode is not supported */
4750         if (mode & ~(FALLOC_FL_KEEP_SIZE | FALLOC_FL_PUNCH_HOLE |
4751                      FALLOC_FL_COLLAPSE_RANGE | FALLOC_FL_ZERO_RANGE |
4752                      FALLOC_FL_INSERT_RANGE))
4753                 return -EOPNOTSUPP;
4754
4755         inode_lock(inode);
4756         ret = ext4_convert_inline_data(inode);
4757         if (ret)
4758                 goto out_inode_lock;
4759
4760         /* Wait all existing dio workers, newcomers will block on i_rwsem */
4761         inode_dio_wait(inode);
4762
4763         ret = file_modified(file);
4764         if (ret)
4765                 goto out_inode_lock;
4766
4767         if ((mode & FALLOC_FL_MODE_MASK) == FALLOC_FL_ALLOCATE_RANGE) {
4768                 ret = ext4_do_fallocate(file, offset, len, mode);
4769                 goto out_inode_lock;
4770         }
4771
4772         /*
4773          * Follow-up operations will drop page cache, hold invalidate lock
4774          * to prevent page faults from reinstantiating pages we have
4775          * released from page cache.
4776          */
4777         filemap_invalidate_lock(mapping);
4778
4779         ret = ext4_break_layouts(inode);
4780         if (ret)
4781                 goto out_invalidate_lock;
4782
4783         if (mode & FALLOC_FL_PUNCH_HOLE)
4784                 ret = ext4_punch_hole(file, offset, len);
4785         else if (mode & FALLOC_FL_COLLAPSE_RANGE)
4786                 ret = ext4_collapse_range(file, offset, len);
4787         else if (mode & FALLOC_FL_INSERT_RANGE)
4788                 ret = ext4_insert_range(file, offset, len);
4789         else if (mode & FALLOC_FL_ZERO_RANGE)
4790                 ret = ext4_zero_range(file, offset, len, mode);
4791         else
4792                 ret = -EOPNOTSUPP;
4793
4794 out_invalidate_lock:
4795         filemap_invalidate_unlock(mapping);
4796 out_inode_lock:
4797         inode_unlock(inode);
4798         return ret;
4799 }
4800
4801 /*
4802  * This function converts a range of blocks to written extents. The caller of
4803  * this function will pass the start offset and the size. all unwritten extents
4804  * within this range will be converted to written extents.
4805  *
4806  * This function is called from the direct IO end io call back function for
4807  * atomic writes, to convert the unwritten extents after IO is completed.
4808  *
4809  * Note that the requirement for atomic writes is that all conversion should
4810  * happen atomically in a single fs journal transaction. We mainly only allocate
4811  * unwritten extents either on a hole on a pre-exiting unwritten extent range in
4812  * ext4_map_blocks_atomic_write(). The only case where we can have multiple
4813  * unwritten extents in a range [offset, offset+len) is when there is a split
4814  * unwritten extent between two leaf nodes which was cached in extent status
4815  * cache during ext4_iomap_alloc() time. That will allow
4816  * ext4_map_blocks_atomic_write() to return the unwritten extent range w/o going
4817  * into the slow path. That means we might need a loop for conversion of this
4818  * unwritten extent split across leaf block within a single journal transaction.
4819  * Split extents across leaf nodes is a rare case, but let's still handle that
4820  * to meet the requirements of multi-fsblock atomic writes.
4821  *
4822  * Returns 0 on success.
4823  */
4824 int ext4_convert_unwritten_extents_atomic(handle_t *handle, struct inode *inode,
4825                                           loff_t offset, ssize_t len)
4826 {
4827         unsigned int max_blocks;
4828         int ret = 0, ret2 = 0, ret3 = 0;
4829         struct ext4_map_blocks map;
4830         unsigned int blkbits = inode->i_blkbits;
4831         unsigned int credits = 0;
4832         int flags = EXT4_GET_BLOCKS_IO_CONVERT_EXT | EXT4_EX_NOCACHE;
4833
4834         map.m_lblk = offset >> blkbits;
4835         max_blocks = EXT4_MAX_BLOCKS(len, offset, blkbits);
4836
4837         if (!handle) {
4838                 /*
4839                  * TODO: An optimization can be added later by having an extent
4840                  * status flag e.g. EXTENT_STATUS_SPLIT_LEAF. If we query that
4841                  * it can tell if the extent in the cache is a split extent.
4842                  * But for now let's assume pextents as 2 always.
4843                  */
4844                 credits = ext4_meta_trans_blocks(inode, max_blocks, 2);
4845         }
4846
4847         if (credits) {
4848                 handle = ext4_journal_start(inode, EXT4_HT_MAP_BLOCKS, credits);
4849                 if (IS_ERR(handle)) {
4850                         ret = PTR_ERR(handle);
4851                         return ret;
4852                 }
4853         }
4854
4855         while (ret >= 0 && ret < max_blocks) {
4856                 map.m_lblk += ret;
4857                 map.m_len = (max_blocks -= ret);
4858                 ret = ext4_map_blocks(handle, inode, &map, flags);
4859                 if (ret != max_blocks)
4860                         ext4_msg(inode->i_sb, KERN_INFO,
4861                                      "inode #%lu: block %u: len %u: "
4862                                      "split block mapping found for atomic write, "
4863                                      "ret = %d",
4864                                      inode->i_ino, map.m_lblk,
4865                                      map.m_len, ret);
4866                 if (ret <= 0)
4867                         break;
4868         }
4869
4870         ret2 = ext4_mark_inode_dirty(handle, inode);
4871
4872         if (credits) {
4873                 ret3 = ext4_journal_stop(handle);
4874                 if (unlikely(ret3))
4875                         ret2 = ret3;
4876         }
4877
4878         if (ret <= 0 || ret2)
4879                 ext4_warning(inode->i_sb,
4880                              "inode #%lu: block %u: len %u: "
4881                              "returned %d or %d",
4882                              inode->i_ino, map.m_lblk,
4883                              map.m_len, ret, ret2);
4884
4885         return ret > 0 ? ret2 : ret;
4886 }
4887
4888 /*
4889  * This function convert a range of blocks to written extents
4890  * The caller of this function will pass the start offset and the size.
4891  * all unwritten extents within this range will be converted to
4892  * written extents.
4893  *
4894  * This function is called from the direct IO end io call back
4895  * function, to convert the fallocated extents after IO is completed.
4896  * Returns 0 on success.
4897  */
4898 int ext4_convert_unwritten_extents(handle_t *handle, struct inode *inode,
4899                                    loff_t offset, ssize_t len)
4900 {
4901         unsigned int max_blocks;
4902         int ret = 0, ret2 = 0, ret3 = 0;
4903         struct ext4_map_blocks map;
4904         unsigned int blkbits = inode->i_blkbits;
4905         unsigned int credits = 0;
4906
4907         map.m_lblk = offset >> blkbits;
4908         max_blocks = EXT4_MAX_BLOCKS(len, offset, blkbits);
4909
4910         if (!handle) {
4911                 /*
4912                  * credits to insert 1 extent into extent tree
4913                  */
4914                 credits = ext4_chunk_trans_blocks(inode, max_blocks);
4915         }
4916         while (ret >= 0 && ret < max_blocks) {
4917                 map.m_lblk += ret;
4918                 map.m_len = (max_blocks -= ret);
4919                 if (credits) {
4920                         handle = ext4_journal_start(inode, EXT4_HT_MAP_BLOCKS,
4921                                                     credits);
4922                         if (IS_ERR(handle)) {
4923                                 ret = PTR_ERR(handle);
4924                                 break;
4925                         }
4926                 }
4927                 /*
4928                  * Do not cache any unrelated extents, as it does not hold the
4929                  * i_rwsem or invalidate_lock, which could corrupt the extent
4930                  * status tree.
4931                  */
4932                 ret = ext4_map_blocks(handle, inode, &map,
4933                                       EXT4_GET_BLOCKS_IO_CONVERT_EXT |
4934                                       EXT4_EX_NOCACHE);
4935                 if (ret <= 0)
4936                         ext4_warning(inode->i_sb,
4937                                      "inode #%lu: block %u: len %u: "
4938                                      "ext4_ext_map_blocks returned %d",
4939                                      inode->i_ino, map.m_lblk,
4940                                      map.m_len, ret);
4941                 ret2 = ext4_mark_inode_dirty(handle, inode);
4942                 if (credits) {
4943                         ret3 = ext4_journal_stop(handle);
4944                         if (unlikely(ret3))
4945                                 ret2 = ret3;
4946                 }
4947
4948                 if (ret <= 0 || ret2)
4949                         break;
4950         }
4951         return ret > 0 ? ret2 : ret;
4952 }
4953
4954 int ext4_convert_unwritten_io_end_vec(handle_t *handle, ext4_io_end_t *io_end)
4955 {
4956         int ret = 0, err = 0;
4957         struct ext4_io_end_vec *io_end_vec;
4958
4959         /*
4960          * This is somewhat ugly but the idea is clear: When transaction is
4961          * reserved, everything goes into it. Otherwise we rather start several
4962          * smaller transactions for conversion of each extent separately.
4963          */
4964         if (handle) {
4965                 handle = ext4_journal_start_reserved(handle,
4966                                                      EXT4_HT_EXT_CONVERT);
4967                 if (IS_ERR(handle))
4968                         return PTR_ERR(handle);
4969         }
4970
4971         list_for_each_entry(io_end_vec, &io_end->list_vec, list) {
4972                 ret = ext4_convert_unwritten_extents(handle, io_end->inode,
4973                                                      io_end_vec->offset,
4974                                                      io_end_vec->size);
4975                 if (ret)
4976                         break;
4977         }
4978
4979         if (handle)
4980                 err = ext4_journal_stop(handle);
4981
4982         return ret < 0 ? ret : err;
4983 }
4984
4985 static int ext4_iomap_xattr_fiemap(struct inode *inode, struct iomap *iomap)
4986 {
4987         __u64 physical = 0;
4988         __u64 length = 0;
4989         int blockbits = inode->i_sb->s_blocksize_bits;
4990         int error = 0;
4991         u16 iomap_type;
4992
4993         /* in-inode? */
4994         if (ext4_test_inode_state(inode, EXT4_STATE_XATTR)) {
4995                 struct ext4_iloc iloc;
4996                 int offset;     /* offset of xattr in inode */
4997
4998                 error = ext4_get_inode_loc(inode, &iloc);
4999                 if (error)
5000                         return error;
5001                 physical = (__u64)iloc.bh->b_blocknr << blockbits;
5002                 offset = EXT4_GOOD_OLD_INODE_SIZE +
5003                                 EXT4_I(inode)->i_extra_isize;
5004                 physical += offset;
5005                 length = EXT4_SB(inode->i_sb)->s_inode_size - offset;
5006                 brelse(iloc.bh);
5007                 iomap_type = IOMAP_INLINE;
5008         } else if (EXT4_I(inode)->i_file_acl) { /* external block */
5009                 physical = (__u64)EXT4_I(inode)->i_file_acl << blockbits;
5010                 length = inode->i_sb->s_blocksize;
5011                 iomap_type = IOMAP_MAPPED;
5012         } else {
5013                 /* no in-inode or external block for xattr, so return -ENOENT */
5014                 error = -ENOENT;
5015                 goto out;
5016         }
5017
5018         iomap->addr = physical;
5019         iomap->offset = 0;
5020         iomap->length = length;
5021         iomap->type = iomap_type;
5022         iomap->flags = 0;
5023 out:
5024         return error;
5025 }
5026
5027 static int ext4_iomap_xattr_begin(struct inode *inode, loff_t offset,
5028                                   loff_t length, unsigned flags,
5029                                   struct iomap *iomap, struct iomap *srcmap)
5030 {
5031         int error;
5032
5033         error = ext4_iomap_xattr_fiemap(inode, iomap);
5034         if (error == 0 && (offset >= iomap->length))
5035                 error = -ENOENT;
5036         return error;
5037 }
5038
5039 static const struct iomap_ops ext4_iomap_xattr_ops = {
5040         .iomap_begin            = ext4_iomap_xattr_begin,
5041 };
5042
5043 static int ext4_fiemap_check_ranges(struct inode *inode, u64 start, u64 *len)
5044 {
5045         u64 maxbytes = ext4_get_maxbytes(inode);
5046
5047         if (*len == 0)
5048                 return -EINVAL;
5049         if (start > maxbytes)
5050                 return -EFBIG;
5051
5052         /*
5053          * Shrink request scope to what the fs can actually handle.
5054          */
5055         if (*len > maxbytes || (maxbytes - *len) < start)
5056                 *len = maxbytes - start;
5057         return 0;
5058 }
5059
5060 int ext4_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo,
5061                 u64 start, u64 len)
5062 {
5063         int error = 0;
5064
5065         inode_lock_shared(inode);
5066         if (fieinfo->fi_flags & FIEMAP_FLAG_CACHE) {
5067                 error = ext4_ext_precache(inode);
5068                 if (error)
5069                         goto unlock;
5070                 fieinfo->fi_flags &= ~FIEMAP_FLAG_CACHE;
5071         }
5072
5073         /*
5074          * For bitmap files the maximum size limit could be smaller than
5075          * s_maxbytes, so check len here manually instead of just relying on the
5076          * generic check.
5077          */
5078         error = ext4_fiemap_check_ranges(inode, start, &len);
5079         if (error)
5080                 goto unlock;
5081
5082         if (fieinfo->fi_flags & FIEMAP_FLAG_XATTR) {
5083                 fieinfo->fi_flags &= ~FIEMAP_FLAG_XATTR;
5084                 error = iomap_fiemap(inode, fieinfo, start, len,
5085                                      &ext4_iomap_xattr_ops);
5086         } else {
5087                 error = iomap_fiemap(inode, fieinfo, start, len,
5088                                      &ext4_iomap_report_ops);
5089         }
5090 unlock:
5091         inode_unlock_shared(inode);
5092         return error;
5093 }
5094
5095 int ext4_get_es_cache(struct inode *inode, struct fiemap_extent_info *fieinfo,
5096                       __u64 start, __u64 len)
5097 {
5098         ext4_lblk_t start_blk, len_blks;
5099         __u64 last_blk;
5100         int error = 0;
5101
5102         if (ext4_has_inline_data(inode)) {
5103                 int has_inline;
5104
5105                 down_read(&EXT4_I(inode)->xattr_sem);
5106                 has_inline = ext4_has_inline_data(inode);
5107                 up_read(&EXT4_I(inode)->xattr_sem);
5108                 if (has_inline)
5109                         return 0;
5110         }
5111
5112         if (fieinfo->fi_flags & FIEMAP_FLAG_CACHE) {
5113                 inode_lock_shared(inode);
5114                 error = ext4_ext_precache(inode);
5115                 inode_unlock_shared(inode);
5116                 if (error)
5117                         return error;
5118                 fieinfo->fi_flags &= ~FIEMAP_FLAG_CACHE;
5119         }
5120
5121         error = fiemap_prep(inode, fieinfo, start, &len, 0);
5122         if (error)
5123                 return error;
5124
5125         error = ext4_fiemap_check_ranges(inode, start, &len);
5126         if (error)
5127                 return error;
5128
5129         start_blk = start >> inode->i_sb->s_blocksize_bits;
5130         last_blk = (start + len - 1) >> inode->i_sb->s_blocksize_bits;
5131         if (last_blk >= EXT_MAX_BLOCKS)
5132                 last_blk = EXT_MAX_BLOCKS-1;
5133         len_blks = ((ext4_lblk_t) last_blk) - start_blk + 1;
5134
5135         /*
5136          * Walk the extent tree gathering extent information
5137          * and pushing extents back to the user.
5138          */
5139         return ext4_fill_es_cache_info(inode, start_blk, len_blks, fieinfo);
5140 }
5141
5142 /*
5143  * ext4_ext_shift_path_extents:
5144  * Shift the extents of a path structure lying between path[depth].p_ext
5145  * and EXT_LAST_EXTENT(path[depth].p_hdr), by @shift blocks. @SHIFT tells
5146  * if it is right shift or left shift operation.
5147  */
5148 static int
5149 ext4_ext_shift_path_extents(struct ext4_ext_path *path, ext4_lblk_t shift,
5150                             struct inode *inode, handle_t *handle,
5151                             enum SHIFT_DIRECTION SHIFT)
5152 {
5153         int depth, err = 0;
5154         struct ext4_extent *ex_start, *ex_last;
5155         bool update = false;
5156         int credits, restart_credits;
5157         depth = path->p_depth;
5158
5159         while (depth >= 0) {
5160                 if (depth == path->p_depth) {
5161                         ex_start = path[depth].p_ext;
5162                         if (!ex_start)
5163                                 return -EFSCORRUPTED;
5164
5165                         ex_last = EXT_LAST_EXTENT(path[depth].p_hdr);
5166                         /* leaf + sb + inode */
5167                         credits = 3;
5168                         if (ex_start == EXT_FIRST_EXTENT(path[depth].p_hdr)) {
5169                                 update = true;
5170                                 /* extent tree + sb + inode */
5171                                 credits = depth + 2;
5172                         }
5173
5174                         restart_credits = ext4_writepage_trans_blocks(inode);
5175                         err = ext4_datasem_ensure_credits(handle, inode, credits,
5176                                         restart_credits, 0);
5177                         if (err) {
5178                                 if (err > 0)
5179                                         err = -EAGAIN;
5180                                 goto out;
5181                         }
5182
5183                         err = ext4_ext_get_access(handle, inode, path + depth);
5184                         if (err)
5185                                 goto out;
5186
5187                         while (ex_start <= ex_last) {
5188                                 if (SHIFT == SHIFT_LEFT) {
5189                                         le32_add_cpu(&ex_start->ee_block,
5190                                                 -shift);
5191                                         /* Try to merge to the left. */
5192                                         if ((ex_start >
5193                                             EXT_FIRST_EXTENT(path[depth].p_hdr))
5194                                             &&
5195                                             ext4_ext_try_to_merge_right(inode,
5196                                             path, ex_start - 1))
5197                                                 ex_last--;
5198                                         else
5199                                                 ex_start++;
5200                                 } else {
5201                                         le32_add_cpu(&ex_last->ee_block, shift);
5202                                         ext4_ext_try_to_merge_right(inode, path,
5203                                                 ex_last);
5204                                         ex_last--;
5205                                 }
5206                         }
5207                         err = ext4_ext_dirty(handle, inode, path + depth);
5208                         if (err)
5209                                 goto out;
5210
5211                         if (--depth < 0 || !update)
5212                                 break;
5213                 }
5214
5215                 /* Update index too */
5216                 err = ext4_ext_get_access(handle, inode, path + depth);
5217                 if (err)
5218                         goto out;
5219
5220                 if (SHIFT == SHIFT_LEFT)
5221                         le32_add_cpu(&path[depth].p_idx->ei_block, -shift);
5222                 else
5223                         le32_add_cpu(&path[depth].p_idx->ei_block, shift);
5224                 err = ext4_ext_dirty(handle, inode, path + depth);
5225                 if (err)
5226                         goto out;
5227
5228                 /* we are done if current index is not a starting index */
5229                 if (path[depth].p_idx != EXT_FIRST_INDEX(path[depth].p_hdr))
5230                         break;
5231
5232                 depth--;
5233         }
5234
5235 out:
5236         return err;
5237 }
5238
5239 /*
5240  * ext4_ext_shift_extents:
5241  * All the extents which lies in the range from @start to the last allocated
5242  * block for the @inode are shifted either towards left or right (depending
5243  * upon @SHIFT) by @shift blocks.
5244  * On success, 0 is returned, error otherwise.
5245  */
5246 static int
5247 ext4_ext_shift_extents(struct inode *inode, handle_t *handle,
5248                        ext4_lblk_t start, ext4_lblk_t shift,
5249                        enum SHIFT_DIRECTION SHIFT)
5250 {
5251         struct ext4_ext_path *path;
5252         int ret = 0, depth;
5253         struct ext4_extent *extent;
5254         ext4_lblk_t stop, *iterator, ex_start, ex_end;
5255         ext4_lblk_t tmp = EXT_MAX_BLOCKS;
5256
5257         /* Let path point to the last extent */
5258         path = ext4_find_extent(inode, EXT_MAX_BLOCKS - 1, NULL,
5259                                 EXT4_EX_NOCACHE);
5260         if (IS_ERR(path))
5261                 return PTR_ERR(path);
5262
5263         depth = path->p_depth;
5264         extent = path[depth].p_ext;
5265         if (!extent)
5266                 goto out;
5267
5268         stop = le32_to_cpu(extent->ee_block);
5269
5270        /*
5271         * For left shifts, make sure the hole on the left is big enough to
5272         * accommodate the shift.  For right shifts, make sure the last extent
5273         * won't be shifted beyond EXT_MAX_BLOCKS.
5274         */
5275         if (SHIFT == SHIFT_LEFT) {
5276                 path = ext4_find_extent(inode, start - 1, path,
5277                                         EXT4_EX_NOCACHE);
5278                 if (IS_ERR(path))
5279                         return PTR_ERR(path);
5280                 depth = path->p_depth;
5281                 extent =  path[depth].p_ext;
5282                 if (extent) {
5283                         ex_start = le32_to_cpu(extent->ee_block);
5284                         ex_end = le32_to_cpu(extent->ee_block) +
5285                                 ext4_ext_get_actual_len(extent);
5286                 } else {
5287                         ex_start = 0;
5288                         ex_end = 0;
5289                 }
5290
5291                 if ((start == ex_start && shift > ex_start) ||
5292                     (shift > start - ex_end)) {
5293                         ret = -EINVAL;
5294                         goto out;
5295                 }
5296         } else {
5297                 if (shift > EXT_MAX_BLOCKS -
5298                     (stop + ext4_ext_get_actual_len(extent))) {
5299                         ret = -EINVAL;
5300                         goto out;
5301                 }
5302         }
5303
5304         /*
5305          * In case of left shift, iterator points to start and it is increased
5306          * till we reach stop. In case of right shift, iterator points to stop
5307          * and it is decreased till we reach start.
5308          */
5309 again:
5310         ret = 0;
5311         if (SHIFT == SHIFT_LEFT)
5312                 iterator = &start;
5313         else
5314                 iterator = &stop;
5315
5316         if (tmp != EXT_MAX_BLOCKS)
5317                 *iterator = tmp;
5318
5319         /*
5320          * Its safe to start updating extents.  Start and stop are unsigned, so
5321          * in case of right shift if extent with 0 block is reached, iterator
5322          * becomes NULL to indicate the end of the loop.
5323          */
5324         while (iterator && start <= stop) {
5325                 path = ext4_find_extent(inode, *iterator, path,
5326                                         EXT4_EX_NOCACHE);
5327                 if (IS_ERR(path))
5328                         return PTR_ERR(path);
5329                 depth = path->p_depth;
5330                 extent = path[depth].p_ext;
5331                 if (!extent) {
5332                         EXT4_ERROR_INODE(inode, "unexpected hole at %lu",
5333                                          (unsigned long) *iterator);
5334                         return -EFSCORRUPTED;
5335                 }
5336                 if (SHIFT == SHIFT_LEFT && *iterator >
5337                     le32_to_cpu(extent->ee_block)) {
5338                         /* Hole, move to the next extent */
5339                         if (extent < EXT_LAST_EXTENT(path[depth].p_hdr)) {
5340                                 path[depth].p_ext++;
5341                         } else {
5342                                 *iterator = ext4_ext_next_allocated_block(path);
5343                                 continue;
5344                         }
5345                 }
5346
5347                 tmp = *iterator;
5348                 if (SHIFT == SHIFT_LEFT) {
5349                         extent = EXT_LAST_EXTENT(path[depth].p_hdr);
5350                         *iterator = le32_to_cpu(extent->ee_block) +
5351                                         ext4_ext_get_actual_len(extent);
5352                 } else {
5353                         extent = EXT_FIRST_EXTENT(path[depth].p_hdr);
5354                         if (le32_to_cpu(extent->ee_block) > start)
5355                                 *iterator = le32_to_cpu(extent->ee_block) - 1;
5356                         else if (le32_to_cpu(extent->ee_block) == start)
5357                                 iterator = NULL;
5358                         else {
5359                                 extent = EXT_LAST_EXTENT(path[depth].p_hdr);
5360                                 while (le32_to_cpu(extent->ee_block) >= start)
5361                                         extent--;
5362
5363                                 if (extent == EXT_LAST_EXTENT(path[depth].p_hdr))
5364                                         break;
5365
5366                                 extent++;
5367                                 iterator = NULL;
5368                         }
5369                         path[depth].p_ext = extent;
5370                 }
5371                 ret = ext4_ext_shift_path_extents(path, shift, inode,
5372                                 handle, SHIFT);
5373                 /* iterator can be NULL which means we should break */
5374                 if (ret == -EAGAIN)
5375                         goto again;
5376                 if (ret)
5377                         break;
5378         }
5379 out:
5380         ext4_free_ext_path(path);
5381         return ret;
5382 }
5383
5384 /*
5385  * ext4_collapse_range:
5386  * This implements the fallocate's collapse range functionality for ext4
5387  * Returns: 0 and non-zero on error.
5388  */
5389 static int ext4_collapse_range(struct file *file, loff_t offset, loff_t len)
5390 {
5391         struct inode *inode = file_inode(file);
5392         struct super_block *sb = inode->i_sb;
5393         struct address_space *mapping = inode->i_mapping;
5394         loff_t end = offset + len;
5395         ext4_lblk_t start_lblk, end_lblk;
5396         handle_t *handle;
5397         unsigned int credits;
5398         loff_t start, new_size;
5399         int ret;
5400
5401         trace_ext4_collapse_range(inode, offset, len);
5402         WARN_ON_ONCE(!inode_is_locked(inode));
5403
5404         /* Currently just for extent based files */
5405         if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
5406                 return -EOPNOTSUPP;
5407         /* Collapse range works only on fs cluster size aligned regions. */
5408         if (!IS_ALIGNED(offset | len, EXT4_CLUSTER_SIZE(sb)))
5409                 return -EINVAL;
5410         /*
5411          * There is no need to overlap collapse range with EOF, in which case
5412          * it is effectively a truncate operation
5413          */
5414         if (end >= inode->i_size)
5415                 return -EINVAL;
5416
5417         /*
5418          * Write tail of the last page before removed range and data that
5419          * will be shifted since they will get removed from the page cache
5420          * below. We are also protected from pages becoming dirty by
5421          * i_rwsem and invalidate_lock.
5422          * Need to round down offset to be aligned with page size boundary
5423          * for page size > block size.
5424          */
5425         start = round_down(offset, PAGE_SIZE);
5426         ret = filemap_write_and_wait_range(mapping, start, offset);
5427         if (!ret)
5428                 ret = filemap_write_and_wait_range(mapping, end, LLONG_MAX);
5429         if (ret)
5430                 return ret;
5431
5432         truncate_pagecache(inode, start);
5433
5434         credits = ext4_writepage_trans_blocks(inode);
5435         handle = ext4_journal_start(inode, EXT4_HT_TRUNCATE, credits);
5436         if (IS_ERR(handle))
5437                 return PTR_ERR(handle);
5438
5439         ext4_fc_mark_ineligible(sb, EXT4_FC_REASON_FALLOC_RANGE, handle);
5440
5441         start_lblk = offset >> inode->i_blkbits;
5442         end_lblk = (offset + len) >> inode->i_blkbits;
5443
5444         ext4_check_map_extents_env(inode);
5445
5446         down_write(&EXT4_I(inode)->i_data_sem);
5447         ext4_discard_preallocations(inode);
5448         ext4_es_remove_extent(inode, start_lblk, EXT_MAX_BLOCKS - start_lblk);
5449
5450         ret = ext4_ext_remove_space(inode, start_lblk, end_lblk - 1);
5451         if (ret) {
5452                 up_write(&EXT4_I(inode)->i_data_sem);
5453                 goto out_handle;
5454         }
5455         ext4_discard_preallocations(inode);
5456
5457         ret = ext4_ext_shift_extents(inode, handle, end_lblk,
5458                                      end_lblk - start_lblk, SHIFT_LEFT);
5459         if (ret) {
5460                 up_write(&EXT4_I(inode)->i_data_sem);
5461                 goto out_handle;
5462         }
5463
5464         new_size = inode->i_size - len;
5465         i_size_write(inode, new_size);
5466         EXT4_I(inode)->i_disksize = new_size;
5467
5468         up_write(&EXT4_I(inode)->i_data_sem);
5469         ret = ext4_mark_inode_dirty(handle, inode);
5470         if (ret)
5471                 goto out_handle;
5472
5473         ext4_update_inode_fsync_trans(handle, inode, 1);
5474         if (IS_SYNC(inode))
5475                 ext4_handle_sync(handle);
5476
5477 out_handle:
5478         ext4_journal_stop(handle);
5479         return ret;
5480 }
5481
5482 /*
5483  * ext4_insert_range:
5484  * This function implements the FALLOC_FL_INSERT_RANGE flag of fallocate.
5485  * The data blocks starting from @offset to the EOF are shifted by @len
5486  * towards right to create a hole in the @inode. Inode size is increased
5487  * by len bytes.
5488  * Returns 0 on success, error otherwise.
5489  */
5490 static int ext4_insert_range(struct file *file, loff_t offset, loff_t len)
5491 {
5492         struct inode *inode = file_inode(file);
5493         struct super_block *sb = inode->i_sb;
5494         struct address_space *mapping = inode->i_mapping;
5495         handle_t *handle;
5496         struct ext4_ext_path *path;
5497         struct ext4_extent *extent;
5498         ext4_lblk_t start_lblk, len_lblk, ee_start_lblk = 0;
5499         unsigned int credits, ee_len;
5500         int ret, depth, split_flag = 0;
5501         loff_t start;
5502
5503         trace_ext4_insert_range(inode, offset, len);
5504         WARN_ON_ONCE(!inode_is_locked(inode));
5505
5506         /* Currently just for extent based files */
5507         if (!ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
5508                 return -EOPNOTSUPP;
5509         /* Insert range works only on fs cluster size aligned regions. */
5510         if (!IS_ALIGNED(offset | len, EXT4_CLUSTER_SIZE(sb)))
5511                 return -EINVAL;
5512         /* Offset must be less than i_size */
5513         if (offset >= inode->i_size)
5514                 return -EINVAL;
5515         /* Check whether the maximum file size would be exceeded */
5516         if (len > inode->i_sb->s_maxbytes - inode->i_size)
5517                 return -EFBIG;
5518
5519         /*
5520          * Write out all dirty pages. Need to round down to align start offset
5521          * to page size boundary for page size > block size.
5522          */
5523         start = round_down(offset, PAGE_SIZE);
5524         ret = filemap_write_and_wait_range(mapping, start, LLONG_MAX);
5525         if (ret)
5526                 return ret;
5527
5528         truncate_pagecache(inode, start);
5529
5530         credits = ext4_writepage_trans_blocks(inode);
5531         handle = ext4_journal_start(inode, EXT4_HT_TRUNCATE, credits);
5532         if (IS_ERR(handle))
5533                 return PTR_ERR(handle);
5534
5535         ext4_fc_mark_ineligible(sb, EXT4_FC_REASON_FALLOC_RANGE, handle);
5536
5537         /* Expand file to avoid data loss if there is error while shifting */
5538         inode->i_size += len;
5539         EXT4_I(inode)->i_disksize += len;
5540         ret = ext4_mark_inode_dirty(handle, inode);
5541         if (ret)
5542                 goto out_handle;
5543
5544         start_lblk = offset >> inode->i_blkbits;
5545         len_lblk = len >> inode->i_blkbits;
5546
5547         ext4_check_map_extents_env(inode);
5548
5549         down_write(&EXT4_I(inode)->i_data_sem);
5550         ext4_discard_preallocations(inode);
5551
5552         path = ext4_find_extent(inode, start_lblk, NULL, 0);
5553         if (IS_ERR(path)) {
5554                 up_write(&EXT4_I(inode)->i_data_sem);
5555                 ret = PTR_ERR(path);
5556                 goto out_handle;
5557         }
5558
5559         depth = ext_depth(inode);
5560         extent = path[depth].p_ext;
5561         if (extent) {
5562                 ee_start_lblk = le32_to_cpu(extent->ee_block);
5563                 ee_len = ext4_ext_get_actual_len(extent);
5564
5565                 /*
5566                  * If start_lblk is not the starting block of extent, split
5567                  * the extent @start_lblk
5568                  */
5569                 if ((start_lblk > ee_start_lblk) &&
5570                                 (start_lblk < (ee_start_lblk + ee_len))) {
5571                         if (ext4_ext_is_unwritten(extent))
5572                                 split_flag = EXT4_EXT_MARK_UNWRIT1 |
5573                                         EXT4_EXT_MARK_UNWRIT2;
5574                         path = ext4_split_extent_at(handle, inode, path,
5575                                         start_lblk, split_flag,
5576                                         EXT4_EX_NOCACHE |
5577                                         EXT4_GET_BLOCKS_PRE_IO |
5578                                         EXT4_GET_BLOCKS_METADATA_NOFAIL);
5579                 }
5580
5581                 if (IS_ERR(path)) {
5582                         up_write(&EXT4_I(inode)->i_data_sem);
5583                         ret = PTR_ERR(path);
5584                         goto out_handle;
5585                 }
5586         }
5587
5588         ext4_free_ext_path(path);
5589         ext4_es_remove_extent(inode, start_lblk, EXT_MAX_BLOCKS - start_lblk);
5590
5591         /*
5592          * if start_lblk lies in a hole which is at start of file, use
5593          * ee_start_lblk to shift extents
5594          */
5595         ret = ext4_ext_shift_extents(inode, handle,
5596                 max(ee_start_lblk, start_lblk), len_lblk, SHIFT_RIGHT);
5597         up_write(&EXT4_I(inode)->i_data_sem);
5598         if (ret)
5599                 goto out_handle;
5600
5601         ext4_update_inode_fsync_trans(handle, inode, 1);
5602         if (IS_SYNC(inode))
5603                 ext4_handle_sync(handle);
5604
5605 out_handle:
5606         ext4_journal_stop(handle);
5607         return ret;
5608 }
5609
5610 /**
5611  * ext4_swap_extents() - Swap extents between two inodes
5612  * @handle: handle for this transaction
5613  * @inode1:     First inode
5614  * @inode2:     Second inode
5615  * @lblk1:      Start block for first inode
5616  * @lblk2:      Start block for second inode
5617  * @count:      Number of blocks to swap
5618  * @unwritten: Mark second inode's extents as unwritten after swap
5619  * @erp:        Pointer to save error value
5620  *
5621  * This helper routine does exactly what is promise "swap extents". All other
5622  * stuff such as page-cache locking consistency, bh mapping consistency or
5623  * extent's data copying must be performed by caller.
5624  * Locking:
5625  *              i_rwsem is held for both inodes
5626  *              i_data_sem is locked for write for both inodes
5627  * Assumptions:
5628  *              All pages from requested range are locked for both inodes
5629  */
5630 int
5631 ext4_swap_extents(handle_t *handle, struct inode *inode1,
5632                   struct inode *inode2, ext4_lblk_t lblk1, ext4_lblk_t lblk2,
5633                   ext4_lblk_t count, int unwritten, int *erp)
5634 {
5635         struct ext4_ext_path *path1 = NULL;
5636         struct ext4_ext_path *path2 = NULL;
5637         int replaced_count = 0;
5638
5639         BUG_ON(!rwsem_is_locked(&EXT4_I(inode1)->i_data_sem));
5640         BUG_ON(!rwsem_is_locked(&EXT4_I(inode2)->i_data_sem));
5641         BUG_ON(!inode_is_locked(inode1));
5642         BUG_ON(!inode_is_locked(inode2));
5643
5644         ext4_es_remove_extent(inode1, lblk1, count);
5645         ext4_es_remove_extent(inode2, lblk2, count);
5646
5647         while (count) {
5648                 struct ext4_extent *ex1, *ex2, tmp_ex;
5649                 ext4_lblk_t e1_blk, e2_blk;
5650                 int e1_len, e2_len, len;
5651                 int split = 0;
5652
5653                 path1 = ext4_find_extent(inode1, lblk1, path1, EXT4_EX_NOCACHE);
5654                 if (IS_ERR(path1)) {
5655                         *erp = PTR_ERR(path1);
5656                         goto errout;
5657                 }
5658                 path2 = ext4_find_extent(inode2, lblk2, path2, EXT4_EX_NOCACHE);
5659                 if (IS_ERR(path2)) {
5660                         *erp = PTR_ERR(path2);
5661                         goto errout;
5662                 }
5663                 ex1 = path1[path1->p_depth].p_ext;
5664                 ex2 = path2[path2->p_depth].p_ext;
5665                 /* Do we have something to swap ? */
5666                 if (unlikely(!ex2 || !ex1))
5667                         goto errout;
5668
5669                 e1_blk = le32_to_cpu(ex1->ee_block);
5670                 e2_blk = le32_to_cpu(ex2->ee_block);
5671                 e1_len = ext4_ext_get_actual_len(ex1);
5672                 e2_len = ext4_ext_get_actual_len(ex2);
5673
5674                 /* Hole handling */
5675                 if (!in_range(lblk1, e1_blk, e1_len) ||
5676                     !in_range(lblk2, e2_blk, e2_len)) {
5677                         ext4_lblk_t next1, next2;
5678
5679                         /* if hole after extent, then go to next extent */
5680                         next1 = ext4_ext_next_allocated_block(path1);
5681                         next2 = ext4_ext_next_allocated_block(path2);
5682                         /* If hole before extent, then shift to that extent */
5683                         if (e1_blk > lblk1)
5684                                 next1 = e1_blk;
5685                         if (e2_blk > lblk2)
5686                                 next2 = e2_blk;
5687                         /* Do we have something to swap */
5688                         if (next1 == EXT_MAX_BLOCKS || next2 == EXT_MAX_BLOCKS)
5689                                 goto errout;
5690                         /* Move to the rightest boundary */
5691                         len = next1 - lblk1;
5692                         if (len < next2 - lblk2)
5693                                 len = next2 - lblk2;
5694                         if (len > count)
5695                                 len = count;
5696                         lblk1 += len;
5697                         lblk2 += len;
5698                         count -= len;
5699                         continue;
5700                 }
5701
5702                 /* Prepare left boundary */
5703                 if (e1_blk < lblk1) {
5704                         split = 1;
5705                         path1 = ext4_force_split_extent_at(handle, inode1,
5706                                                            path1, lblk1, 0);
5707                         if (IS_ERR(path1)) {
5708                                 *erp = PTR_ERR(path1);
5709                                 goto errout;
5710                         }
5711                 }
5712                 if (e2_blk < lblk2) {
5713                         split = 1;
5714                         path2 = ext4_force_split_extent_at(handle, inode2,
5715                                                            path2, lblk2, 0);
5716                         if (IS_ERR(path2)) {
5717                                 *erp = PTR_ERR(path2);
5718                                 goto errout;
5719                         }
5720                 }
5721                 /* ext4_split_extent_at() may result in leaf extent split,
5722                  * path must to be revalidated. */
5723                 if (split)
5724                         continue;
5725
5726                 /* Prepare right boundary */
5727                 len = count;
5728                 if (len > e1_blk + e1_len - lblk1)
5729                         len = e1_blk + e1_len - lblk1;
5730                 if (len > e2_blk + e2_len - lblk2)
5731                         len = e2_blk + e2_len - lblk2;
5732
5733                 if (len != e1_len) {
5734                         split = 1;
5735                         path1 = ext4_force_split_extent_at(handle, inode1,
5736                                                         path1, lblk1 + len, 0);
5737                         if (IS_ERR(path1)) {
5738                                 *erp = PTR_ERR(path1);
5739                                 goto errout;
5740                         }
5741                 }
5742                 if (len != e2_len) {
5743                         split = 1;
5744                         path2 = ext4_force_split_extent_at(handle, inode2,
5745                                                         path2, lblk2 + len, 0);
5746                         if (IS_ERR(path2)) {
5747                                 *erp = PTR_ERR(path2);
5748                                 goto errout;
5749                         }
5750                 }
5751                 /* ext4_split_extent_at() may result in leaf extent split,
5752                  * path must to be revalidated. */
5753                 if (split)
5754                         continue;
5755
5756                 BUG_ON(e2_len != e1_len);
5757                 *erp = ext4_ext_get_access(handle, inode1, path1 + path1->p_depth);
5758                 if (unlikely(*erp))
5759                         goto errout;
5760                 *erp = ext4_ext_get_access(handle, inode2, path2 + path2->p_depth);
5761                 if (unlikely(*erp))
5762                         goto errout;
5763
5764                 /* Both extents are fully inside boundaries. Swap it now */
5765                 tmp_ex = *ex1;
5766                 ext4_ext_store_pblock(ex1, ext4_ext_pblock(ex2));
5767                 ext4_ext_store_pblock(ex2, ext4_ext_pblock(&tmp_ex));
5768                 ex1->ee_len = cpu_to_le16(e2_len);
5769                 ex2->ee_len = cpu_to_le16(e1_len);
5770                 if (unwritten)
5771                         ext4_ext_mark_unwritten(ex2);
5772                 if (ext4_ext_is_unwritten(&tmp_ex))
5773                         ext4_ext_mark_unwritten(ex1);
5774
5775                 ext4_ext_try_to_merge(handle, inode2, path2, ex2);
5776                 ext4_ext_try_to_merge(handle, inode1, path1, ex1);
5777                 *erp = ext4_ext_dirty(handle, inode2, path2 +
5778                                       path2->p_depth);
5779                 if (unlikely(*erp))
5780                         goto errout;
5781                 *erp = ext4_ext_dirty(handle, inode1, path1 +
5782                                       path1->p_depth);
5783                 /*
5784                  * Looks scarry ah..? second inode already points to new blocks,
5785                  * and it was successfully dirtied. But luckily error may happen
5786                  * only due to journal error, so full transaction will be
5787                  * aborted anyway.
5788                  */
5789                 if (unlikely(*erp))
5790                         goto errout;
5791
5792                 lblk1 += len;
5793                 lblk2 += len;
5794                 replaced_count += len;
5795                 count -= len;
5796         }
5797
5798 errout:
5799         ext4_free_ext_path(path1);
5800         ext4_free_ext_path(path2);
5801         return replaced_count;
5802 }
5803
5804 /*
5805  * ext4_clu_mapped - determine whether any block in a logical cluster has
5806  *                   been mapped to a physical cluster
5807  *
5808  * @inode - file containing the logical cluster
5809  * @lclu - logical cluster of interest
5810  *
5811  * Returns 1 if any block in the logical cluster is mapped, signifying
5812  * that a physical cluster has been allocated for it.  Otherwise,
5813  * returns 0.  Can also return negative error codes.  Derived from
5814  * ext4_ext_map_blocks().
5815  */
5816 int ext4_clu_mapped(struct inode *inode, ext4_lblk_t lclu)
5817 {
5818         struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
5819         struct ext4_ext_path *path;
5820         int depth, mapped = 0, err = 0;
5821         struct ext4_extent *extent;
5822         ext4_lblk_t first_lblk, first_lclu, last_lclu;
5823
5824         /*
5825          * if data can be stored inline, the logical cluster isn't
5826          * mapped - no physical clusters have been allocated, and the
5827          * file has no extents
5828          */
5829         if (ext4_test_inode_state(inode, EXT4_STATE_MAY_INLINE_DATA) ||
5830             ext4_has_inline_data(inode))
5831                 return 0;
5832
5833         /* search for the extent closest to the first block in the cluster */
5834         path = ext4_find_extent(inode, EXT4_C2B(sbi, lclu), NULL, 0);
5835         if (IS_ERR(path))
5836                 return PTR_ERR(path);
5837
5838         depth = ext_depth(inode);
5839
5840         /*
5841          * A consistent leaf must not be empty.  This situation is possible,
5842          * though, _during_ tree modification, and it's why an assert can't
5843          * be put in ext4_find_extent().
5844          */
5845         if (unlikely(path[depth].p_ext == NULL && depth != 0)) {
5846                 EXT4_ERROR_INODE(inode,
5847                     "bad extent address - lblock: %lu, depth: %d, pblock: %lld",
5848                                  (unsigned long) EXT4_C2B(sbi, lclu),
5849                                  depth, path[depth].p_block);
5850                 err = -EFSCORRUPTED;
5851                 goto out;
5852         }
5853
5854         extent = path[depth].p_ext;
5855
5856         /* can't be mapped if the extent tree is empty */
5857         if (extent == NULL)
5858                 goto out;
5859
5860         first_lblk = le32_to_cpu(extent->ee_block);
5861         first_lclu = EXT4_B2C(sbi, first_lblk);
5862
5863         /*
5864          * Three possible outcomes at this point - found extent spanning
5865          * the target cluster, to the left of the target cluster, or to the
5866          * right of the target cluster.  The first two cases are handled here.
5867          * The last case indicates the target cluster is not mapped.
5868          */
5869         if (lclu >= first_lclu) {
5870                 last_lclu = EXT4_B2C(sbi, first_lblk +
5871                                      ext4_ext_get_actual_len(extent) - 1);
5872                 if (lclu <= last_lclu) {
5873                         mapped = 1;
5874                 } else {
5875                         first_lblk = ext4_ext_next_allocated_block(path);
5876                         first_lclu = EXT4_B2C(sbi, first_lblk);
5877                         if (lclu == first_lclu)
5878                                 mapped = 1;
5879                 }
5880         }
5881
5882 out:
5883         ext4_free_ext_path(path);
5884
5885         return err ? err : mapped;
5886 }
5887
5888 /*
5889  * Updates physical block address and unwritten status of extent
5890  * starting at lblk start and of len. If such an extent doesn't exist,
5891  * this function splits the extent tree appropriately to create an
5892  * extent like this.  This function is called in the fast commit
5893  * replay path.  Returns 0 on success and error on failure.
5894  */
5895 int ext4_ext_replay_update_ex(struct inode *inode, ext4_lblk_t start,
5896                               int len, int unwritten, ext4_fsblk_t pblk)
5897 {
5898         struct ext4_ext_path *path;
5899         struct ext4_extent *ex;
5900         int ret;
5901
5902         path = ext4_find_extent(inode, start, NULL, 0);
5903         if (IS_ERR(path))
5904                 return PTR_ERR(path);
5905         ex = path[path->p_depth].p_ext;
5906         if (!ex) {
5907                 ret = -EFSCORRUPTED;
5908                 goto out;
5909         }
5910
5911         if (le32_to_cpu(ex->ee_block) != start ||
5912                 ext4_ext_get_actual_len(ex) != len) {
5913                 /* We need to split this extent to match our extent first */
5914                 down_write(&EXT4_I(inode)->i_data_sem);
5915                 path = ext4_force_split_extent_at(NULL, inode, path, start, 1);
5916                 up_write(&EXT4_I(inode)->i_data_sem);
5917                 if (IS_ERR(path)) {
5918                         ret = PTR_ERR(path);
5919                         goto out;
5920                 }
5921
5922                 path = ext4_find_extent(inode, start, path, 0);
5923                 if (IS_ERR(path))
5924                         return PTR_ERR(path);
5925
5926                 ex = path[path->p_depth].p_ext;
5927                 WARN_ON(le32_to_cpu(ex->ee_block) != start);
5928
5929                 if (ext4_ext_get_actual_len(ex) != len) {
5930                         down_write(&EXT4_I(inode)->i_data_sem);
5931                         path = ext4_force_split_extent_at(NULL, inode, path,
5932                                                           start + len, 1);
5933                         up_write(&EXT4_I(inode)->i_data_sem);
5934                         if (IS_ERR(path)) {
5935                                 ret = PTR_ERR(path);
5936                                 goto out;
5937                         }
5938
5939                         path = ext4_find_extent(inode, start, path, 0);
5940                         if (IS_ERR(path))
5941                                 return PTR_ERR(path);
5942                         ex = path[path->p_depth].p_ext;
5943                 }
5944         }
5945         if (unwritten)
5946                 ext4_ext_mark_unwritten(ex);
5947         else
5948                 ext4_ext_mark_initialized(ex);
5949         ext4_ext_store_pblock(ex, pblk);
5950         down_write(&EXT4_I(inode)->i_data_sem);
5951         ret = ext4_ext_dirty(NULL, inode, &path[path->p_depth]);
5952         up_write(&EXT4_I(inode)->i_data_sem);
5953 out:
5954         ext4_free_ext_path(path);
5955         ext4_mark_inode_dirty(NULL, inode);
5956         return ret;
5957 }
5958
5959 /* Try to shrink the extent tree */
5960 void ext4_ext_replay_shrink_inode(struct inode *inode, ext4_lblk_t end)
5961 {
5962         struct ext4_ext_path *path = NULL;
5963         struct ext4_extent *ex;
5964         ext4_lblk_t old_cur, cur = 0;
5965
5966         while (cur < end) {
5967                 path = ext4_find_extent(inode, cur, NULL, 0);
5968                 if (IS_ERR(path))
5969                         return;
5970                 ex = path[path->p_depth].p_ext;
5971                 if (!ex) {
5972                         ext4_free_ext_path(path);
5973                         ext4_mark_inode_dirty(NULL, inode);
5974                         return;
5975                 }
5976                 old_cur = cur;
5977                 cur = le32_to_cpu(ex->ee_block) + ext4_ext_get_actual_len(ex);
5978                 if (cur <= old_cur)
5979                         cur = old_cur + 1;
5980                 ext4_ext_try_to_merge(NULL, inode, path, ex);
5981                 down_write(&EXT4_I(inode)->i_data_sem);
5982                 ext4_ext_dirty(NULL, inode, &path[path->p_depth]);
5983                 up_write(&EXT4_I(inode)->i_data_sem);
5984                 ext4_mark_inode_dirty(NULL, inode);
5985                 ext4_free_ext_path(path);
5986         }
5987 }
5988
5989 /* Check if *cur is a hole and if it is, skip it */
5990 static int skip_hole(struct inode *inode, ext4_lblk_t *cur)
5991 {
5992         int ret;
5993         struct ext4_map_blocks map;
5994
5995         map.m_lblk = *cur;
5996         map.m_len = ((inode->i_size) >> inode->i_sb->s_blocksize_bits) - *cur;
5997
5998         ret = ext4_map_blocks(NULL, inode, &map, 0);
5999         if (ret < 0)
6000                 return ret;
6001         if (ret != 0)
6002                 return 0;
6003         *cur = *cur + map.m_len;
6004         return 0;
6005 }
6006
6007 /* Count number of blocks used by this inode and update i_blocks */
6008 int ext4_ext_replay_set_iblocks(struct inode *inode)
6009 {
6010         struct ext4_ext_path *path = NULL, *path2 = NULL;
6011         struct ext4_extent *ex;
6012         ext4_lblk_t cur = 0, end;
6013         int numblks = 0, i, ret = 0;
6014         ext4_fsblk_t cmp1, cmp2;
6015         struct ext4_map_blocks map;
6016
6017         /* Determin the size of the file first */
6018         path = ext4_find_extent(inode, EXT_MAX_BLOCKS - 1, NULL,
6019                                         EXT4_EX_NOCACHE);
6020         if (IS_ERR(path))
6021                 return PTR_ERR(path);
6022         ex = path[path->p_depth].p_ext;
6023         if (!ex)
6024                 goto out;
6025         end = le32_to_cpu(ex->ee_block) + ext4_ext_get_actual_len(ex);
6026
6027         /* Count the number of data blocks */
6028         cur = 0;
6029         while (cur < end) {
6030                 map.m_lblk = cur;
6031                 map.m_len = end - cur;
6032                 ret = ext4_map_blocks(NULL, inode, &map, 0);
6033                 if (ret < 0)
6034                         break;
6035                 if (ret > 0)
6036                         numblks += ret;
6037                 cur = cur + map.m_len;
6038         }
6039
6040         /*
6041          * Count the number of extent tree blocks. We do it by looking up
6042          * two successive extents and determining the difference between
6043          * their paths. When path is different for 2 successive extents
6044          * we compare the blocks in the path at each level and increment
6045          * iblocks by total number of differences found.
6046          */
6047         cur = 0;
6048         ret = skip_hole(inode, &cur);
6049         if (ret < 0)
6050                 goto out;
6051         path = ext4_find_extent(inode, cur, path, 0);
6052         if (IS_ERR(path))
6053                 goto out;
6054         numblks += path->p_depth;
6055         while (cur < end) {
6056                 path = ext4_find_extent(inode, cur, path, 0);
6057                 if (IS_ERR(path))
6058                         break;
6059                 ex = path[path->p_depth].p_ext;
6060                 if (!ex)
6061                         goto cleanup;
6062
6063                 cur = max(cur + 1, le32_to_cpu(ex->ee_block) +
6064                                         ext4_ext_get_actual_len(ex));
6065                 ret = skip_hole(inode, &cur);
6066                 if (ret < 0)
6067                         break;
6068
6069                 path2 = ext4_find_extent(inode, cur, path2, 0);
6070                 if (IS_ERR(path2))
6071                         break;
6072
6073                 for (i = 0; i <= max(path->p_depth, path2->p_depth); i++) {
6074                         cmp1 = cmp2 = 0;
6075                         if (i <= path->p_depth)
6076                                 cmp1 = path[i].p_bh ?
6077                                         path[i].p_bh->b_blocknr : 0;
6078                         if (i <= path2->p_depth)
6079                                 cmp2 = path2[i].p_bh ?
6080                                         path2[i].p_bh->b_blocknr : 0;
6081                         if (cmp1 != cmp2 && cmp2 != 0)
6082                                 numblks++;
6083                 }
6084         }
6085
6086 out:
6087         inode->i_blocks = numblks << (inode->i_sb->s_blocksize_bits - 9);
6088         ext4_mark_inode_dirty(NULL, inode);
6089 cleanup:
6090         ext4_free_ext_path(path);
6091         ext4_free_ext_path(path2);
6092         return 0;
6093 }
6094
6095 int ext4_ext_clear_bb(struct inode *inode)
6096 {
6097         struct ext4_ext_path *path = NULL;
6098         struct ext4_extent *ex;
6099         ext4_lblk_t cur = 0, end;
6100         int j, ret = 0;
6101         struct ext4_map_blocks map;
6102
6103         if (ext4_test_inode_flag(inode, EXT4_INODE_INLINE_DATA))
6104                 return 0;
6105
6106         /* Determin the size of the file first */
6107         path = ext4_find_extent(inode, EXT_MAX_BLOCKS - 1, NULL,
6108                                         EXT4_EX_NOCACHE);
6109         if (IS_ERR(path))
6110                 return PTR_ERR(path);
6111         ex = path[path->p_depth].p_ext;
6112         if (!ex)
6113                 goto out;
6114         end = le32_to_cpu(ex->ee_block) + ext4_ext_get_actual_len(ex);
6115
6116         cur = 0;
6117         while (cur < end) {
6118                 map.m_lblk = cur;
6119                 map.m_len = end - cur;
6120                 ret = ext4_map_blocks(NULL, inode, &map, 0);
6121                 if (ret < 0)
6122                         break;
6123                 if (ret > 0) {
6124                         path = ext4_find_extent(inode, map.m_lblk, path, 0);
6125                         if (!IS_ERR(path)) {
6126                                 for (j = 0; j < path->p_depth; j++) {
6127                                         ext4_mb_mark_bb(inode->i_sb,
6128                                                         path[j].p_block, 1, false);
6129                                         ext4_fc_record_regions(inode->i_sb, inode->i_ino,
6130                                                         0, path[j].p_block, 1, 1);
6131                                 }
6132                         } else {
6133                                 path = NULL;
6134                         }
6135                         ext4_mb_mark_bb(inode->i_sb, map.m_pblk, map.m_len, false);
6136                         ext4_fc_record_regions(inode->i_sb, inode->i_ino,
6137                                         map.m_lblk, map.m_pblk, map.m_len, 1);
6138                 }
6139                 cur = cur + map.m_len;
6140         }
6141
6142 out:
6143         ext4_free_ext_path(path);
6144         return 0;
6145 }