fs/ext4/extents.c

   1 /*
   2  * Copyright (c) 2003-2006, Cluster File Systems, Inc, info@clusterfs.com
   3  * Written by Alex Tomas <alex@clusterfs.com>
   4  *
   5  * Architecture independence:
   6  *   Copyright (c) 2005, Bull S.A.
   7  *   Written by Pierre Peiffer <pierre.peiffer@bull.net>
   8  *
   9  * This program is free software; you can redistribute it and/or modify
  10  * it under the terms of the GNU General Public License version 2 as
  11  * published by the Free Software Foundation.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public Licens
  19  * along with this program; if not, write to the Free Software
  20  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-
  21  */
  22
  23 /*
  24  * Extents support for EXT4
  25  *
  26  * TODO:
  27  *   - ext4*_error() should be used in some situations
  28  *   - analyze all BUG()/BUG_ON(), use -EIO where appropriate
  29  *   - smart tree reduction
  30  */
  31
  32 #include <linux/fs.h>
  33 #include <linux/time.h>
  34 #include <linux/jbd2.h>
  35 #include <linux/highuid.h>
  36 #include <linux/pagemap.h>
  37 #include <linux/quotaops.h>
  38 #include <linux/string.h>
  39 #include <linux/slab.h>
  40 #include <linux/falloc.h>
  41 #include <asm/uaccess.h>
  42 #include <linux/fiemap.h>
  43 #include "ext4_jbd2.h"
  44 #include "ext4_extents.h"
  45 #include "xattr.h"
  46
  47 #include <trace/events/ext4.h>
  48
  49 /*
  50  * used by extent splitting.
  51  */
  52 #define EXT4_EXT_MAY_ZEROOUT    0x1  /* safe to zeroout if split fails \
  53                                         due to ENOSPC */
  54 #define EXT4_EXT_MARK_UNINIT1   0x2  /* mark first half uninitialized */
  55 #define EXT4_EXT_MARK_UNINIT2   0x4  /* mark second half uninitialized */
  56
  57 #define EXT4_EXT_DATA_VALID1    0x8  /* first half contains valid data */
  58 #define EXT4_EXT_DATA_VALID2    0x10 /* second half contains valid data */
  59
  60 static __le32 ext4_extent_block_csum(struct inode *inode,
  61                                      struct ext4_extent_header *eh)
  62 {
  63         struct ext4_inode_info *ei = EXT4_I(inode);
  64         struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
  65         __u32 csum;
  66
  67         csum = ext4_chksum(sbi, ei->i_csum_seed, (__u8 *)eh,
  68                            EXT4_EXTENT_TAIL_OFFSET(eh));
  69         return cpu_to_le32(csum);
  70 }
  71
  72 static int ext4_extent_block_csum_verify(struct inode *inode,
  73                                          struct ext4_extent_header *eh)
  74 {
  75         struct ext4_extent_tail *et;
  76
  77         if (!EXT4_HAS_RO_COMPAT_FEATURE(inode->i_sb,
  78                 EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
  79                 return 1;
  80
  81         et = find_ext4_extent_tail(eh);
  82         if (et->et_checksum != ext4_extent_block_csum(inode, eh))
  83                 return 0;
  84         return 1;
  85 }
  86
  87 static void ext4_extent_block_csum_set(struct inode *inode,
  88                                        struct ext4_extent_header *eh)
  89 {
  90         struct ext4_extent_tail *et;
  91
  92         if (!EXT4_HAS_RO_COMPAT_FEATURE(inode->i_sb,
  93                 EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
  94                 return;
  95
  96         et = find_ext4_extent_tail(eh);
  97         et->et_checksum = ext4_extent_block_csum(inode, eh);
  98 }
  99
 100 static int ext4_split_extent(handle_t *handle,
 101                                 struct inode *inode,
 102                                 struct ext4_ext_path *path,
 103                                 struct ext4_map_blocks *map,
 104                                 int split_flag,
 105                                 int flags);
 106
 107 static int ext4_split_extent_at(handle_t *handle,
 108                              struct inode *inode,
 109                              struct ext4_ext_path *path,
 110                              ext4_lblk_t split,
 111                              int split_flag,
 112                              int flags);
 113
 114 static int ext4_find_delayed_extent(struct inode *inode,
 115                                     struct extent_status *newes);
 116
 117 static int ext4_ext_truncate_extend_restart(handle_t *handle,
 118                                             struct inode *inode,
 119                                             int needed)
 120 {
 121         int err;
 122
 123         if (!ext4_handle_valid(handle))
 124                 return 0;
 125         if (handle->h_buffer_credits > needed)
 126                 return 0;
 127         err = ext4_journal_extend(handle, needed);
 128         if (err <= 0)
 129                 return err;
 130         err = ext4_truncate_restart_trans(handle, inode, needed);
 131         if (err == 0)
 132                 err = -EAGAIN;
 133
 134         return err;
 135 }
 136
 137 /*
 138  * could return:
 139  *  - EROFS
 140  *  - ENOMEM
 141  */
 142 static int ext4_ext_get_access(handle_t *handle, struct inode *inode,
 143                                 struct ext4_ext_path *path)
 144 {
 145         if (path->p_bh) {
 146                 /* path points to block */
 147                 return ext4_journal_get_write_access(handle, path->p_bh);
 148         }
 149         /* path points to leaf/index in inode body */
 150         /* we use in-core data, no need to protect them */
 151         return 0;
 152 }
 153
 154 /*
 155  * could return:
 156  *  - EROFS
 157  *  - ENOMEM
 158  *  - EIO
 159  */
 160 int __ext4_ext_dirty(const char *where, unsigned int line, handle_t *handle,
 161                      struct inode *inode, struct ext4_ext_path *path)
 162 {
 163         int err;
 164         if (path->p_bh) {
 165                 ext4_extent_block_csum_set(inode, ext_block_hdr(path->p_bh));
 166                 /* path points to block */
 167                 err = __ext4_handle_dirty_metadata(where, line, handle,
 168                                                    inode, path->p_bh);
 169         } else {
 170                 /* path points to leaf/index in inode body */
 171                 err = ext4_mark_inode_dirty(handle, inode);
 172         }
 173         return err;
 174 }
 175
 176 static ext4_fsblk_t ext4_ext_find_goal(struct inode *inode,
 177                               struct ext4_ext_path *path,
 178                               ext4_lblk_t block)
 179 {
 180         if (path) {
 181                 int depth = path->p_depth;
 182                 struct ext4_extent *ex;
 183
 184                 /*
 185                  * Try to predict block placement assuming that we are
 186                  * filling in a file which will eventually be
 187                  * non-sparse --- i.e., in the case of libbfd writing
 188                  * an ELF object sections out-of-order but in a way
 189                  * the eventually results in a contiguous object or
 190                  * executable file, or some database extending a table
 191                  * space file.  However, this is actually somewhat
 192                  * non-ideal if we are writing a sparse file such as
 193                  * qemu or KVM writing a raw image file that is going
 194                  * to stay fairly sparse, since it will end up
 195                  * fragmenting the file system's free space.  Maybe we
 196                  * should have some hueristics or some way to allow
 197                  * userspace to pass a hint to file system,
 198                  * especially if the latter case turns out to be
 199                  * common.
 200                  */
 201                 ex = path[depth].p_ext;
 202                 if (ex) {
 203                         ext4_fsblk_t ext_pblk = ext4_ext_pblock(ex);
 204                         ext4_lblk_t ext_block = le32_to_cpu(ex->ee_block);
 205
 206                         if (block > ext_block)
 207                                 return ext_pblk + (block - ext_block);
 208                         else
 209                                 return ext_pblk - (ext_block - block);
 210                 }
 211
 212                 /* it looks like index is empty;
 213                  * try to find starting block from index itself */
 214                 if (path[depth].p_bh)
 215                         return path[depth].p_bh->b_blocknr;
 216         }
 217
 218         /* OK. use inode's group */
 219         return ext4_inode_to_goal_block(inode);
 220 }
 221
 222 /*
 223  * Allocation for a meta data block
 224  */
 225 static ext4_fsblk_t
 226 ext4_ext_new_meta_block(handle_t *handle, struct inode *inode,
 227                         struct ext4_ext_path *path,
 228                         struct ext4_extent *ex, int *err, unsigned int flags)
 229 {
 230         ext4_fsblk_t goal, newblock;
 231
 232         goal = ext4_ext_find_goal(inode, path, le32_to_cpu(ex->ee_block));
 233         newblock = ext4_new_meta_blocks(handle, inode, goal, flags,
 234                                         NULL, err);
 235         return newblock;
 236 }
 237
 238 static inline int ext4_ext_space_block(struct inode *inode, int check)
 239 {
 240         int size;
 241
 242         size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
 243                         / sizeof(struct ext4_extent);
 244 #ifdef AGGRESSIVE_TEST
 245         if (!check && size > 6)
 246                 size = 6;
 247 #endif
 248         return size;
 249 }
 250
 251 static inline int ext4_ext_space_block_idx(struct inode *inode, int check)
 252 {
 253         int size;
 254
 255         size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
 256                         / sizeof(struct ext4_extent_idx);
 257 #ifdef AGGRESSIVE_TEST
 258         if (!check && size > 5)
 259                 size = 5;
 260 #endif
 261         return size;
 262 }
 263
 264 static inline int ext4_ext_space_root(struct inode *inode, int check)
 265 {
 266         int size;
 267
 268         size = sizeof(EXT4_I(inode)->i_data);
 269         size -= sizeof(struct ext4_extent_header);
 270         size /= sizeof(struct ext4_extent);
 271 #ifdef AGGRESSIVE_TEST
 272         if (!check && size > 3)
 273                 size = 3;
 274 #endif
 275         return size;
 276 }
 277
 278 static inline int ext4_ext_space_root_idx(struct inode *inode, int check)
 279 {
 280         int size;
 281
 282         size = sizeof(EXT4_I(inode)->i_data);
 283         size -= sizeof(struct ext4_extent_header);
 284         size /= sizeof(struct ext4_extent_idx);
 285 #ifdef AGGRESSIVE_TEST
 286         if (!check && size > 4)
 287                 size = 4;
 288 #endif
 289         return size;
 290 }
 291
 292 /*
 293  * Calculate the number of metadata blocks needed
 294  * to allocate @blocks
 295  * Worse case is one block per extent
 296  */
 297 int ext4_ext_calc_metadata_amount(struct inode *inode, ext4_lblk_t lblock)
 298 {
 299         struct ext4_inode_info *ei = EXT4_I(inode);
 300         int idxs;
 301
 302         idxs = ((inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
 303                 / sizeof(struct ext4_extent_idx));
 304
 305         /*
 306          * If the new delayed allocation block is contiguous with the
 307          * previous da block, it can share index blocks with the
 308          * previous block, so we only need to allocate a new index
 309          * block every idxs leaf blocks.  At ldxs**2 blocks, we need
 310          * an additional index block, and at ldxs**3 blocks, yet
 311          * another index blocks.
 312          */
 313         if (ei->i_da_metadata_calc_len &&
 314             ei->i_da_metadata_calc_last_lblock+1 == lblock) {
 315                 int num = 0;
 316
 317                 if ((ei->i_da_metadata_calc_len % idxs) == 0)
 318                         num++;
 319                 if ((ei->i_da_metadata_calc_len % (idxs*idxs)) == 0)
 320                         num++;
 321                 if ((ei->i_da_metadata_calc_len % (idxs*idxs*idxs)) == 0) {
 322                         num++;
 323                         ei->i_da_metadata_calc_len = 0;
 324                 } else
 325                         ei->i_da_metadata_calc_len++;
 326                 ei->i_da_metadata_calc_last_lblock++;
 327                 return num;
 328         }
 329
 330         /*
 331          * In the worst case we need a new set of index blocks at
 332          * every level of the inode's extent tree.
 333          */
 334         ei->i_da_metadata_calc_len = 1;
 335         ei->i_da_metadata_calc_last_lblock = lblock;
 336         return ext_depth(inode) + 1;
 337 }
 338
 339 static int
 340 ext4_ext_max_entries(struct inode *inode, int depth)
 341 {
 342         int max;
 343
 344         if (depth == ext_depth(inode)) {
 345                 if (depth == 0)
 346                         max = ext4_ext_space_root(inode, 1);
 347                 else
 348                         max = ext4_ext_space_root_idx(inode, 1);
 349         } else {
 350                 if (depth == 0)
 351                         max = ext4_ext_space_block(inode, 1);
 352                 else
 353                         max = ext4_ext_space_block_idx(inode, 1);
 354         }
 355
 356         return max;
 357 }
 358
 359 static int ext4_valid_extent(struct inode *inode, struct ext4_extent *ext)
 360 {
 361         ext4_fsblk_t block = ext4_ext_pblock(ext);
 362         int len = ext4_ext_get_actual_len(ext);
 363         ext4_lblk_t lblock = le32_to_cpu(ext->ee_block);
 364         ext4_lblk_t last = lblock + len - 1;
 365
 366         if (lblock > last)
 367                 return 0;
 368         return ext4_data_block_valid(EXT4_SB(inode->i_sb), block, len);
 369 }
 370
 371 static int ext4_valid_extent_idx(struct inode *inode,
 372                                 struct ext4_extent_idx *ext_idx)
 373 {
 374         ext4_fsblk_t block = ext4_idx_pblock(ext_idx);
 375
 376         return ext4_data_block_valid(EXT4_SB(inode->i_sb), block, 1);
 377 }
 378
 379 static int ext4_valid_extent_entries(struct inode *inode,
 380                                 struct ext4_extent_header *eh,
 381                                 int depth)
 382 {
 383         unsigned short entries;
 384         if (eh->eh_entries == 0)
 385                 return 1;
 386
 387         entries = le16_to_cpu(eh->eh_entries);
 388
 389         if (depth == 0) {
 390                 /* leaf entries */
 391                 struct ext4_extent *ext = EXT_FIRST_EXTENT(eh);
 392                 struct ext4_super_block *es = EXT4_SB(inode->i_sb)->s_es;
 393                 ext4_fsblk_t pblock = 0;
 394                 ext4_lblk_t lblock = 0;
 395                 ext4_lblk_t prev = 0;
 396                 int len = 0;
 397                 while (entries) {
 398                         if (!ext4_valid_extent(inode, ext))
 399                                 return 0;
 400
 401                         /* Check for overlapping extents */
 402                         lblock = le32_to_cpu(ext->ee_block);
 403                         len = ext4_ext_get_actual_len(ext);
 404                         if ((lblock <= prev) && prev) {
 405                                 pblock = ext4_ext_pblock(ext);
 406                                 es->s_last_error_block = cpu_to_le64(pblock);
 407                                 return 0;
 408                         }
 409                         ext++;
 410                         entries--;
 411                         prev = lblock + len - 1;
 412                 }
 413         } else {
 414                 struct ext4_extent_idx *ext_idx = EXT_FIRST_INDEX(eh);
 415                 while (entries) {
 416                         if (!ext4_valid_extent_idx(inode, ext_idx))
 417                                 return 0;
 418                         ext_idx++;
 419                         entries--;
 420                 }
 421         }
 422         return 1;
 423 }
 424
 425 static int __ext4_ext_check(const char *function, unsigned int line,
 426                             struct inode *inode, struct ext4_extent_header *eh,
 427                             int depth)
 428 {
 429         const char *error_msg;
 430         int max = 0;
 431
 432         if (unlikely(eh->eh_magic != EXT4_EXT_MAGIC)) {
 433                 error_msg = "invalid magic";
 434                 goto corrupted;
 435         }
 436         if (unlikely(le16_to_cpu(eh->eh_depth) != depth)) {
 437                 error_msg = "unexpected eh_depth";
 438                 goto corrupted;
 439         }
 440         if (unlikely(eh->eh_max == 0)) {
 441                 error_msg = "invalid eh_max";
 442                 goto corrupted;
 443         }
 444         max = ext4_ext_max_entries(inode, depth);
 445         if (unlikely(le16_to_cpu(eh->eh_max) > max)) {
 446                 error_msg = "too large eh_max";
 447                 goto corrupted;
 448         }
 449         if (unlikely(le16_to_cpu(eh->eh_entries) > le16_to_cpu(eh->eh_max))) {
 450                 error_msg = "invalid eh_entries";
 451                 goto corrupted;
 452         }
 453         if (!ext4_valid_extent_entries(inode, eh, depth)) {
 454                 error_msg = "invalid extent entries";
 455                 goto corrupted;
 456         }
 457         /* Verify checksum on non-root extent tree nodes */
 458         if (ext_depth(inode) != depth &&
 459             !ext4_extent_block_csum_verify(inode, eh)) {
 460                 error_msg = "extent tree corrupted";
 461                 goto corrupted;
 462         }
 463         return 0;
 464
 465 corrupted:
 466         ext4_error_inode(inode, function, line, 0,
 467                         "bad header/extent: %s - magic %x, "
 468                         "entries %u, max %u(%u), depth %u(%u)",
 469                         error_msg, le16_to_cpu(eh->eh_magic),
 470                         le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max),
 471                         max, le16_to_cpu(eh->eh_depth), depth);
 472
 473         return -EIO;
 474 }
 475
 476 #define ext4_ext_check(inode, eh, depth)        \
 477         __ext4_ext_check(__func__, __LINE__, inode, eh, depth)
 478
 479 int ext4_ext_check_inode(struct inode *inode)
 480 {
 481         return ext4_ext_check(inode, ext_inode_hdr(inode), ext_depth(inode));
 482 }
 483
 484 static int __ext4_ext_check_block(const char *function, unsigned int line,
 485                                   struct inode *inode,
 486                                   struct ext4_extent_header *eh,
 487                                   int depth,
 488                                   struct buffer_head *bh)
 489 {
 490         int ret;
 491
 492         if (buffer_verified(bh))
 493                 return 0;
 494         ret = ext4_ext_check(inode, eh, depth);
 495         if (ret)
 496                 return ret;
 497         set_buffer_verified(bh);
 498         return ret;
 499 }
 500
 501 #define ext4_ext_check_block(inode, eh, depth, bh)      \
 502         __ext4_ext_check_block(__func__, __LINE__, inode, eh, depth, bh)
 503
 504 #ifdef EXT_DEBUG
 505 static void ext4_ext_show_path(struct inode *inode, struct ext4_ext_path *path)
 506 {
 507         int k, l = path->p_depth;
 508
 509         ext_debug("path:");
 510         for (k = 0; k <= l; k++, path++) {
 511                 if (path->p_idx) {
 512                   ext_debug("  %d->%llu", le32_to_cpu(path->p_idx->ei_block),
 513                             ext4_idx_pblock(path->p_idx));
 514                 } else if (path->p_ext) {
 515                         ext_debug("  %d:[%d]%d:%llu ",
 516                                   le32_to_cpu(path->p_ext->ee_block),
 517                                   ext4_ext_is_uninitialized(path->p_ext),
 518                                   ext4_ext_get_actual_len(path->p_ext),
 519                                   ext4_ext_pblock(path->p_ext));
 520                 } else
 521                         ext_debug("  []");
 522         }
 523         ext_debug("\n");
 524 }
 525
 526 static void ext4_ext_show_leaf(struct inode *inode, struct ext4_ext_path *path)
 527 {
 528         int depth = ext_depth(inode);
 529         struct ext4_extent_header *eh;
 530         struct ext4_extent *ex;
 531         int i;
 532
 533         if (!path)
 534                 return;
 535
 536         eh = path[depth].p_hdr;
 537         ex = EXT_FIRST_EXTENT(eh);
 538
 539         ext_debug("Displaying leaf extents for inode %lu\n", inode->i_ino);
 540
 541         for (i = 0; i < le16_to_cpu(eh->eh_entries); i++, ex++) {
 542                 ext_debug("%d:[%d]%d:%llu ", le32_to_cpu(ex->ee_block),
 543                           ext4_ext_is_uninitialized(ex),
 544                           ext4_ext_get_actual_len(ex), ext4_ext_pblock(ex));
 545         }
 546         ext_debug("\n");
 547 }
 548
 549 static void ext4_ext_show_move(struct inode *inode, struct ext4_ext_path *path,
 550                         ext4_fsblk_t newblock, int level)
 551 {
 552         int depth = ext_depth(inode);
 553         struct ext4_extent *ex;
 554
 555         if (depth != level) {
 556                 struct ext4_extent_idx *idx;
 557                 idx = path[level].p_idx;
 558                 while (idx <= EXT_MAX_INDEX(path[level].p_hdr)) {
 559                         ext_debug("%d: move %d:%llu in new index %llu\n", level,
 560                                         le32_to_cpu(idx->ei_block),
 561                                         ext4_idx_pblock(idx),
 562                                         newblock);
 563                         idx++;
 564                 }
 565
 566                 return;
 567         }
 568
 569         ex = path[depth].p_ext;
 570         while (ex <= EXT_MAX_EXTENT(path[depth].p_hdr)) {
 571                 ext_debug("move %d:%llu:[%d]%d in new leaf %llu\n",
 572                                 le32_to_cpu(ex->ee_block),
 573                                 ext4_ext_pblock(ex),
 574                                 ext4_ext_is_uninitialized(ex),
 575                                 ext4_ext_get_actual_len(ex),
 576                                 newblock);
 577                 ex++;
 578         }
 579 }
 580
 581 #else
 582 #define ext4_ext_show_path(inode, path)
 583 #define ext4_ext_show_leaf(inode, path)
 584 #define ext4_ext_show_move(inode, path, newblock, level)
 585 #endif
 586
 587 void ext4_ext_drop_refs(struct ext4_ext_path *path)
 588 {
 589         int depth = path->p_depth;
 590         int i;
 591
 592         for (i = 0; i <= depth; i++, path++)
 593                 if (path->p_bh) {
 594                         brelse(path->p_bh);
 595                         path->p_bh = NULL;
 596                 }
 597 }
 598
 599 /*
 600  * ext4_ext_binsearch_idx:
 601  * binary search for the closest index of the given block
 602  * the header must be checked before calling this
 603  */
 604 static void
 605 ext4_ext_binsearch_idx(struct inode *inode,
 606                         struct ext4_ext_path *path, ext4_lblk_t block)
 607 {
 608         struct ext4_extent_header *eh = path->p_hdr;
 609         struct ext4_extent_idx *r, *l, *m;
 610
 611
 612         ext_debug("binsearch for %u(idx):  ", block);
 613
 614         l = EXT_FIRST_INDEX(eh) + 1;
 615         r = EXT_LAST_INDEX(eh);
 616         while (l <= r) {
 617                 m = l + (r - l) / 2;
 618                 if (block < le32_to_cpu(m->ei_block))
 619                         r = m - 1;
 620                 else
 621                         l = m + 1;
 622                 ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ei_block),
 623                                 m, le32_to_cpu(m->ei_block),
 624                                 r, le32_to_cpu(r->ei_block));
 625         }
 626
 627         path->p_idx = l - 1;
 628         ext_debug("  -> %u->%lld ", le32_to_cpu(path->p_idx->ei_block),
 629                   ext4_idx_pblock(path->p_idx));
 630
 631 #ifdef CHECK_BINSEARCH
 632         {
 633                 struct ext4_extent_idx *chix, *ix;
 634                 int k;
 635
 636                 chix = ix = EXT_FIRST_INDEX(eh);
 637                 for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ix++) {
 638                   if (k != 0 &&
 639                       le32_to_cpu(ix->ei_block) <= le32_to_cpu(ix[-1].ei_block)) {
 640                                 printk(KERN_DEBUG "k=%d, ix=0x%p, "
 641                                        "first=0x%p\n", k,
 642                                        ix, EXT_FIRST_INDEX(eh));
 643                                 printk(KERN_DEBUG "%u <= %u\n",
 644                                        le32_to_cpu(ix->ei_block),
 645                                        le32_to_cpu(ix[-1].ei_block));
 646                         }
 647                         BUG_ON(k && le32_to_cpu(ix->ei_block)
 648                                            <= le32_to_cpu(ix[-1].ei_block));
 649                         if (block < le32_to_cpu(ix->ei_block))
 650                                 break;
 651                         chix = ix;
 652                 }
 653                 BUG_ON(chix != path->p_idx);
 654         }
 655 #endif
 656
 657 }
 658
 659 /*
 660  * ext4_ext_binsearch:
 661  * binary search for closest extent of the given block
 662  * the header must be checked before calling this
 663  */
 664 static void
 665 ext4_ext_binsearch(struct inode *inode,
 666                 struct ext4_ext_path *path, ext4_lblk_t block)
 667 {
 668         struct ext4_extent_header *eh = path->p_hdr;
 669         struct ext4_extent *r, *l, *m;
 670
 671         if (eh->eh_entries == 0) {
 672                 /*
 673                  * this leaf is empty:
 674                  * we get such a leaf in split/add case
 675                  */
 676                 return;
 677         }
 678
 679         ext_debug("binsearch for %u:  ", block);
 680
 681         l = EXT_FIRST_EXTENT(eh) + 1;
 682         r = EXT_LAST_EXTENT(eh);
 683
 684         while (l <= r) {
 685                 m = l + (r - l) / 2;
 686                 if (block < le32_to_cpu(m->ee_block))
 687                         r = m - 1;
 688                 else
 689                         l = m + 1;
 690                 ext_debug("%p(%u):%p(%u):%p(%u) ", l, le32_to_cpu(l->ee_block),
 691                                 m, le32_to_cpu(m->ee_block),
 692                                 r, le32_to_cpu(r->ee_block));
 693         }
 694
 695         path->p_ext = l - 1;
 696         ext_debug("  -> %d:%llu:[%d]%d ",
 697                         le32_to_cpu(path->p_ext->ee_block),
 698                         ext4_ext_pblock(path->p_ext),
 699                         ext4_ext_is_uninitialized(path->p_ext),
 700                         ext4_ext_get_actual_len(path->p_ext));
 701
 702 #ifdef CHECK_BINSEARCH
 703         {
 704                 struct ext4_extent *chex, *ex;
 705                 int k;
 706
 707                 chex = ex = EXT_FIRST_EXTENT(eh);
 708                 for (k = 0; k < le16_to_cpu(eh->eh_entries); k++, ex++) {
 709                         BUG_ON(k && le32_to_cpu(ex->ee_block)
 710                                           <= le32_to_cpu(ex[-1].ee_block));
 711                         if (block < le32_to_cpu(ex->ee_block))
 712                                 break;
 713                         chex = ex;
 714                 }
 715                 BUG_ON(chex != path->p_ext);
 716         }
 717 #endif
 718
 719 }
 720
 721 int ext4_ext_tree_init(handle_t *handle, struct inode *inode)
 722 {
 723         struct ext4_extent_header *eh;
 724
 725         eh = ext_inode_hdr(inode);
 726         eh->eh_depth = 0;
 727         eh->eh_entries = 0;
 728         eh->eh_magic = EXT4_EXT_MAGIC;
 729         eh->eh_max = cpu_to_le16(ext4_ext_space_root(inode, 0));
 730         ext4_mark_inode_dirty(handle, inode);
 731         return 0;
 732 }
 733
 734 struct ext4_ext_path *
 735 ext4_ext_find_extent(struct inode *inode, ext4_lblk_t block,
 736                                         struct ext4_ext_path *path)
 737 {
 738         struct ext4_extent_header *eh;
 739         struct buffer_head *bh;
 740         short int depth, i, ppos = 0, alloc = 0;
 741         int ret;
 742
 743         eh = ext_inode_hdr(inode);
 744         depth = ext_depth(inode);
 745
 746         /* account possible depth increase */
 747         if (!path) {
 748                 path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 2),
 749                                 GFP_NOFS);
 750                 if (!path)
 751                         return ERR_PTR(-ENOMEM);
 752                 alloc = 1;
 753         }
 754         path[0].p_hdr = eh;
 755         path[0].p_bh = NULL;
 756
 757         i = depth;
 758         /* walk through the tree */
 759         while (i) {
 760                 ext_debug("depth %d: num %d, max %d\n",
 761                           ppos, le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
 762
 763                 ext4_ext_binsearch_idx(inode, path + ppos, block);
 764                 path[ppos].p_block = ext4_idx_pblock(path[ppos].p_idx);
 765                 path[ppos].p_depth = i;
 766                 path[ppos].p_ext = NULL;
 767
 768                 bh = sb_getblk(inode->i_sb, path[ppos].p_block);
 769                 if (unlikely(!bh)) {
 770                         ret = -ENOMEM;
 771                         goto err;
 772                 }
 773                 if (!bh_uptodate_or_lock(bh)) {
 774                         trace_ext4_ext_load_extent(inode, block,
 775                                                 path[ppos].p_block);
 776                         ret = bh_submit_read(bh);
 777                         if (ret < 0) {
 778                                 put_bh(bh);
 779                                 goto err;
 780                         }
 781                 }
 782                 eh = ext_block_hdr(bh);
 783                 ppos++;
 784                 if (unlikely(ppos > depth)) {
 785                         put_bh(bh);
 786                         EXT4_ERROR_INODE(inode,
 787                                          "ppos %d > depth %d", ppos, depth);
 788                         ret = -EIO;
 789                         goto err;
 790                 }
 791                 path[ppos].p_bh = bh;
 792                 path[ppos].p_hdr = eh;
 793                 i--;
 794
 795                 ret = ext4_ext_check_block(inode, eh, i, bh);
 796                 if (ret < 0)
 797                         goto err;
 798         }
 799
 800         path[ppos].p_depth = i;
 801         path[ppos].p_ext = NULL;
 802         path[ppos].p_idx = NULL;
 803
 804         /* find extent */
 805         ext4_ext_binsearch(inode, path + ppos, block);
 806         /* if not an empty leaf */
 807         if (path[ppos].p_ext)
 808                 path[ppos].p_block = ext4_ext_pblock(path[ppos].p_ext);
 809
 810         ext4_ext_show_path(inode, path);
 811
 812         return path;
 813
 814 err:
 815         ext4_ext_drop_refs(path);
 816         if (alloc)
 817                 kfree(path);
 818         return ERR_PTR(ret);
 819 }
 820
 821 /*
 822  * ext4_ext_insert_index:
 823  * insert new index [@logical;@ptr] into the block at @curp;
 824  * check where to insert: before @curp or after @curp
 825  */
 826 static int ext4_ext_insert_index(handle_t *handle, struct inode *inode,
 827                                  struct ext4_ext_path *curp,
 828                                  int logical, ext4_fsblk_t ptr)
 829 {
 830         struct ext4_extent_idx *ix;
 831         int len, err;
 832
 833         err = ext4_ext_get_access(handle, inode, curp);
 834         if (err)
 835                 return err;
 836
 837         if (unlikely(logical == le32_to_cpu(curp->p_idx->ei_block))) {
 838                 EXT4_ERROR_INODE(inode,
 839                                  "logical %d == ei_block %d!",
 840                                  logical, le32_to_cpu(curp->p_idx->ei_block));
 841                 return -EIO;
 842         }
 843
 844         if (unlikely(le16_to_cpu(curp->p_hdr->eh_entries)
 845                              >= le16_to_cpu(curp->p_hdr->eh_max))) {
 846                 EXT4_ERROR_INODE(inode,
 847                                  "eh_entries %d >= eh_max %d!",
 848                                  le16_to_cpu(curp->p_hdr->eh_entries),
 849                                  le16_to_cpu(curp->p_hdr->eh_max));
 850                 return -EIO;
 851         }
 852
 853         if (logical > le32_to_cpu(curp->p_idx->ei_block)) {
 854                 /* insert after */
 855                 ext_debug("insert new index %d after: %llu\n", logical, ptr);
 856                 ix = curp->p_idx + 1;
 857         } else {
 858                 /* insert before */
 859                 ext_debug("insert new index %d before: %llu\n", logical, ptr);
 860                 ix = curp->p_idx;
 861         }
 862
 863         len = EXT_LAST_INDEX(curp->p_hdr) - ix + 1;
 864         BUG_ON(len < 0);
 865         if (len > 0) {
 866                 ext_debug("insert new index %d: "
 867                                 "move %d indices from 0x%p to 0x%p\n",
 868                                 logical, len, ix, ix + 1);
 869                 memmove(ix + 1, ix, len * sizeof(struct ext4_extent_idx));
 870         }
 871
 872         if (unlikely(ix > EXT_MAX_INDEX(curp->p_hdr))) {
 873                 EXT4_ERROR_INODE(inode, "ix > EXT_MAX_INDEX!");
 874                 return -EIO;
 875         }
 876
 877         ix->ei_block = cpu_to_le32(logical);
 878         ext4_idx_store_pblock(ix, ptr);
 879         le16_add_cpu(&curp->p_hdr->eh_entries, 1);
 880
 881         if (unlikely(ix > EXT_LAST_INDEX(curp->p_hdr))) {
 882                 EXT4_ERROR_INODE(inode, "ix > EXT_LAST_INDEX!");
 883                 return -EIO;
 884         }
 885
 886         err = ext4_ext_dirty(handle, inode, curp);
 887         ext4_std_error(inode->i_sb, err);
 888
 889         return err;
 890 }
 891
 892 /*
 893  * ext4_ext_split:
 894  * inserts new subtree into the path, using free index entry
 895  * at depth @at:
 896  * - allocates all needed blocks (new leaf and all intermediate index blocks)
 897  * - makes decision where to split
 898  * - moves remaining extents and index entries (right to the split point)
 899  *   into the newly allocated blocks
 900  * - initializes subtree
 901  */
 902 static int ext4_ext_split(handle_t *handle, struct inode *inode,
 903                           unsigned int flags,
 904                           struct ext4_ext_path *path,
 905                           struct ext4_extent *newext, int at)
 906 {
 907         struct buffer_head *bh = NULL;
 908         int depth = ext_depth(inode);
 909         struct ext4_extent_header *neh;
 910         struct ext4_extent_idx *fidx;
 911         int i = at, k, m, a;
 912         ext4_fsblk_t newblock, oldblock;
 913         __le32 border;
 914         ext4_fsblk_t *ablocks = NULL; /* array of allocated blocks */
 915         int err = 0;
 916
 917         /* make decision: where to split? */
 918         /* FIXME: now decision is simplest: at current extent */
 919
 920         /* if current leaf will be split, then we should use
 921          * border from split point */
 922         if (unlikely(path[depth].p_ext > EXT_MAX_EXTENT(path[depth].p_hdr))) {
 923                 EXT4_ERROR_INODE(inode, "p_ext > EXT_MAX_EXTENT!");
 924                 return -EIO;
 925         }
 926         if (path[depth].p_ext != EXT_MAX_EXTENT(path[depth].p_hdr)) {
 927                 border = path[depth].p_ext[1].ee_block;
 928                 ext_debug("leaf will be split."
 929                                 " next leaf starts at %d\n",
 930                                   le32_to_cpu(border));
 931         } else {
 932                 border = newext->ee_block;
 933                 ext_debug("leaf will be added."
 934                                 " next leaf starts at %d\n",
 935                                 le32_to_cpu(border));
 936         }
 937
 938         /*
 939          * If error occurs, then we break processing
 940          * and mark filesystem read-only. index won't
 941          * be inserted and tree will be in consistent
 942          * state. Next mount will repair buffers too.
 943          */
 944
 945         /*
 946          * Get array to track all allocated blocks.
 947          * We need this to handle errors and free blocks
 948          * upon them.
 949          */
 950         ablocks = kzalloc(sizeof(ext4_fsblk_t) * depth, GFP_NOFS);
 951         if (!ablocks)
 952                 return -ENOMEM;
 953
 954         /* allocate all needed blocks */
 955         ext_debug("allocate %d blocks for indexes/leaf\n", depth - at);
 956         for (a = 0; a < depth - at; a++) {
 957                 newblock = ext4_ext_new_meta_block(handle, inode, path,
 958                                                    newext, &err, flags);
 959                 if (newblock == 0)
 960                         goto cleanup;
 961                 ablocks[a] = newblock;
 962         }
 963
 964         /* initialize new leaf */
 965         newblock = ablocks[--a];
 966         if (unlikely(newblock == 0)) {
 967                 EXT4_ERROR_INODE(inode, "newblock == 0!");
 968                 err = -EIO;
 969                 goto cleanup;
 970         }
 971         bh = sb_getblk(inode->i_sb, newblock);
 972         if (unlikely(!bh)) {
 973                 err = -ENOMEM;
 974                 goto cleanup;
 975         }
 976         lock_buffer(bh);
 977
 978         err = ext4_journal_get_create_access(handle, bh);
 979         if (err)
 980                 goto cleanup;
 981
 982         neh = ext_block_hdr(bh);
 983         neh->eh_entries = 0;
 984         neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0));
 985         neh->eh_magic = EXT4_EXT_MAGIC;
 986         neh->eh_depth = 0;
 987
 988         /* move remainder of path[depth] to the new leaf */
 989         if (unlikely(path[depth].p_hdr->eh_entries !=
 990                      path[depth].p_hdr->eh_max)) {
 991                 EXT4_ERROR_INODE(inode, "eh_entries %d != eh_max %d!",
 992                                  path[depth].p_hdr->eh_entries,
 993                                  path[depth].p_hdr->eh_max);
 994                 err = -EIO;
 995                 goto cleanup;
 996         }
 997         /* start copy from next extent */
 998         m = EXT_MAX_EXTENT(path[depth].p_hdr) - path[depth].p_ext++;
 999         ext4_ext_show_move(inode, path, newblock, depth);
1000         if (m) {
1001                 struct ext4_extent *ex;
1002                 ex = EXT_FIRST_EXTENT(neh);
1003                 memmove(ex, path[depth].p_ext, sizeof(struct ext4_extent) * m);
1004                 le16_add_cpu(&neh->eh_entries, m);
1005         }
1006
1007         ext4_extent_block_csum_set(inode, neh);
1008         set_buffer_uptodate(bh);
1009         unlock_buffer(bh);
1010
1011         err = ext4_handle_dirty_metadata(handle, inode, bh);
1012         if (err)
1013                 goto cleanup;
1014         brelse(bh);
1015         bh = NULL;
1016
1017         /* correct old leaf */
1018         if (m) {
1019                 err = ext4_ext_get_access(handle, inode, path + depth);
1020                 if (err)
1021                         goto cleanup;
1022                 le16_add_cpu(&path[depth].p_hdr->eh_entries, -m);
1023                 err = ext4_ext_dirty(handle, inode, path + depth);
1024                 if (err)
1025                         goto cleanup;
1026
1027         }
1028
1029         /* create intermediate indexes */
1030         k = depth - at - 1;
1031         if (unlikely(k < 0)) {
1032                 EXT4_ERROR_INODE(inode, "k %d < 0!", k);
1033                 err = -EIO;
1034                 goto cleanup;
1035         }
1036         if (k)
1037                 ext_debug("create %d intermediate indices\n", k);
1038         /* insert new index into current index block */
1039         /* current depth stored in i var */
1040         i = depth - 1;
1041         while (k--) {
1042                 oldblock = newblock;
1043                 newblock = ablocks[--a];
1044                 bh = sb_getblk(inode->i_sb, newblock);
1045                 if (unlikely(!bh)) {
1046                         err = -ENOMEM;
1047                         goto cleanup;
1048                 }
1049                 lock_buffer(bh);
1050
1051                 err = ext4_journal_get_create_access(handle, bh);
1052                 if (err)
1053                         goto cleanup;
1054
1055                 neh = ext_block_hdr(bh);
1056                 neh->eh_entries = cpu_to_le16(1);
1057                 neh->eh_magic = EXT4_EXT_MAGIC;
1058                 neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0));
1059                 neh->eh_depth = cpu_to_le16(depth - i);
1060                 fidx = EXT_FIRST_INDEX(neh);
1061                 fidx->ei_block = border;
1062                 ext4_idx_store_pblock(fidx, oldblock);
1063
1064                 ext_debug("int.index at %d (block %llu): %u -> %llu\n",
1065                                 i, newblock, le32_to_cpu(border), oldblock);
1066
1067                 /* move remainder of path[i] to the new index block */
1068                 if (unlikely(EXT_MAX_INDEX(path[i].p_hdr) !=
1069                                         EXT_LAST_INDEX(path[i].p_hdr))) {
1070                         EXT4_ERROR_INODE(inode,
1071                                          "EXT_MAX_INDEX != EXT_LAST_INDEX ee_block %d!",
1072                                          le32_to_cpu(path[i].p_ext->ee_block));
1073                         err = -EIO;
1074                         goto cleanup;
1075                 }
1076                 /* start copy indexes */
1077                 m = EXT_MAX_INDEX(path[i].p_hdr) - path[i].p_idx++;
1078                 ext_debug("cur 0x%p, last 0x%p\n", path[i].p_idx,
1079                                 EXT_MAX_INDEX(path[i].p_hdr));
1080                 ext4_ext_show_move(inode, path, newblock, i);
1081                 if (m) {
1082                         memmove(++fidx, path[i].p_idx,
1083                                 sizeof(struct ext4_extent_idx) * m);
1084                         le16_add_cpu(&neh->eh_entries, m);
1085                 }
1086                 ext4_extent_block_csum_set(inode, neh);
1087                 set_buffer_uptodate(bh);
1088                 unlock_buffer(bh);
1089
1090                 err = ext4_handle_dirty_metadata(handle, inode, bh);
1091                 if (err)
1092                         goto cleanup;
1093                 brelse(bh);
1094                 bh = NULL;
1095
1096                 /* correct old index */
1097                 if (m) {
1098                         err = ext4_ext_get_access(handle, inode, path + i);
1099                         if (err)
1100                                 goto cleanup;
1101                         le16_add_cpu(&path[i].p_hdr->eh_entries, -m);
1102                         err = ext4_ext_dirty(handle, inode, path + i);
1103                         if (err)
1104                                 goto cleanup;
1105                 }
1106
1107                 i--;
1108         }
1109
1110         /* insert new index */
1111         err = ext4_ext_insert_index(handle, inode, path + at,
1112                                     le32_to_cpu(border), newblock);
1113
1114 cleanup:
1115         if (bh) {
1116                 if (buffer_locked(bh))
1117                         unlock_buffer(bh);
1118                 brelse(bh);
1119         }
1120
1121         if (err) {
1122                 /* free all allocated blocks in error case */
1123                 for (i = 0; i < depth; i++) {
1124                         if (!ablocks[i])
1125                                 continue;
1126                         ext4_free_blocks(handle, inode, NULL, ablocks[i], 1,
1127                                          EXT4_FREE_BLOCKS_METADATA);
1128                 }
1129         }
1130         kfree(ablocks);
1131
1132         return err;
1133 }
1134
1135 /*
1136  * ext4_ext_grow_indepth:
1137  * implements tree growing procedure:
1138  * - allocates new block
1139  * - moves top-level data (index block or leaf) into the new block
1140  * - initializes new top-level, creating index that points to the
1141  *   just created block
1142  */
1143 static int ext4_ext_grow_indepth(handle_t *handle, struct inode *inode,
1144                                  unsigned int flags,
1145                                  struct ext4_extent *newext)
1146 {
1147         struct ext4_extent_header *neh;
1148         struct buffer_head *bh;
1149         ext4_fsblk_t newblock;
1150         int err = 0;
1151
1152         newblock = ext4_ext_new_meta_block(handle, inode, NULL,
1153                 newext, &err, flags);
1154         if (newblock == 0)
1155                 return err;
1156
1157         bh = sb_getblk(inode->i_sb, newblock);
1158         if (unlikely(!bh))
1159                 return -ENOMEM;
1160         lock_buffer(bh);
1161
1162         err = ext4_journal_get_create_access(handle, bh);
1163         if (err) {
1164                 unlock_buffer(bh);
1165                 goto out;
1166         }
1167
1168         /* move top-level index/leaf into new block */
1169         memmove(bh->b_data, EXT4_I(inode)->i_data,
1170                 sizeof(EXT4_I(inode)->i_data));
1171
1172         /* set size of new block */
1173         neh = ext_block_hdr(bh);
1174         /* old root could have indexes or leaves
1175          * so calculate e_max right way */
1176         if (ext_depth(inode))
1177                 neh->eh_max = cpu_to_le16(ext4_ext_space_block_idx(inode, 0));
1178         else
1179                 neh->eh_max = cpu_to_le16(ext4_ext_space_block(inode, 0));
1180         neh->eh_magic = EXT4_EXT_MAGIC;
1181         ext4_extent_block_csum_set(inode, neh);
1182         set_buffer_uptodate(bh);
1183         unlock_buffer(bh);
1184
1185         err = ext4_handle_dirty_metadata(handle, inode, bh);
1186         if (err)
1187                 goto out;
1188
1189         /* Update top-level index: num,max,pointer */
1190         neh = ext_inode_hdr(inode);
1191         neh->eh_entries = cpu_to_le16(1);
1192         ext4_idx_store_pblock(EXT_FIRST_INDEX(neh), newblock);
1193         if (neh->eh_depth == 0) {
1194                 /* Root extent block becomes index block */
1195                 neh->eh_max = cpu_to_le16(ext4_ext_space_root_idx(inode, 0));
1196                 EXT_FIRST_INDEX(neh)->ei_block =
1197                         EXT_FIRST_EXTENT(neh)->ee_block;
1198         }
1199         ext_debug("new root: num %d(%d), lblock %d, ptr %llu\n",
1200                   le16_to_cpu(neh->eh_entries), le16_to_cpu(neh->eh_max),
1201                   le32_to_cpu(EXT_FIRST_INDEX(neh)->ei_block),
1202                   ext4_idx_pblock(EXT_FIRST_INDEX(neh)));
1203
1204         le16_add_cpu(&neh->eh_depth, 1);
1205         ext4_mark_inode_dirty(handle, inode);
1206 out:
1207         brelse(bh);
1208
1209         return err;
1210 }
1211
1212 /*
1213  * ext4_ext_create_new_leaf:
1214  * finds empty index and adds new leaf.
1215  * if no free index is found, then it requests in-depth growing.
1216  */
1217 static int ext4_ext_create_new_leaf(handle_t *handle, struct inode *inode,
1218                                     unsigned int flags,
1219                                     struct ext4_ext_path *path,
1220                                     struct ext4_extent *newext)
1221 {
1222         struct ext4_ext_path *curp;
1223         int depth, i, err = 0;
1224
1225 repeat:
1226         i = depth = ext_depth(inode);
1227
1228         /* walk up to the tree and look for free index entry */
1229         curp = path + depth;
1230         while (i > 0 && !EXT_HAS_FREE_INDEX(curp)) {
1231                 i--;
1232                 curp--;
1233         }
1234
1235         /* we use already allocated block for index block,
1236          * so subsequent data blocks should be contiguous */
1237         if (EXT_HAS_FREE_INDEX(curp)) {
1238                 /* if we found index with free entry, then use that
1239                  * entry: create all needed subtree and add new leaf */
1240                 err = ext4_ext_split(handle, inode, flags, path, newext, i);
1241                 if (err)
1242                         goto out;
1243
1244                 /* refill path */
1245                 ext4_ext_drop_refs(path);
1246                 path = ext4_ext_find_extent(inode,
1247                                     (ext4_lblk_t)le32_to_cpu(newext->ee_block),
1248                                     path);
1249                 if (IS_ERR(path))
1250                         err = PTR_ERR(path);
1251         } else {
1252                 /* tree is full, time to grow in depth */
1253                 err = ext4_ext_grow_indepth(handle, inode, flags, newext);
1254                 if (err)
1255                         goto out;
1256
1257                 /* refill path */
1258                 ext4_ext_drop_refs(path);
1259                 path = ext4_ext_find_extent(inode,
1260                                    (ext4_lblk_t)le32_to_cpu(newext->ee_block),
1261                                     path);
1262                 if (IS_ERR(path)) {
1263                         err = PTR_ERR(path);
1264                         goto out;
1265                 }
1266
1267                 /*
1268                  * only first (depth 0 -> 1) produces free space;
1269                  * in all other cases we have to split the grown tree
1270                  */
1271                 depth = ext_depth(inode);
1272                 if (path[depth].p_hdr->eh_entries == path[depth].p_hdr->eh_max) {
1273                         /* now we need to split */
1274                         goto repeat;
1275                 }
1276         }
1277
1278 out:
1279         return err;
1280 }
1281
1282 /*
1283  * search the closest allocated block to the left for *logical
1284  * and returns it at @logical + it's physical address at @phys
1285  * if *logical is the smallest allocated block, the function
1286  * returns 0 at @phys
1287  * return value contains 0 (success) or error code
1288  */
1289 static int ext4_ext_search_left(struct inode *inode,
1290                                 struct ext4_ext_path *path,
1291                                 ext4_lblk_t *logical, ext4_fsblk_t *phys)
1292 {
1293         struct ext4_extent_idx *ix;
1294         struct ext4_extent *ex;
1295         int depth, ee_len;
1296
1297         if (unlikely(path == NULL)) {
1298                 EXT4_ERROR_INODE(inode, "path == NULL *logical %d!", *logical);
1299                 return -EIO;
1300         }
1301         depth = path->p_depth;
1302         *phys = 0;
1303
1304         if (depth == 0 && path->p_ext == NULL)
1305                 return 0;
1306
1307         /* usually extent in the path covers blocks smaller
1308          * then *logical, but it can be that extent is the
1309          * first one in the file */
1310
1311         ex = path[depth].p_ext;
1312         ee_len = ext4_ext_get_actual_len(ex);
1313         if (*logical < le32_to_cpu(ex->ee_block)) {
1314                 if (unlikely(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex)) {
1315                         EXT4_ERROR_INODE(inode,
1316                                          "EXT_FIRST_EXTENT != ex *logical %d ee_block %d!",
1317                                          *logical, le32_to_cpu(ex->ee_block));
1318                         return -EIO;
1319                 }
1320                 while (--depth >= 0) {
1321                         ix = path[depth].p_idx;
1322                         if (unlikely(ix != EXT_FIRST_INDEX(path[depth].p_hdr))) {
1323                                 EXT4_ERROR_INODE(inode,
1324                                   "ix (%d) != EXT_FIRST_INDEX (%d) (depth %d)!",
1325                                   ix != NULL ? le32_to_cpu(ix->ei_block) : 0,
1326                                   EXT_FIRST_INDEX(path[depth].p_hdr) != NULL ?
1327                 le32_to_cpu(EXT_FIRST_INDEX(path[depth].p_hdr)->ei_block) : 0,
1328                                   depth);
1329                                 return -EIO;
1330                         }
1331                 }
1332                 return 0;
1333         }
1334
1335         if (unlikely(*logical < (le32_to_cpu(ex->ee_block) + ee_len))) {
1336                 EXT4_ERROR_INODE(inode,
1337                                  "logical %d < ee_block %d + ee_len %d!",
1338                                  *logical, le32_to_cpu(ex->ee_block), ee_len);
1339                 return -EIO;
1340         }
1341
1342         *logical = le32_to_cpu(ex->ee_block) + ee_len - 1;
1343         *phys = ext4_ext_pblock(ex) + ee_len - 1;
1344         return 0;
1345 }
1346
1347 /*
1348  * search the closest allocated block to the right for *logical
1349  * and returns it at @logical + it's physical address at @phys
1350  * if *logical is the largest allocated block, the function
1351  * returns 0 at @phys
1352  * return value contains 0 (success) or error code
1353  */
1354 static int ext4_ext_search_right(struct inode *inode,
1355                                  struct ext4_ext_path *path,
1356                                  ext4_lblk_t *logical, ext4_fsblk_t *phys,
1357                                  struct ext4_extent **ret_ex)
1358 {
1359         struct buffer_head *bh = NULL;
1360         struct ext4_extent_header *eh;
1361         struct ext4_extent_idx *ix;
1362         struct ext4_extent *ex;
1363         ext4_fsblk_t block;
1364         int depth;      /* Note, NOT eh_depth; depth from top of tree */
1365         int ee_len;
1366
1367         if (unlikely(path == NULL)) {
1368                 EXT4_ERROR_INODE(inode, "path == NULL *logical %d!", *logical);
1369                 return -EIO;
1370         }
1371         depth = path->p_depth;
1372         *phys = 0;
1373
1374         if (depth == 0 && path->p_ext == NULL)
1375                 return 0;
1376
1377         /* usually extent in the path covers blocks smaller
1378          * then *logical, but it can be that extent is the
1379          * first one in the file */
1380
1381         ex = path[depth].p_ext;
1382         ee_len = ext4_ext_get_actual_len(ex);
1383         if (*logical < le32_to_cpu(ex->ee_block)) {
1384                 if (unlikely(EXT_FIRST_EXTENT(path[depth].p_hdr) != ex)) {
1385                         EXT4_ERROR_INODE(inode,
1386                                          "first_extent(path[%d].p_hdr) != ex",
1387                                          depth);
1388                         return -EIO;
1389                 }
1390                 while (--depth >= 0) {
1391                         ix = path[depth].p_idx;
1392                         if (unlikely(ix != EXT_FIRST_INDEX(path[depth].p_hdr))) {
1393                                 EXT4_ERROR_INODE(inode,
1394                                                  "ix != EXT_FIRST_INDEX *logical %d!",
1395                                                  *logical);
1396                                 return -EIO;
1397                         }
1398                 }
1399                 goto found_extent;
1400         }
1401
1402         if (unlikely(*logical < (le32_to_cpu(ex->ee_block) + ee_len))) {
1403                 EXT4_ERROR_INODE(inode,
1404                                  "logical %d < ee_block %d + ee_len %d!",
1405                                  *logical, le32_to_cpu(ex->ee_block), ee_len);
1406                 return -EIO;
1407         }
1408
1409         if (ex != EXT_LAST_EXTENT(path[depth].p_hdr)) {
1410                 /* next allocated block in this leaf */
1411                 ex++;
1412                 goto found_extent;
1413         }
1414
1415         /* go up and search for index to the right */
1416         while (--depth >= 0) {
1417                 ix = path[depth].p_idx;
1418                 if (ix != EXT_LAST_INDEX(path[depth].p_hdr))
1419                         goto got_index;
1420         }
1421
1422         /* we've gone up to the root and found no index to the right */
1423         return 0;
1424
1425 got_index:
1426         /* we've found index to the right, let's
1427          * follow it and find the closest allocated
1428          * block to the right */
1429         ix++;
1430         block = ext4_idx_pblock(ix);
1431         while (++depth < path->p_depth) {
1432                 bh = sb_bread(inode->i_sb, block);
1433                 if (bh == NULL)
1434                         return -EIO;
1435                 eh = ext_block_hdr(bh);
1436                 /* subtract from p_depth to get proper eh_depth */
1437                 if (ext4_ext_check_block(inode, eh,
1438                                          path->p_depth - depth, bh)) {
1439                         put_bh(bh);
1440                         return -EIO;
1441                 }
1442                 ix = EXT_FIRST_INDEX(eh);
1443                 block = ext4_idx_pblock(ix);
1444                 put_bh(bh);
1445         }
1446
1447         bh = sb_bread(inode->i_sb, block);
1448         if (bh == NULL)
1449                 return -EIO;
1450         eh = ext_block_hdr(bh);
1451         if (ext4_ext_check_block(inode, eh, path->p_depth - depth, bh)) {
1452                 put_bh(bh);
1453                 return -EIO;
1454         }
1455         ex = EXT_FIRST_EXTENT(eh);
1456 found_extent:
1457         *logical = le32_to_cpu(ex->ee_block);
1458         *phys = ext4_ext_pblock(ex);
1459         *ret_ex = ex;
1460         if (bh)
1461                 put_bh(bh);
1462         return 0;
1463 }
1464
1465 /*
1466  * ext4_ext_next_allocated_block:
1467  * returns allocated block in subsequent extent or EXT_MAX_BLOCKS.
1468  * NOTE: it considers block number from index entry as
1469  * allocated block. Thus, index entries have to be consistent
1470  * with leaves.
1471  */
1472 static ext4_lblk_t
1473 ext4_ext_next_allocated_block(struct ext4_ext_path *path)
1474 {
1475         int depth;
1476
1477         BUG_ON(path == NULL);
1478         depth = path->p_depth;
1479
1480         if (depth == 0 && path->p_ext == NULL)
1481                 return EXT_MAX_BLOCKS;
1482
1483         while (depth >= 0) {
1484                 if (depth == path->p_depth) {
1485                         /* leaf */
1486                         if (path[depth].p_ext &&
1487                                 path[depth].p_ext !=
1488                                         EXT_LAST_EXTENT(path[depth].p_hdr))
1489                           return le32_to_cpu(path[depth].p_ext[1].ee_block);
1490                 } else {
1491                         /* index */
1492                         if (path[depth].p_idx !=
1493                                         EXT_LAST_INDEX(path[depth].p_hdr))
1494                           return le32_to_cpu(path[depth].p_idx[1].ei_block);
1495                 }
1496                 depth--;
1497         }
1498
1499         return EXT_MAX_BLOCKS;
1500 }
1501
1502 /*
1503  * ext4_ext_next_leaf_block:
1504  * returns first allocated block from next leaf or EXT_MAX_BLOCKS
1505  */
1506 static ext4_lblk_t ext4_ext_next_leaf_block(struct ext4_ext_path *path)
1507 {
1508         int depth;
1509
1510         BUG_ON(path == NULL);
1511         depth = path->p_depth;
1512
1513         /* zero-tree has no leaf blocks at all */
1514         if (depth == 0)
1515                 return EXT_MAX_BLOCKS;
1516
1517         /* go to index block */
1518         depth--;
1519
1520         while (depth >= 0) {
1521                 if (path[depth].p_idx !=
1522                                 EXT_LAST_INDEX(path[depth].p_hdr))
1523                         return (ext4_lblk_t)
1524                                 le32_to_cpu(path[depth].p_idx[1].ei_block);
1525                 depth--;
1526         }
1527
1528         return EXT_MAX_BLOCKS;
1529 }
1530
1531 /*
1532  * ext4_ext_correct_indexes:
1533  * if leaf gets modified and modified extent is first in the leaf,
1534  * then we have to correct all indexes above.
1535  * TODO: do we need to correct tree in all cases?
1536  */
1537 static int ext4_ext_correct_indexes(handle_t *handle, struct inode *inode,
1538                                 struct ext4_ext_path *path)
1539 {
1540         struct ext4_extent_header *eh;
1541         int depth = ext_depth(inode);
1542         struct ext4_extent *ex;
1543         __le32 border;
1544         int k, err = 0;
1545
1546         eh = path[depth].p_hdr;
1547         ex = path[depth].p_ext;
1548
1549         if (unlikely(ex == NULL || eh == NULL)) {
1550                 EXT4_ERROR_INODE(inode,
1551                                  "ex %p == NULL or eh %p == NULL", ex, eh);
1552                 return -EIO;
1553         }
1554
1555         if (depth == 0) {
1556                 /* there is no tree at all */
1557                 return 0;
1558         }
1559
1560         if (ex != EXT_FIRST_EXTENT(eh)) {
1561                 /* we correct tree if first leaf got modified only */
1562                 return 0;
1563         }
1564
1565         /*
1566          * TODO: we need correction if border is smaller than current one
1567          */
1568         k = depth - 1;
1569         border = path[depth].p_ext->ee_block;
1570         err = ext4_ext_get_access(handle, inode, path + k);
1571         if (err)
1572                 return err;
1573         path[k].p_idx->ei_block = border;
1574         err = ext4_ext_dirty(handle, inode, path + k);
1575         if (err)
1576                 return err;
1577
1578         while (k--) {
1579                 /* change all left-side indexes */
1580                 if (path[k+1].p_idx != EXT_FIRST_INDEX(path[k+1].p_hdr))
1581                         break;
1582                 err = ext4_ext_get_access(handle, inode, path + k);
1583                 if (err)
1584                         break;
1585                 path[k].p_idx->ei_block = border;
1586                 err = ext4_ext_dirty(handle, inode, path + k);
1587                 if (err)
1588                         break;
1589         }
1590
1591         return err;
1592 }
1593
1594 int
1595 ext4_can_extents_be_merged(struct inode *inode, struct ext4_extent *ex1,
1596                                 struct ext4_extent *ex2)
1597 {
1598         unsigned short ext1_ee_len, ext2_ee_len, max_len;
1599
1600         /*
1601          * Make sure that both extents are initialized. We don't merge
1602          * uninitialized extents so that we can be sure that end_io code has
1603          * the extent that was written properly split out and conversion to
1604          * initialized is trivial.
1605          */
1606         if (ext4_ext_is_uninitialized(ex1) || ext4_ext_is_uninitialized(ex2))
1607                 return 0;
1608
1609         if (ext4_ext_is_uninitialized(ex1))
1610                 max_len = EXT_UNINIT_MAX_LEN;
1611         else
1612                 max_len = EXT_INIT_MAX_LEN;
1613
1614         ext1_ee_len = ext4_ext_get_actual_len(ex1);
1615         ext2_ee_len = ext4_ext_get_actual_len(ex2);
1616
1617         if (le32_to_cpu(ex1->ee_block) + ext1_ee_len !=
1618                         le32_to_cpu(ex2->ee_block))
1619                 return 0;
1620
1621         /*
1622          * To allow future support for preallocated extents to be added
1623          * as an RO_COMPAT feature, refuse to merge to extents if
1624          * this can result in the top bit of ee_len being set.
1625          */
1626         if (ext1_ee_len + ext2_ee_len > max_len)
1627                 return 0;
1628 #ifdef AGGRESSIVE_TEST
1629         if (ext1_ee_len >= 4)
1630                 return 0;
1631 #endif
1632
1633         if (ext4_ext_pblock(ex1) + ext1_ee_len == ext4_ext_pblock(ex2))
1634                 return 1;
1635         return 0;
1636 }
1637
1638 /*
1639  * This function tries to merge the "ex" extent to the next extent in the tree.
1640  * It always tries to merge towards right. If you want to merge towards
1641  * left, pass "ex - 1" as argument instead of "ex".
1642  * Returns 0 if the extents (ex and ex+1) were _not_ merged and returns
1643  * 1 if they got merged.
1644  */
1645 static int ext4_ext_try_to_merge_right(struct inode *inode,
1646                                  struct ext4_ext_path *path,
1647                                  struct ext4_extent *ex)
1648 {
1649         struct ext4_extent_header *eh;
1650         unsigned int depth, len;
1651         int merge_done = 0;
1652         int uninitialized = 0;
1653
1654         depth = ext_depth(inode);
1655         BUG_ON(path[depth].p_hdr == NULL);
1656         eh = path[depth].p_hdr;
1657
1658         while (ex < EXT_LAST_EXTENT(eh)) {
1659                 if (!ext4_can_extents_be_merged(inode, ex, ex + 1))
1660                         break;
1661                 /* merge with next extent! */
1662                 if (ext4_ext_is_uninitialized(ex))
1663                         uninitialized = 1;
1664                 ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
1665                                 + ext4_ext_get_actual_len(ex + 1));
1666                 if (uninitialized)
1667                         ext4_ext_mark_uninitialized(ex);
1668
1669                 if (ex + 1 < EXT_LAST_EXTENT(eh)) {
1670                         len = (EXT_LAST_EXTENT(eh) - ex - 1)
1671                                 * sizeof(struct ext4_extent);
1672                         memmove(ex + 1, ex + 2, len);
1673                 }
1674                 le16_add_cpu(&eh->eh_entries, -1);
1675                 merge_done = 1;
1676                 WARN_ON(eh->eh_entries == 0);
1677                 if (!eh->eh_entries)
1678                         EXT4_ERROR_INODE(inode, "eh->eh_entries = 0!");
1679         }
1680
1681         return merge_done;
1682 }
1683
1684 /*
1685  * This function does a very simple check to see if we can collapse
1686  * an extent tree with a single extent tree leaf block into the inode.
1687  */
1688 static void ext4_ext_try_to_merge_up(handle_t *handle,
1689                                      struct inode *inode,
1690                                      struct ext4_ext_path *path)
1691 {
1692         size_t s;
1693         unsigned max_root = ext4_ext_space_root(inode, 0);
1694         ext4_fsblk_t blk;
1695
1696         if ((path[0].p_depth != 1) ||
1697             (le16_to_cpu(path[0].p_hdr->eh_entries) != 1) ||
1698             (le16_to_cpu(path[1].p_hdr->eh_entries) > max_root))
1699                 return;
1700
1701         /*
1702          * We need to modify the block allocation bitmap and the block
1703          * group descriptor to release the extent tree block.  If we
1704          * can't get the journal credits, give up.
1705          */
1706         if (ext4_journal_extend(handle, 2))
1707                 return;
1708
1709         /*
1710          * Copy the extent data up to the inode
1711          */
1712         blk = ext4_idx_pblock(path[0].p_idx);
1713         s = le16_to_cpu(path[1].p_hdr->eh_entries) *
1714                 sizeof(struct ext4_extent_idx);
1715         s += sizeof(struct ext4_extent_header);
1716
1717         memcpy(path[0].p_hdr, path[1].p_hdr, s);
1718         path[0].p_depth = 0;
1719         path[0].p_ext = EXT_FIRST_EXTENT(path[0].p_hdr) +
1720                 (path[1].p_ext - EXT_FIRST_EXTENT(path[1].p_hdr));
1721         path[0].p_hdr->eh_max = cpu_to_le16(max_root);
1722
1723         brelse(path[1].p_bh);
1724         ext4_free_blocks(handle, inode, NULL, blk, 1,
1725                          EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET |
1726                          EXT4_FREE_BLOCKS_RESERVE);
1727 }
1728
1729 /*
1730  * This function tries to merge the @ex extent to neighbours in the tree.
1731  * return 1 if merge left else 0.
1732  */
1733 static void ext4_ext_try_to_merge(handle_t *handle,
1734                                   struct inode *inode,
1735                                   struct ext4_ext_path *path,
1736                                   struct ext4_extent *ex) {
1737         struct ext4_extent_header *eh;
1738         unsigned int depth;
1739         int merge_done = 0;
1740
1741         depth = ext_depth(inode);
1742         BUG_ON(path[depth].p_hdr == NULL);
1743         eh = path[depth].p_hdr;
1744
1745         if (ex > EXT_FIRST_EXTENT(eh))
1746                 merge_done = ext4_ext_try_to_merge_right(inode, path, ex - 1);
1747
1748         if (!merge_done)
1749                 (void) ext4_ext_try_to_merge_right(inode, path, ex);
1750
1751         ext4_ext_try_to_merge_up(handle, inode, path);
1752 }
1753
1754 /*
1755  * check if a portion of the "newext" extent overlaps with an
1756  * existing extent.
1757  *
1758  * If there is an overlap discovered, it updates the length of the newext
1759  * such that there will be no overlap, and then returns 1.
1760  * If there is no overlap found, it returns 0.
1761  */
1762 static unsigned int ext4_ext_check_overlap(struct ext4_sb_info *sbi,
1763                                            struct inode *inode,
1764                                            struct ext4_extent *newext,
1765                                            struct ext4_ext_path *path)
1766 {
1767         ext4_lblk_t b1, b2;
1768         unsigned int depth, len1;
1769         unsigned int ret = 0;
1770
1771         b1 = le32_to_cpu(newext->ee_block);
1772         len1 = ext4_ext_get_actual_len(newext);
1773         depth = ext_depth(inode);
1774         if (!path[depth].p_ext)
1775                 goto out;
1776         b2 = EXT4_LBLK_CMASK(sbi, le32_to_cpu(path[depth].p_ext->ee_block));
1777
1778         /*
1779          * get the next allocated block if the extent in the path
1780          * is before the requested block(s)
1781          */
1782         if (b2 < b1) {
1783                 b2 = ext4_ext_next_allocated_block(path);
1784                 if (b2 == EXT_MAX_BLOCKS)
1785                         goto out;
1786                 b2 = EXT4_LBLK_CMASK(sbi, b2);
1787         }
1788
1789         /* check for wrap through zero on extent logical start block*/
1790         if (b1 + len1 < b1) {
1791                 len1 = EXT_MAX_BLOCKS - b1;
1792                 newext->ee_len = cpu_to_le16(len1);
1793                 ret = 1;
1794         }
1795
1796         /* check for overlap */
1797         if (b1 + len1 > b2) {
1798                 newext->ee_len = cpu_to_le16(b2 - b1);
1799                 ret = 1;
1800         }
1801 out:
1802         return ret;
1803 }
1804
1805 /*
1806  * ext4_ext_insert_extent:
1807  * tries to merge requsted extent into the existing extent or
1808  * inserts requested extent as new one into the tree,
1809  * creating new leaf in the no-space case.
1810  */
1811 int ext4_ext_insert_extent(handle_t *handle, struct inode *inode,
1812                                 struct ext4_ext_path *path,
1813                                 struct ext4_extent *newext, int flag)
1814 {
1815         struct ext4_extent_header *eh;
1816         struct ext4_extent *ex, *fex;
1817         struct ext4_extent *nearex; /* nearest extent */
1818         struct ext4_ext_path *npath = NULL;
1819         int depth, len, err;
1820         ext4_lblk_t next;
1821         unsigned uninitialized = 0;
1822         int flags = 0;
1823
1824         if (unlikely(ext4_ext_get_actual_len(newext) == 0)) {
1825                 EXT4_ERROR_INODE(inode, "ext4_ext_get_actual_len(newext) == 0");
1826                 return -EIO;
1827         }
1828         depth = ext_depth(inode);
1829         ex = path[depth].p_ext;
1830         eh = path[depth].p_hdr;
1831         if (unlikely(path[depth].p_hdr == NULL)) {
1832                 EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
1833                 return -EIO;
1834         }
1835
1836         /* try to insert block into found extent and return */
1837         if (ex && !(flag & EXT4_GET_BLOCKS_PRE_IO)) {
1838
1839                 /*
1840                  * Try to see whether we should rather test the extent on
1841                  * right from ex, or from the left of ex. This is because
1842                  * ext4_ext_find_extent() can return either extent on the
1843                  * left, or on the right from the searched position. This
1844                  * will make merging more effective.
1845                  */
1846                 if (ex < EXT_LAST_EXTENT(eh) &&
1847                     (le32_to_cpu(ex->ee_block) +
1848                     ext4_ext_get_actual_len(ex) <
1849                     le32_to_cpu(newext->ee_block))) {
1850                         ex += 1;
1851                         goto prepend;
1852                 } else if ((ex > EXT_FIRST_EXTENT(eh)) &&
1853                            (le32_to_cpu(newext->ee_block) +
1854                            ext4_ext_get_actual_len(newext) <
1855                            le32_to_cpu(ex->ee_block)))
1856                         ex -= 1;
1857
1858                 /* Try to append newex to the ex */
1859                 if (ext4_can_extents_be_merged(inode, ex, newext)) {
1860                         ext_debug("append [%d]%d block to %u:[%d]%d"
1861                                   "(from %llu)\n",
1862                                   ext4_ext_is_uninitialized(newext),
1863                                   ext4_ext_get_actual_len(newext),
1864                                   le32_to_cpu(ex->ee_block),
1865                                   ext4_ext_is_uninitialized(ex),
1866                                   ext4_ext_get_actual_len(ex),
1867                                   ext4_ext_pblock(ex));
1868                         err = ext4_ext_get_access(handle, inode,
1869                                                   path + depth);
1870                         if (err)
1871                                 return err;
1872
1873                         /*
1874                          * ext4_can_extents_be_merged should have checked
1875                          * that either both extents are uninitialized, or
1876                          * both aren't. Thus we need to check only one of
1877                          * them here.
1878                          */
1879                         if (ext4_ext_is_uninitialized(ex))
1880                                 uninitialized = 1;
1881                         ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
1882                                         + ext4_ext_get_actual_len(newext));
1883                         if (uninitialized)
1884                                 ext4_ext_mark_uninitialized(ex);
1885                         eh = path[depth].p_hdr;
1886                         nearex = ex;
1887                         goto merge;
1888                 }
1889
1890 prepend:
1891                 /* Try to prepend newex to the ex */
1892                 if (ext4_can_extents_be_merged(inode, newext, ex)) {
1893                         ext_debug("prepend %u[%d]%d block to %u:[%d]%d"
1894                                   "(from %llu)\n",
1895                                   le32_to_cpu(newext->ee_block),
1896                                   ext4_ext_is_uninitialized(newext),
1897                                   ext4_ext_get_actual_len(newext),
1898                                   le32_to_cpu(ex->ee_block),
1899                                   ext4_ext_is_uninitialized(ex),
1900                                   ext4_ext_get_actual_len(ex),
1901                                   ext4_ext_pblock(ex));
1902                         err = ext4_ext_get_access(handle, inode,
1903                                                   path + depth);
1904                         if (err)
1905                                 return err;
1906
1907                         /*
1908                          * ext4_can_extents_be_merged should have checked
1909                          * that either both extents are uninitialized, or
1910                          * both aren't. Thus we need to check only one of
1911                          * them here.
1912                          */
1913                         if (ext4_ext_is_uninitialized(ex))
1914                                 uninitialized = 1;
1915                         ex->ee_block = newext->ee_block;
1916                         ext4_ext_store_pblock(ex, ext4_ext_pblock(newext));
1917                         ex->ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex)
1918                                         + ext4_ext_get_actual_len(newext));
1919                         if (uninitialized)
1920                                 ext4_ext_mark_uninitialized(ex);
1921                         eh = path[depth].p_hdr;
1922                         nearex = ex;
1923                         goto merge;
1924                 }
1925         }
1926
1927         depth = ext_depth(inode);
1928         eh = path[depth].p_hdr;
1929         if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max))
1930                 goto has_space;
1931
1932         /* probably next leaf has space for us? */
1933         fex = EXT_LAST_EXTENT(eh);
1934         next = EXT_MAX_BLOCKS;
1935         if (le32_to_cpu(newext->ee_block) > le32_to_cpu(fex->ee_block))
1936                 next = ext4_ext_next_leaf_block(path);
1937         if (next != EXT_MAX_BLOCKS) {
1938                 ext_debug("next leaf block - %u\n", next);
1939                 BUG_ON(npath != NULL);
1940                 npath = ext4_ext_find_extent(inode, next, NULL);
1941                 if (IS_ERR(npath))
1942                         return PTR_ERR(npath);
1943                 BUG_ON(npath->p_depth != path->p_depth);
1944                 eh = npath[depth].p_hdr;
1945                 if (le16_to_cpu(eh->eh_entries) < le16_to_cpu(eh->eh_max)) {
1946                         ext_debug("next leaf isn't full(%d)\n",
1947                                   le16_to_cpu(eh->eh_entries));
1948                         path = npath;
1949                         goto has_space;
1950                 }
1951                 ext_debug("next leaf has no free space(%d,%d)\n",
1952                           le16_to_cpu(eh->eh_entries), le16_to_cpu(eh->eh_max));
1953         }
1954
1955         /*
1956          * There is no free space in the found leaf.
1957          * We're gonna add a new leaf in the tree.
1958          */
1959         if (flag & EXT4_GET_BLOCKS_METADATA_NOFAIL)
1960                 flags = EXT4_MB_USE_RESERVED;
1961         err = ext4_ext_create_new_leaf(handle, inode, flags, path, newext);
1962         if (err)
1963                 goto cleanup;
1964         depth = ext_depth(inode);
1965         eh = path[depth].p_hdr;
1966
1967 has_space:
1968         nearex = path[depth].p_ext;
1969
1970         err = ext4_ext_get_access(handle, inode, path + depth);
1971         if (err)
1972                 goto cleanup;
1973
1974         if (!nearex) {
1975                 /* there is no extent in this leaf, create first one */
1976                 ext_debug("first extent in the leaf: %u:%llu:[%d]%d\n",
1977                                 le32_to_cpu(newext->ee_block),
1978                                 ext4_ext_pblock(newext),
1979                                 ext4_ext_is_uninitialized(newext),
1980                                 ext4_ext_get_actual_len(newext));
1981                 nearex = EXT_FIRST_EXTENT(eh);
1982         } else {
1983                 if (le32_to_cpu(newext->ee_block)
1984                            > le32_to_cpu(nearex->ee_block)) {
1985                         /* Insert after */
1986                         ext_debug("insert %u:%llu:[%d]%d before: "
1987                                         "nearest %p\n",
1988                                         le32_to_cpu(newext->ee_block),
1989                                         ext4_ext_pblock(newext),
1990                                         ext4_ext_is_uninitialized(newext),
1991                                         ext4_ext_get_actual_len(newext),
1992                                         nearex);
1993                         nearex++;
1994                 } else {
1995                         /* Insert before */
1996                         BUG_ON(newext->ee_block == nearex->ee_block);
1997                         ext_debug("insert %u:%llu:[%d]%d after: "
1998                                         "nearest %p\n",
1999                                         le32_to_cpu(newext->ee_block),
2000                                         ext4_ext_pblock(newext),
2001                                         ext4_ext_is_uninitialized(newext),
2002                                         ext4_ext_get_actual_len(newext),
2003                                         nearex);
2004                 }
2005                 len = EXT_LAST_EXTENT(eh) - nearex + 1;
2006                 if (len > 0) {
2007                         ext_debug("insert %u:%llu:[%d]%d: "
2008                                         "move %d extents from 0x%p to 0x%p\n",
2009                                         le32_to_cpu(newext->ee_block),
2010                                         ext4_ext_pblock(newext),
2011                                         ext4_ext_is_uninitialized(newext),
2012                                         ext4_ext_get_actual_len(newext),
2013                                         len, nearex, nearex + 1);
2014                         memmove(nearex + 1, nearex,
2015                                 len * sizeof(struct ext4_extent));
2016                 }
2017         }
2018
2019         le16_add_cpu(&eh->eh_entries, 1);
2020         path[depth].p_ext = nearex;
2021         nearex->ee_block = newext->ee_block;
2022         ext4_ext_store_pblock(nearex, ext4_ext_pblock(newext));
2023         nearex->ee_len = newext->ee_len;
2024
2025 merge:
2026         /* try to merge extents */
2027         if (!(flag & EXT4_GET_BLOCKS_PRE_IO))
2028                 ext4_ext_try_to_merge(handle, inode, path, nearex);
2029
2030
2031         /* time to correct all indexes above */
2032         err = ext4_ext_correct_indexes(handle, inode, path);
2033         if (err)
2034                 goto cleanup;
2035
2036         err = ext4_ext_dirty(handle, inode, path + path->p_depth);
2037
2038 cleanup:
2039         if (npath) {
2040                 ext4_ext_drop_refs(npath);
2041                 kfree(npath);
2042         }
2043         return err;
2044 }
2045
2046 static int ext4_fill_fiemap_extents(struct inode *inode,
2047                                     ext4_lblk_t block, ext4_lblk_t num,
2048                                     struct fiemap_extent_info *fieinfo)
2049 {
2050         struct ext4_ext_path *path = NULL;
2051         struct ext4_extent *ex;
2052         struct extent_status es;
2053         ext4_lblk_t next, next_del, start = 0, end = 0;
2054         ext4_lblk_t last = block + num;
2055         int exists, depth = 0, err = 0;
2056         unsigned int flags = 0;
2057         unsigned char blksize_bits = inode->i_sb->s_blocksize_bits;
2058
2059         while (block < last && block != EXT_MAX_BLOCKS) {
2060                 num = last - block;
2061                 /* find extent for this block */
2062                 down_read(&EXT4_I(inode)->i_data_sem);
2063
2064                 if (path && ext_depth(inode) != depth) {
2065                         /* depth was changed. we have to realloc path */
2066                         kfree(path);
2067                         path = NULL;
2068                 }
2069
2070                 path = ext4_ext_find_extent(inode, block, path);
2071                 if (IS_ERR(path)) {
2072                         up_read(&EXT4_I(inode)->i_data_sem);
2073                         err = PTR_ERR(path);
2074                         path = NULL;
2075                         break;
2076                 }
2077
2078                 depth = ext_depth(inode);
2079                 if (unlikely(path[depth].p_hdr == NULL)) {
2080                         up_read(&EXT4_I(inode)->i_data_sem);
2081                         EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
2082                         err = -EIO;
2083                         break;
2084                 }
2085                 ex = path[depth].p_ext;
2086                 next = ext4_ext_next_allocated_block(path);
2087                 ext4_ext_drop_refs(path);
2088
2089                 flags = 0;
2090                 exists = 0;
2091                 if (!ex) {
2092                         /* there is no extent yet, so try to allocate
2093                          * all requested space */
2094                         start = block;
2095                         end = block + num;
2096                 } else if (le32_to_cpu(ex->ee_block) > block) {
2097                         /* need to allocate space before found extent */
2098                         start = block;
2099                         end = le32_to_cpu(ex->ee_block);
2100                         if (block + num < end)
2101                                 end = block + num;
2102                 } else if (block >= le32_to_cpu(ex->ee_block)
2103                                         + ext4_ext_get_actual_len(ex)) {
2104                         /* need to allocate space after found extent */
2105                         start = block;
2106                         end = block + num;
2107                         if (end >= next)
2108                                 end = next;
2109                 } else if (block >= le32_to_cpu(ex->ee_block)) {
2110                         /*
2111                          * some part of requested space is covered
2112                          * by found extent
2113                          */
2114                         start = block;
2115                         end = le32_to_cpu(ex->ee_block)
2116                                 + ext4_ext_get_actual_len(ex);
2117                         if (block + num < end)
2118                                 end = block + num;
2119                         exists = 1;
2120                 } else {
2121                         BUG();
2122                 }
2123                 BUG_ON(end <= start);
2124
2125                 if (!exists) {
2126                         es.es_lblk = start;
2127                         es.es_len = end - start;
2128                         es.es_pblk = 0;
2129                 } else {
2130                         es.es_lblk = le32_to_cpu(ex->ee_block);
2131                         es.es_len = ext4_ext_get_actual_len(ex);
2132                         es.es_pblk = ext4_ext_pblock(ex);
2133                         if (ext4_ext_is_uninitialized(ex))
2134                                 flags |= FIEMAP_EXTENT_UNWRITTEN;
2135                 }
2136
2137                 /*
2138                  * Find delayed extent and update es accordingly. We call
2139                  * it even in !exists case to find out whether es is the
2140                  * last existing extent or not.
2141                  */
2142                 next_del = ext4_find_delayed_extent(inode, &es);
2143                 if (!exists && next_del) {
2144                         exists = 1;
2145                         flags |= FIEMAP_EXTENT_DELALLOC;
2146                 }
2147                 up_read(&EXT4_I(inode)->i_data_sem);
2148
2149                 if (unlikely(es.es_len == 0)) {
2150                         EXT4_ERROR_INODE(inode, "es.es_len == 0");
2151                         err = -EIO;
2152                         break;
2153                 }
2154
2155                 /*
2156                  * This is possible iff next == next_del == EXT_MAX_BLOCKS.
2157                  * we need to check next == EXT_MAX_BLOCKS because it is
2158                  * possible that an extent is with unwritten and delayed
2159                  * status due to when an extent is delayed allocated and
2160                  * is allocated by fallocate status tree will track both of
2161                  * them in a extent.
2162                  *
2163                  * So we could return a unwritten and delayed extent, and
2164                  * its block is equal to 'next'.
2165                  */
2166                 if (next == next_del && next == EXT_MAX_BLOCKS) {
2167                         flags |= FIEMAP_EXTENT_LAST;
2168                         if (unlikely(next_del != EXT_MAX_BLOCKS ||
2169                                      next != EXT_MAX_BLOCKS)) {
2170                                 EXT4_ERROR_INODE(inode,
2171                                                  "next extent == %u, next "
2172                                                  "delalloc extent = %u",
2173                                                  next, next_del);
2174                                 err = -EIO;
2175                                 break;
2176                         }
2177                 }
2178
2179                 if (exists) {
2180                         err = fiemap_fill_next_extent(fieinfo,
2181                                 (__u64)es.es_lblk << blksize_bits,
2182                                 (__u64)es.es_pblk << blksize_bits,
2183                                 (__u64)es.es_len << blksize_bits,
2184                                 flags);
2185                         if (err < 0)
2186                                 break;
2187                         if (err == 1) {
2188                                 err = 0;
2189                                 break;
2190                         }
2191                 }
2192
2193                 block = es.es_lblk + es.es_len;
2194         }
2195
2196         if (path) {
2197                 ext4_ext_drop_refs(path);
2198                 kfree(path);
2199         }
2200
2201         return err;
2202 }
2203
2204 /*
2205  * ext4_ext_put_gap_in_cache:
2206  * calculate boundaries of the gap that the requested block fits into
2207  * and cache this gap
2208  */
2209 static void
2210 ext4_ext_put_gap_in_cache(struct inode *inode, struct ext4_ext_path *path,
2211                                 ext4_lblk_t block)
2212 {
2213         int depth = ext_depth(inode);
2214         unsigned long len;
2215         ext4_lblk_t lblock;
2216         struct ext4_extent *ex;
2217
2218         ex = path[depth].p_ext;
2219         if (ex == NULL) {
2220                 /*
2221                  * there is no extent yet, so gap is [0;-] and we
2222                  * don't cache it
2223                  */
2224                 ext_debug("cache gap(whole file):");
2225         } else if (block < le32_to_cpu(ex->ee_block)) {
2226                 lblock = block;
2227                 len = le32_to_cpu(ex->ee_block) - block;
2228                 ext_debug("cache gap(before): %u [%u:%u]",
2229                                 block,
2230                                 le32_to_cpu(ex->ee_block),
2231                                  ext4_ext_get_actual_len(ex));
2232                 if (!ext4_find_delalloc_range(inode, lblock, lblock + len - 1))
2233                         ext4_es_insert_extent(inode, lblock, len, ~0,
2234                                               EXTENT_STATUS_HOLE);
2235         } else if (block >= le32_to_cpu(ex->ee_block)
2236                         + ext4_ext_get_actual_len(ex)) {
2237                 ext4_lblk_t next;
2238                 lblock = le32_to_cpu(ex->ee_block)
2239                         + ext4_ext_get_actual_len(ex);
2240
2241                 next = ext4_ext_next_allocated_block(path);
2242                 ext_debug("cache gap(after): [%u:%u] %u",
2243                                 le32_to_cpu(ex->ee_block),
2244                                 ext4_ext_get_actual_len(ex),
2245                                 block);
2246                 BUG_ON(next == lblock);
2247                 len = next - lblock;
2248                 if (!ext4_find_delalloc_range(inode, lblock, lblock + len - 1))
2249                         ext4_es_insert_extent(inode, lblock, len, ~0,
2250                                               EXTENT_STATUS_HOLE);
2251         } else {
2252                 lblock = len = 0;
2253                 BUG();
2254         }
2255
2256         ext_debug(" -> %u:%lu\n", lblock, len);
2257 }
2258
2259 /*
2260  * ext4_ext_rm_idx:
2261  * removes index from the index block.
2262  */
2263 static int ext4_ext_rm_idx(handle_t *handle, struct inode *inode,
2264                         struct ext4_ext_path *path, int depth)
2265 {
2266         int err;
2267         ext4_fsblk_t leaf;
2268
2269         /* free index block */
2270         depth--;
2271         path = path + depth;
2272         leaf = ext4_idx_pblock(path->p_idx);
2273         if (unlikely(path->p_hdr->eh_entries == 0)) {
2274                 EXT4_ERROR_INODE(inode, "path->p_hdr->eh_entries == 0");
2275                 return -EIO;
2276         }
2277         err = ext4_ext_get_access(handle, inode, path);
2278         if (err)
2279                 return err;
2280
2281         if (path->p_idx != EXT_LAST_INDEX(path->p_hdr)) {
2282                 int len = EXT_LAST_INDEX(path->p_hdr) - path->p_idx;
2283                 len *= sizeof(struct ext4_extent_idx);
2284                 memmove(path->p_idx, path->p_idx + 1, len);
2285         }
2286
2287         le16_add_cpu(&path->p_hdr->eh_entries, -1);
2288         err = ext4_ext_dirty(handle, inode, path);
2289         if (err)
2290                 return err;
2291         ext_debug("index is empty, remove it, free block %llu\n", leaf);
2292         trace_ext4_ext_rm_idx(inode, leaf);
2293
2294         ext4_free_blocks(handle, inode, NULL, leaf, 1,
2295                          EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET);
2296
2297         while (--depth >= 0) {
2298                 if (path->p_idx != EXT_FIRST_INDEX(path->p_hdr))
2299                         break;
2300                 path--;
2301                 err = ext4_ext_get_access(handle, inode, path);
2302                 if (err)
2303                         break;
2304                 path->p_idx->ei_block = (path+1)->p_idx->ei_block;
2305                 err = ext4_ext_dirty(handle, inode, path);
2306                 if (err)
2307                         break;
2308         }
2309         return err;
2310 }
2311
2312 /*
2313  * ext4_ext_calc_credits_for_single_extent:
2314  * This routine returns max. credits that needed to insert an extent
2315  * to the extent tree.
2316  * When pass the actual path, the caller should calculate credits
2317  * under i_data_sem.
2318  */
2319 int ext4_ext_calc_credits_for_single_extent(struct inode *inode, int nrblocks,
2320                                                 struct ext4_ext_path *path)
2321 {
2322         if (path) {
2323                 int depth = ext_depth(inode);
2324                 int ret = 0;
2325
2326                 /* probably there is space in leaf? */
2327                 if (le16_to_cpu(path[depth].p_hdr->eh_entries)
2328                                 < le16_to_cpu(path[depth].p_hdr->eh_max)) {
2329
2330                         /*
2331                          *  There are some space in the leaf tree, no
2332                          *  need to account for leaf block credit
2333                          *
2334                          *  bitmaps and block group descriptor blocks
2335                          *  and other metadata blocks still need to be
2336                          *  accounted.
2337                          */
2338                         /* 1 bitmap, 1 block group descriptor */
2339                         ret = 2 + EXT4_META_TRANS_BLOCKS(inode->i_sb);
2340                         return ret;
2341                 }
2342         }
2343
2344         return ext4_chunk_trans_blocks(inode, nrblocks);
2345 }
2346
2347 /*
2348  * How many index/leaf blocks need to change/allocate to modify nrblocks?
2349  *
2350  * if nrblocks are fit in a single extent (chunk flag is 1), then
2351  * in the worse case, each tree level index/leaf need to be changed
2352  * if the tree split due to insert a new extent, then the old tree
2353  * index/leaf need to be updated too
2354  *
2355  * If the nrblocks are discontiguous, they could cause
2356  * the whole tree split more than once, but this is really rare.
2357  */
2358 int ext4_ext_index_trans_blocks(struct inode *inode, int nrblocks, int chunk)
2359 {
2360         int index;
2361         int depth;
2362
2363         /* If we are converting the inline data, only one is needed here. */
2364         if (ext4_has_inline_data(inode))
2365                 return 1;
2366
2367         depth = ext_depth(inode);
2368
2369         if (chunk)
2370                 index = depth * 2;
2371         else
2372                 index = depth * 3;
2373
2374         return index;
2375 }
2376
2377 static int ext4_remove_blocks(handle_t *handle, struct inode *inode,
2378                               struct ext4_extent *ex,
2379                               ext4_fsblk_t *partial_cluster,
2380                               ext4_lblk_t from, ext4_lblk_t to)
2381 {
2382         struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2383         unsigned short ee_len =  ext4_ext_get_actual_len(ex);
2384         ext4_fsblk_t pblk;
2385         int flags = 0;
2386
2387         if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode))
2388                 flags |= EXT4_FREE_BLOCKS_METADATA | EXT4_FREE_BLOCKS_FORGET;
2389         else if (ext4_should_journal_data(inode))
2390                 flags |= EXT4_FREE_BLOCKS_FORGET;
2391
2392         /*
2393          * For bigalloc file systems, we never free a partial cluster
2394          * at the beginning of the extent.  Instead, we make a note
2395          * that we tried freeing the cluster, and check to see if we
2396          * need to free it on a subsequent call to ext4_remove_blocks,
2397          * or at the end of the ext4_truncate() operation.
2398          */
2399         flags |= EXT4_FREE_BLOCKS_NOFREE_FIRST_CLUSTER;
2400
2401         trace_ext4_remove_blocks(inode, ex, from, to, *partial_cluster);
2402         /*
2403          * If we have a partial cluster, and it's different from the
2404          * cluster of the last block, we need to explicitly free the
2405          * partial cluster here.
2406          */
2407         pblk = ext4_ext_pblock(ex) + ee_len - 1;
2408         if (*partial_cluster && (EXT4_B2C(sbi, pblk) != *partial_cluster)) {
2409                 ext4_free_blocks(handle, inode, NULL,
2410                                  EXT4_C2B(sbi, *partial_cluster),
2411                                  sbi->s_cluster_ratio, flags);
2412                 *partial_cluster = 0;
2413         }
2414
2415 #ifdef EXTENTS_STATS
2416         {
2417                 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2418                 spin_lock(&sbi->s_ext_stats_lock);
2419                 sbi->s_ext_blocks += ee_len;
2420                 sbi->s_ext_extents++;
2421                 if (ee_len < sbi->s_ext_min)
2422                         sbi->s_ext_min = ee_len;
2423                 if (ee_len > sbi->s_ext_max)
2424                         sbi->s_ext_max = ee_len;
2425                 if (ext_depth(inode) > sbi->s_depth_max)
2426                         sbi->s_depth_max = ext_depth(inode);
2427                 spin_unlock(&sbi->s_ext_stats_lock);
2428         }
2429 #endif
2430         if (from >= le32_to_cpu(ex->ee_block)
2431             && to == le32_to_cpu(ex->ee_block) + ee_len - 1) {
2432                 /* tail removal */
2433                 ext4_lblk_t num;
2434
2435                 num = le32_to_cpu(ex->ee_block) + ee_len - from;
2436                 pblk = ext4_ext_pblock(ex) + ee_len - num;
2437                 ext_debug("free last %u blocks starting %llu\n", num, pblk);
2438                 ext4_free_blocks(handle, inode, NULL, pblk, num, flags);
2439                 /*
2440                  * If the block range to be freed didn't start at the
2441                  * beginning of a cluster, and we removed the entire
2442                  * extent, save the partial cluster here, since we
2443                  * might need to delete if we determine that the
2444                  * truncate operation has removed all of the blocks in
2445                  * the cluster.
2446                  */
2447                 if (EXT4_PBLK_COFF(sbi, pblk) &&
2448                     (ee_len == num))
2449                         *partial_cluster = EXT4_B2C(sbi, pblk);
2450                 else
2451                         *partial_cluster = 0;
2452         } else if (from == le32_to_cpu(ex->ee_block)
2453                    && to <= le32_to_cpu(ex->ee_block) + ee_len - 1) {
2454                 /* head removal */
2455                 ext4_lblk_t num;
2456                 ext4_fsblk_t start;
2457
2458                 num = to - from;
2459                 start = ext4_ext_pblock(ex);
2460
2461                 ext_debug("free first %u blocks starting %llu\n", num, start);
2462                 ext4_free_blocks(handle, inode, NULL, start, num, flags);
2463
2464         } else {
2465                 printk(KERN_INFO "strange request: removal(2) "
2466                                 "%u-%u from %u:%u\n",
2467                                 from, to, le32_to_cpu(ex->ee_block), ee_len);
2468         }
2469         return 0;
2470 }
2471
2472
2473 /*
2474  * ext4_ext_rm_leaf() Removes the extents associated with the
2475  * blocks appearing between "start" and "end", and splits the extents
2476  * if "start" and "end" appear in the same extent
2477  *
2478  * @handle: The journal handle
2479  * @inode:  The files inode
2480  * @path:   The path to the leaf
2481  * @start:  The first block to remove
2482  * @end:   The last block to remove
2483  */
2484 static int
2485 ext4_ext_rm_leaf(handle_t *handle, struct inode *inode,
2486                  struct ext4_ext_path *path, ext4_fsblk_t *partial_cluster,
2487                  ext4_lblk_t start, ext4_lblk_t end)
2488 {
2489         struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2490         int err = 0, correct_index = 0;
2491         int depth = ext_depth(inode), credits;
2492         struct ext4_extent_header *eh;
2493         ext4_lblk_t a, b;
2494         unsigned num;
2495         ext4_lblk_t ex_ee_block;
2496         unsigned short ex_ee_len;
2497         unsigned uninitialized = 0;
2498         struct ext4_extent *ex;
2499
2500         /* the header must be checked already in ext4_ext_remove_space() */
2501         ext_debug("truncate since %u in leaf to %u\n", start, end);
2502         if (!path[depth].p_hdr)
2503                 path[depth].p_hdr = ext_block_hdr(path[depth].p_bh);
2504         eh = path[depth].p_hdr;
2505         if (unlikely(path[depth].p_hdr == NULL)) {
2506                 EXT4_ERROR_INODE(inode, "path[%d].p_hdr == NULL", depth);
2507                 return -EIO;
2508         }
2509         /* find where to start removing */
2510         ex = EXT_LAST_EXTENT(eh);
2511
2512         ex_ee_block = le32_to_cpu(ex->ee_block);
2513         ex_ee_len = ext4_ext_get_actual_len(ex);
2514
2515         /*
2516          * If we're starting with an extent other than the last one in the
2517          * node, we need to see if it shares a cluster with the extent to
2518          * the right (towards the end of the file). If its leftmost cluster
2519          * is this extent's rightmost cluster and it is not cluster aligned,
2520          * we'll mark it as a partial that is not to be deallocated.
2521          */
2522
2523         if (ex != EXT_LAST_EXTENT(eh)) {
2524                 ext4_fsblk_t current_pblk, right_pblk;
2525                 long long current_cluster, right_cluster;
2526
2527                 current_pblk = ext4_ext_pblock(ex) + ex_ee_len - 1;
2528                 current_cluster = (long long)EXT4_B2C(sbi, current_pblk);
2529                 right_pblk = ext4_ext_pblock(ex + 1);
2530                 right_cluster = (long long)EXT4_B2C(sbi, right_pblk);
2531                 if (current_cluster == right_cluster &&
2532                         EXT4_PBLK_COFF(sbi, right_pblk))
2533                         *partial_cluster = -right_cluster;
2534         }
2535
2536         trace_ext4_ext_rm_leaf(inode, start, ex, *partial_cluster);
2537
2538         while (ex >= EXT_FIRST_EXTENT(eh) &&
2539                         ex_ee_block + ex_ee_len > start) {
2540
2541                 if (ext4_ext_is_uninitialized(ex))
2542                         uninitialized = 1;
2543                 else
2544                         uninitialized = 0;
2545
2546                 ext_debug("remove ext %u:[%d]%d\n", ex_ee_block,
2547                          uninitialized, ex_ee_len);
2548                 path[depth].p_ext = ex;
2549
2550                 a = ex_ee_block > start ? ex_ee_block : start;
2551                 b = ex_ee_block+ex_ee_len - 1 < end ?
2552                         ex_ee_block+ex_ee_len - 1 : end;
2553
2554                 ext_debug("  border %u:%u\n", a, b);
2555
2556                 /* If this extent is beyond the end of the hole, skip it */
2557                 if (end < ex_ee_block) {
2558                         ex--;
2559                         ex_ee_block = le32_to_cpu(ex->ee_block);
2560                         ex_ee_len = ext4_ext_get_actual_len(ex);
2561                         continue;
2562                 } else if (b != ex_ee_block + ex_ee_len - 1) {
2563                         EXT4_ERROR_INODE(inode,
2564                                          "can not handle truncate %u:%u "
2565                                          "on extent %u:%u",
2566                                          start, end, ex_ee_block,
2567                                          ex_ee_block + ex_ee_len - 1);
2568                         err = -EIO;
2569                         goto out;
2570                 } else if (a != ex_ee_block) {
2571                         /* remove tail of the extent */
2572                         num = a - ex_ee_block;
2573                 } else {
2574                         /* remove whole extent: excellent! */
2575                         num = 0;
2576                 }
2577                 /*
2578                  * 3 for leaf, sb, and inode plus 2 (bmap and group
2579                  * descriptor) for each block group; assume two block
2580                  * groups plus ex_ee_len/blocks_per_block_group for
2581                  * the worst case
2582                  */
2583                 credits = 7 + 2*(ex_ee_len/EXT4_BLOCKS_PER_GROUP(inode->i_sb));
2584                 if (ex == EXT_FIRST_EXTENT(eh)) {
2585                         correct_index = 1;
2586                         credits += (ext_depth(inode)) + 1;
2587                 }
2588                 credits += EXT4_MAXQUOTAS_TRANS_BLOCKS(inode->i_sb);
2589
2590                 err = ext4_ext_truncate_extend_restart(handle, inode, credits);
2591                 if (err)
2592                         goto out;
2593
2594                 err = ext4_ext_get_access(handle, inode, path + depth);
2595                 if (err)
2596                         goto out;
2597
2598                 err = ext4_remove_blocks(handle, inode, ex, partial_cluster,
2599                                          a, b);
2600                 if (err)
2601                         goto out;
2602
2603                 if (num == 0)
2604                         /* this extent is removed; mark slot entirely unused */
2605                         ext4_ext_store_pblock(ex, 0);
2606
2607                 ex->ee_len = cpu_to_le16(num);
2608                 /*
2609                  * Do not mark uninitialized if all the blocks in the
2610                  * extent have been removed.
2611                  */
2612                 if (uninitialized && num)
2613                         ext4_ext_mark_uninitialized(ex);
2614                 /*
2615                  * If the extent was completely released,
2616                  * we need to remove it from the leaf
2617                  */
2618                 if (num == 0) {
2619                         if (end != EXT_MAX_BLOCKS - 1) {
2620                                 /*
2621                                  * For hole punching, we need to scoot all the
2622                                  * extents up when an extent is removed so that
2623                                  * we dont have blank extents in the middle
2624                                  */
2625                                 memmove(ex, ex+1, (EXT_LAST_EXTENT(eh) - ex) *
2626                                         sizeof(struct ext4_extent));
2627
2628                                 /* Now get rid of the one at the end */
2629                                 memset(EXT_LAST_EXTENT(eh), 0,
2630                                         sizeof(struct ext4_extent));
2631                         }
2632                         le16_add_cpu(&eh->eh_entries, -1);
2633                 } else
2634                         *partial_cluster = 0;
2635
2636                 err = ext4_ext_dirty(handle, inode, path + depth);
2637                 if (err)
2638                         goto out;
2639
2640                 ext_debug("new extent: %u:%u:%llu\n", ex_ee_block, num,
2641                                 ext4_ext_pblock(ex));
2642                 ex--;
2643                 ex_ee_block = le32_to_cpu(ex->ee_block);
2644                 ex_ee_len = ext4_ext_get_actual_len(ex);
2645         }
2646
2647         if (correct_index && eh->eh_entries)
2648                 err = ext4_ext_correct_indexes(handle, inode, path);
2649
2650         /*
2651          * If there is still a entry in the leaf node, check to see if
2652          * it references the partial cluster.  This is the only place
2653          * where it could; if it doesn't, we can free the cluster.
2654          */
2655         if (*partial_cluster && ex >= EXT_FIRST_EXTENT(eh) &&
2656             (EXT4_B2C(sbi, ext4_ext_pblock(ex) + ex_ee_len - 1) !=
2657              *partial_cluster)) {
2658                 int flags = EXT4_FREE_BLOCKS_FORGET;
2659
2660                 if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode))
2661                         flags |= EXT4_FREE_BLOCKS_METADATA;
2662
2663                 ext4_free_blocks(handle, inode, NULL,
2664                                  EXT4_C2B(sbi, *partial_cluster),
2665                                  sbi->s_cluster_ratio, flags);
2666                 *partial_cluster = 0;
2667         }
2668
2669         /* if this leaf is free, then we should
2670          * remove it from index block above */
2671         if (err == 0 && eh->eh_entries == 0 && path[depth].p_bh != NULL)
2672                 err = ext4_ext_rm_idx(handle, inode, path, depth);
2673
2674 out:
2675         return err;
2676 }
2677
2678 /*
2679  * ext4_ext_more_to_rm:
2680  * returns 1 if current index has to be freed (even partial)
2681  */
2682 static int
2683 ext4_ext_more_to_rm(struct ext4_ext_path *path)
2684 {
2685         BUG_ON(path->p_idx == NULL);
2686
2687         if (path->p_idx < EXT_FIRST_INDEX(path->p_hdr))
2688                 return 0;
2689
2690         /*
2691          * if truncate on deeper level happened, it wasn't partial,
2692          * so we have to consider current index for truncation
2693          */
2694         if (le16_to_cpu(path->p_hdr->eh_entries) == path->p_block)
2695                 return 0;
2696         return 1;
2697 }
2698
2699 int ext4_ext_remove_space(struct inode *inode, ext4_lblk_t start,
2700                           ext4_lblk_t end)
2701 {
2702         struct super_block *sb = inode->i_sb;
2703         int depth = ext_depth(inode);
2704         struct ext4_ext_path *path = NULL;
2705         ext4_fsblk_t partial_cluster = 0;
2706         handle_t *handle;
2707         int i = 0, err = 0;
2708
2709         ext_debug("truncate since %u to %u\n", start, end);
2710
2711         /* probably first extent we're gonna free will be last in block */
2712         handle = ext4_journal_start(inode, EXT4_HT_TRUNCATE, depth + 1);
2713         if (IS_ERR(handle))
2714                 return PTR_ERR(handle);
2715
2716 again:
2717         trace_ext4_ext_remove_space(inode, start, depth);
2718
2719         /*
2720          * Check if we are removing extents inside the extent tree. If that
2721          * is the case, we are going to punch a hole inside the extent tree
2722          * so we have to check whether we need to split the extent covering
2723          * the last block to remove so we can easily remove the part of it
2724          * in ext4_ext_rm_leaf().
2725          */
2726         if (end < EXT_MAX_BLOCKS - 1) {
2727                 struct ext4_extent *ex;
2728                 ext4_lblk_t ee_block;
2729
2730                 /* find extent for this block */
2731                 path = ext4_ext_find_extent(inode, end, NULL);
2732                 if (IS_ERR(path)) {
2733                         ext4_journal_stop(handle);
2734                         return PTR_ERR(path);
2735                 }
2736                 depth = ext_depth(inode);
2737                 /* Leaf not may not exist only if inode has no blocks at all */
2738                 ex = path[depth].p_ext;
2739                 if (!ex) {
2740                         if (depth) {
2741                                 EXT4_ERROR_INODE(inode,
2742                                                  "path[%d].p_hdr == NULL",
2743                                                  depth);
2744                                 err = -EIO;
2745                         }
2746                         goto out;
2747                 }
2748
2749                 ee_block = le32_to_cpu(ex->ee_block);
2750
2751                 /*
2752                  * See if the last block is inside the extent, if so split
2753                  * the extent at 'end' block so we can easily remove the
2754                  * tail of the first part of the split extent in
2755                  * ext4_ext_rm_leaf().
2756                  */
2757                 if (end >= ee_block &&
2758                     end < ee_block + ext4_ext_get_actual_len(ex) - 1) {
2759                         int split_flag = 0;
2760
2761                         if (ext4_ext_is_uninitialized(ex))
2762                                 split_flag = EXT4_EXT_MARK_UNINIT1 |
2763                                              EXT4_EXT_MARK_UNINIT2;
2764
2765                         /*
2766                          * Split the extent in two so that 'end' is the last
2767                          * block in the first new extent. Also we should not
2768                          * fail removing space due to ENOSPC so try to use
2769                          * reserved block if that happens.
2770                          */
2771                         err = ext4_split_extent_at(handle, inode, path,
2772                                         end + 1, split_flag,
2773                                         EXT4_GET_BLOCKS_PRE_IO |
2774                                         EXT4_GET_BLOCKS_METADATA_NOFAIL);
2775
2776                         if (err < 0)
2777                                 goto out;
2778                 }
2779         }
2780         /*
2781          * We start scanning from right side, freeing all the blocks
2782          * after i_size and walking into the tree depth-wise.
2783          */
2784         depth = ext_depth(inode);
2785         if (path) {
2786                 int k = i = depth;
2787                 while (--k > 0)
2788                         path[k].p_block =
2789                                 le16_to_cpu(path[k].p_hdr->eh_entries)+1;
2790         } else {
2791                 path = kzalloc(sizeof(struct ext4_ext_path) * (depth + 1),
2792                                GFP_NOFS);
2793                 if (path == NULL) {
2794                         ext4_journal_stop(handle);
2795                         return -ENOMEM;
2796                 }
2797                 path[0].p_depth = depth;
2798                 path[0].p_hdr = ext_inode_hdr(inode);
2799                 i = 0;
2800
2801                 if (ext4_ext_check(inode, path[0].p_hdr, depth)) {
2802                         err = -EIO;
2803                         goto out;
2804                 }
2805         }
2806         err = 0;
2807
2808         while (i >= 0 && err == 0) {
2809                 if (i == depth) {
2810                         /* this is leaf block */
2811                         err = ext4_ext_rm_leaf(handle, inode, path,
2812                                                &partial_cluster, start,
2813                                                end);
2814                         /* root level has p_bh == NULL, brelse() eats this */
2815                         brelse(path[i].p_bh);
2816                         path[i].p_bh = NULL;
2817                         i--;
2818                         continue;
2819                 }
2820
2821                 /* this is index block */
2822                 if (!path[i].p_hdr) {
2823                         ext_debug("initialize header\n");
2824                         path[i].p_hdr = ext_block_hdr(path[i].p_bh);
2825                 }
2826
2827                 if (!path[i].p_idx) {
2828                         /* this level hasn't been touched yet */
2829                         path[i].p_idx = EXT_LAST_INDEX(path[i].p_hdr);
2830                         path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries)+1;
2831                         ext_debug("init index ptr: hdr 0x%p, num %d\n",
2832                                   path[i].p_hdr,
2833                                   le16_to_cpu(path[i].p_hdr->eh_entries));
2834                 } else {
2835                         /* we were already here, see at next index */
2836                         path[i].p_idx--;
2837                 }
2838
2839                 ext_debug("level %d - index, first 0x%p, cur 0x%p\n",
2840                                 i, EXT_FIRST_INDEX(path[i].p_hdr),
2841                                 path[i].p_idx);
2842                 if (ext4_ext_more_to_rm(path + i)) {
2843                         struct buffer_head *bh;
2844                         /* go to the next level */
2845                         ext_debug("move to level %d (block %llu)\n",
2846                                   i + 1, ext4_idx_pblock(path[i].p_idx));
2847                         memset(path + i + 1, 0, sizeof(*path));
2848                         bh = sb_bread(sb, ext4_idx_pblock(path[i].p_idx));
2849                         if (!bh) {
2850                                 /* should we reset i_size? */
2851                                 err = -EIO;
2852                                 break;
2853                         }
2854                         if (WARN_ON(i + 1 > depth)) {
2855                                 err = -EIO;
2856                                 break;
2857                         }
2858                         if (ext4_ext_check_block(inode, ext_block_hdr(bh),
2859                                                         depth - i - 1, bh)) {
2860                                 err = -EIO;
2861                                 break;
2862                         }
2863                         path[i + 1].p_bh = bh;
2864
2865                         /* save actual number of indexes since this
2866                          * number is changed at the next iteration */
2867                         path[i].p_block = le16_to_cpu(path[i].p_hdr->eh_entries);
2868                         i++;
2869                 } else {
2870                         /* we finished processing this index, go up */
2871                         if (path[i].p_hdr->eh_entries == 0 && i > 0) {
2872                                 /* index is empty, remove it;
2873                                  * handle must be already prepared by the
2874                                  * truncatei_leaf() */
2875                                 err = ext4_ext_rm_idx(handle, inode, path, i);
2876                         }
2877                         /* root level has p_bh == NULL, brelse() eats this */
2878                         brelse(path[i].p_bh);
2879                         path[i].p_bh = NULL;
2880                         i--;
2881                         ext_debug("return to level %d\n", i);
2882                 }
2883         }
2884
2885         trace_ext4_ext_remove_space_done(inode, start, depth, partial_cluster,
2886                         path->p_hdr->eh_entries);
2887
2888         /* If we still have something in the partial cluster and we have removed
2889          * even the first extent, then we should free the blocks in the partial
2890          * cluster as well. */
2891         if (partial_cluster && path->p_hdr->eh_entries == 0) {
2892                 int flags = EXT4_FREE_BLOCKS_FORGET;
2893
2894                 if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode))
2895                         flags |= EXT4_FREE_BLOCKS_METADATA;
2896
2897                 ext4_free_blocks(handle, inode, NULL,
2898                                  EXT4_C2B(EXT4_SB(sb), partial_cluster),
2899                                  EXT4_SB(sb)->s_cluster_ratio, flags);
2900                 partial_cluster = 0;
2901         }
2902
2903         /* TODO: flexible tree reduction should be here */
2904         if (path->p_hdr->eh_entries == 0) {
2905                 /*
2906                  * truncate to zero freed all the tree,
2907                  * so we need to correct eh_depth
2908                  */
2909                 err = ext4_ext_get_access(handle, inode, path);
2910                 if (err == 0) {
2911                         ext_inode_hdr(inode)->eh_depth = 0;
2912                         ext_inode_hdr(inode)->eh_max =
2913                                 cpu_to_le16(ext4_ext_space_root(inode, 0));
2914                         err = ext4_ext_dirty(handle, inode, path);
2915                 }
2916         }
2917 out:
2918         ext4_ext_drop_refs(path);
2919         kfree(path);
2920         if (err == -EAGAIN) {
2921                 path = NULL;
2922                 goto again;
2923         }
2924         ext4_journal_stop(handle);
2925
2926         return err;
2927 }
2928
2929 /*
2930  * called at mount time
2931  */
2932 void ext4_ext_init(struct super_block *sb)
2933 {
2934         /*
2935          * possible initialization would be here
2936          */
2937
2938         if (EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS)) {
2939 #if defined(AGGRESSIVE_TEST) || defined(CHECK_BINSEARCH) || defined(EXTENTS_STATS)
2940                 printk(KERN_INFO "EXT4-fs: file extents enabled"
2941 #ifdef AGGRESSIVE_TEST
2942                        ", aggressive tests"
2943 #endif
2944 #ifdef CHECK_BINSEARCH
2945                        ", check binsearch"
2946 #endif
2947 #ifdef EXTENTS_STATS
2948                        ", stats"
2949 #endif
2950                        "\n");
2951 #endif
2952 #ifdef EXTENTS_STATS
2953                 spin_lock_init(&EXT4_SB(sb)->s_ext_stats_lock);
2954                 EXT4_SB(sb)->s_ext_min = 1 << 30;
2955                 EXT4_SB(sb)->s_ext_max = 0;
2956 #endif
2957         }
2958 }
2959
2960 /*
2961  * called at umount time
2962  */
2963 void ext4_ext_release(struct super_block *sb)
2964 {
2965         if (!EXT4_HAS_INCOMPAT_FEATURE(sb, EXT4_FEATURE_INCOMPAT_EXTENTS))
2966                 return;
2967
2968 #ifdef EXTENTS_STATS
2969         if (EXT4_SB(sb)->s_ext_blocks && EXT4_SB(sb)->s_ext_extents) {
2970                 struct ext4_sb_info *sbi = EXT4_SB(sb);
2971                 printk(KERN_ERR "EXT4-fs: %lu blocks in %lu extents (%lu ave)\n",
2972                         sbi->s_ext_blocks, sbi->s_ext_extents,
2973                         sbi->s_ext_blocks / sbi->s_ext_extents);
2974                 printk(KERN_ERR "EXT4-fs: extents: %lu min, %lu max, max depth %lu\n",
2975                         sbi->s_ext_min, sbi->s_ext_max, sbi->s_depth_max);
2976         }
2977 #endif
2978 }
2979
2980 /* FIXME!! we need to try to merge to left or right after zero-out  */
2981 static int ext4_ext_zeroout(struct inode *inode, struct ext4_extent *ex)
2982 {
2983         ext4_fsblk_t ee_pblock;
2984         unsigned int ee_len;
2985         int ret;
2986
2987         ee_len    = ext4_ext_get_actual_len(ex);
2988         ee_pblock = ext4_ext_pblock(ex);
2989
2990         ret = sb_issue_zeroout(inode->i_sb, ee_pblock, ee_len, GFP_NOFS);
2991         if (ret > 0)
2992                 ret = 0;
2993
2994         return ret;
2995 }
2996
2997 /*
2998  * ext4_split_extent_at() splits an extent at given block.
2999  *
3000  * @handle: the journal handle
3001  * @inode: the file inode
3002  * @path: the path to the extent
3003  * @split: the logical block where the extent is splitted.
3004  * @split_flags: indicates if the extent could be zeroout if split fails, and
3005  *               the states(init or uninit) of new extents.
3006  * @flags: flags used to insert new extent to extent tree.
3007  *
3008  *
3009  * Splits extent [a, b] into two extents [a, @split) and [@split, b], states
3010  * of which are deterimined by split_flag.
3011  *
3012  * There are two cases:
3013  *  a> the extent are splitted into two extent.
3014  *  b> split is not needed, and just mark the extent.
3015  *
3016  * return 0 on success.
3017  */
3018 static int ext4_split_extent_at(handle_t *handle,
3019                              struct inode *inode,
3020                              struct ext4_ext_path *path,
3021                              ext4_lblk_t split,
3022                              int split_flag,
3023                              int flags)
3024 {
3025         ext4_fsblk_t newblock;
3026         ext4_lblk_t ee_block;
3027         struct ext4_extent *ex, newex, orig_ex, zero_ex;
3028         struct ext4_extent *ex2 = NULL;
3029         unsigned int ee_len, depth;
3030         int err = 0;
3031
3032         BUG_ON((split_flag & (EXT4_EXT_DATA_VALID1 | EXT4_EXT_DATA_VALID2)) ==
3033                (EXT4_EXT_DATA_VALID1 | EXT4_EXT_DATA_VALID2));
3034
3035         ext_debug("ext4_split_extents_at: inode %lu, logical"
3036                 "block %llu\n", inode->i_ino, (unsigned long long)split);
3037
3038         ext4_ext_show_leaf(inode, path);
3039
3040         depth = ext_depth(inode);
3041         ex = path[depth].p_ext;
3042         ee_block = le32_to_cpu(ex->ee_block);
3043         ee_len = ext4_ext_get_actual_len(ex);
3044         newblock = split - ee_block + ext4_ext_pblock(ex);
3045
3046         BUG_ON(split < ee_block || split >= (ee_block + ee_len));
3047         BUG_ON(!ext4_ext_is_uninitialized(ex) &&
3048                split_flag & (EXT4_EXT_MAY_ZEROOUT |
3049                              EXT4_EXT_MARK_UNINIT1 |
3050                              EXT4_EXT_MARK_UNINIT2));
3051
3052         err = ext4_ext_get_access(handle, inode, path + depth);
3053         if (err)
3054                 goto out;
3055
3056         if (split == ee_block) {
3057                 /*
3058                  * case b: block @split is the block that the extent begins with
3059                  * then we just change the state of the extent, and splitting
3060                  * is not needed.
3061                  */
3062                 if (split_flag & EXT4_EXT_MARK_UNINIT2)
3063                         ext4_ext_mark_uninitialized(ex);
3064                 else
3065                         ext4_ext_mark_initialized(ex);
3066
3067                 if (!(flags & EXT4_GET_BLOCKS_PRE_IO))
3068                         ext4_ext_try_to_merge(handle, inode, path, ex);
3069
3070                 err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3071                 goto out;
3072         }
3073
3074         /* case a */
3075         memcpy(&orig_ex, ex, sizeof(orig_ex));
3076         ex->ee_len = cpu_to_le16(split - ee_block);
3077         if (split_flag & EXT4_EXT_MARK_UNINIT1)
3078                 ext4_ext_mark_uninitialized(ex);
3079
3080         /*
3081          * path may lead to new leaf, not to original leaf any more
3082          * after ext4_ext_insert_extent() returns,
3083          */
3084         err = ext4_ext_dirty(handle, inode, path + depth);
3085         if (err)
3086                 goto fix_extent_len;
3087
3088         ex2 = &newex;
3089         ex2->ee_block = cpu_to_le32(split);
3090         ex2->ee_len   = cpu_to_le16(ee_len - (split - ee_block));
3091         ext4_ext_store_pblock(ex2, newblock);
3092         if (split_flag & EXT4_EXT_MARK_UNINIT2)
3093                 ext4_ext_mark_uninitialized(ex2);
3094
3095         err = ext4_ext_insert_extent(handle, inode, path, &newex, flags);
3096         if (err == -ENOSPC && (EXT4_EXT_MAY_ZEROOUT & split_flag)) {
3097                 if (split_flag & (EXT4_EXT_DATA_VALID1|EXT4_EXT_DATA_VALID2)) {
3098                         if (split_flag & EXT4_EXT_DATA_VALID1) {
3099                                 err = ext4_ext_zeroout(inode, ex2);
3100                                 zero_ex.ee_block = ex2->ee_block;
3101                                 zero_ex.ee_len = cpu_to_le16(
3102                                                 ext4_ext_get_actual_len(ex2));
3103                                 ext4_ext_store_pblock(&zero_ex,
3104                                                       ext4_ext_pblock(ex2));
3105                         } else {
3106                                 err = ext4_ext_zeroout(inode, ex);
3107                                 zero_ex.ee_block = ex->ee_block;
3108                                 zero_ex.ee_len = cpu_to_le16(
3109                                                 ext4_ext_get_actual_len(ex));
3110                                 ext4_ext_store_pblock(&zero_ex,
3111                                                       ext4_ext_pblock(ex));
3112                         }
3113                 } else {
3114                         err = ext4_ext_zeroout(inode, &orig_ex);
3115                         zero_ex.ee_block = orig_ex.ee_block;
3116                         zero_ex.ee_len = cpu_to_le16(
3117                                                 ext4_ext_get_actual_len(&orig_ex));
3118                         ext4_ext_store_pblock(&zero_ex,
3119                                               ext4_ext_pblock(&orig_ex));
3120                 }
3121
3122                 if (err)
3123                         goto fix_extent_len;
3124                 /* update the extent length and mark as initialized */
3125                 ex->ee_len = cpu_to_le16(ee_len);
3126                 ext4_ext_try_to_merge(handle, inode, path, ex);
3127                 err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3128                 if (err)
3129                         goto fix_extent_len;
3130
3131                 /* update extent status tree */
3132                 err = ext4_es_zeroout(inode, &zero_ex);
3133
3134                 goto out;
3135         } else if (err)
3136                 goto fix_extent_len;
3137
3138 out:
3139         ext4_ext_show_leaf(inode, path);
3140         return err;
3141
3142 fix_extent_len:
3143         ex->ee_len = orig_ex.ee_len;
3144         ext4_ext_dirty(handle, inode, path + depth);
3145         return err;
3146 }
3147
3148 /*
3149  * ext4_split_extents() splits an extent and mark extent which is covered
3150  * by @map as split_flags indicates
3151  *
3152  * It may result in splitting the extent into multiple extents (upto three)
3153  * There are three possibilities:
3154  *   a> There is no split required
3155  *   b> Splits in two extents: Split is happening at either end of the extent
3156  *   c> Splits in three extents: Somone is splitting in middle of the extent
3157  *
3158  */
3159 static int ext4_split_extent(handle_t *handle,
3160                               struct inode *inode,
3161                               struct ext4_ext_path *path,
3162                               struct ext4_map_blocks *map,
3163                               int split_flag,
3164                               int flags)
3165 {
3166         ext4_lblk_t ee_block;
3167         struct ext4_extent *ex;
3168         unsigned int ee_len, depth;
3169         int err = 0;
3170         int uninitialized;
3171         int split_flag1, flags1;
3172         int allocated = map->m_len;
3173
3174         depth = ext_depth(inode);
3175         ex = path[depth].p_ext;
3176         ee_block = le32_to_cpu(ex->ee_block);
3177         ee_len = ext4_ext_get_actual_len(ex);
3178         uninitialized = ext4_ext_is_uninitialized(ex);
3179
3180         if (map->m_lblk + map->m_len < ee_block + ee_len) {
3181                 split_flag1 = split_flag & EXT4_EXT_MAY_ZEROOUT;
3182                 flags1 = flags | EXT4_GET_BLOCKS_PRE_IO;
3183                 if (uninitialized)
3184                         split_flag1 |= EXT4_EXT_MARK_UNINIT1 |
3185                                        EXT4_EXT_MARK_UNINIT2;
3186                 if (split_flag & EXT4_EXT_DATA_VALID2)
3187                         split_flag1 |= EXT4_EXT_DATA_VALID1;
3188                 err = ext4_split_extent_at(handle, inode, path,
3189                                 map->m_lblk + map->m_len, split_flag1, flags1);
3190                 if (err)
3191                         goto out;
3192         } else {
3193                 allocated = ee_len - (map->m_lblk - ee_block);
3194         }
3195         /*
3196          * Update path is required because previous ext4_split_extent_at() may
3197          * result in split of original leaf or extent zeroout.
3198          */
3199         ext4_ext_drop_refs(path);
3200         path = ext4_ext_find_extent(inode, map->m_lblk, path);
3201         if (IS_ERR(path))
3202                 return PTR_ERR(path);
3203         depth = ext_depth(inode);
3204         ex = path[depth].p_ext;
3205         uninitialized = ext4_ext_is_uninitialized(ex);
3206         split_flag1 = 0;
3207
3208         if (map->m_lblk >= ee_block) {
3209                 split_flag1 = split_flag & EXT4_EXT_DATA_VALID2;
3210                 if (uninitialized) {
3211                         split_flag1 |= EXT4_EXT_MARK_UNINIT1;
3212                         split_flag1 |= split_flag & (EXT4_EXT_MAY_ZEROOUT |
3213                                                      EXT4_EXT_MARK_UNINIT2);
3214                 }
3215                 err = ext4_split_extent_at(handle, inode, path,
3216                                 map->m_lblk, split_flag1, flags);
3217                 if (err)
3218                         goto out;
3219         }
3220
3221         ext4_ext_show_leaf(inode, path);
3222 out:
3223         return err ? err : allocated;
3224 }
3225
3226 /*
3227  * This function is called by ext4_ext_map_blocks() if someone tries to write
3228  * to an uninitialized extent. It may result in splitting the uninitialized
3229  * extent into multiple extents (up to three - one initialized and two
3230  * uninitialized).
3231  * There are three possibilities:
3232  *   a> There is no split required: Entire extent should be initialized
3233  *   b> Splits in two extents: Write is happening at either end of the extent
3234  *   c> Splits in three extents: Somone is writing in middle of the extent
3235  *
3236  * Pre-conditions:
3237  *  - The extent pointed to by 'path' is uninitialized.
3238  *  - The extent pointed to by 'path' contains a superset
3239  *    of the logical span [map->m_lblk, map->m_lblk + map->m_len).
3240  *
3241  * Post-conditions on success:
3242  *  - the returned value is the number of blocks beyond map->l_lblk
3243  *    that are allocated and initialized.
3244  *    It is guaranteed to be >= map->m_len.
3245  */
3246 static int ext4_ext_convert_to_initialized(handle_t *handle,
3247                                            struct inode *inode,
3248                                            struct ext4_map_blocks *map,
3249                                            struct ext4_ext_path *path,
3250                                            int flags)
3251 {
3252         struct ext4_sb_info *sbi;
3253         struct ext4_extent_header *eh;
3254         struct ext4_map_blocks split_map;
3255         struct ext4_extent zero_ex;
3256         struct ext4_extent *ex, *abut_ex;
3257         ext4_lblk_t ee_block, eof_block;
3258         unsigned int ee_len, depth, map_len = map->m_len;
3259         int allocated = 0, max_zeroout = 0;
3260         int err = 0;
3261         int split_flag = 0;
3262
3263         ext_debug("ext4_ext_convert_to_initialized: inode %lu, logical"
3264                 "block %llu, max_blocks %u\n", inode->i_ino,
3265                 (unsigned long long)map->m_lblk, map_len);
3266
3267         sbi = EXT4_SB(inode->i_sb);
3268         eof_block = (inode->i_size + inode->i_sb->s_blocksize - 1) >>
3269                 inode->i_sb->s_blocksize_bits;
3270         if (eof_block < map->m_lblk + map_len)
3271                 eof_block = map->m_lblk + map_len;
3272
3273         depth = ext_depth(inode);
3274         eh = path[depth].p_hdr;
3275         ex = path[depth].p_ext;
3276         ee_block = le32_to_cpu(ex->ee_block);
3277         ee_len = ext4_ext_get_actual_len(ex);
3278         zero_ex.ee_len = 0;
3279
3280         trace_ext4_ext_convert_to_initialized_enter(inode, map, ex);
3281
3282         /* Pre-conditions */
3283         BUG_ON(!ext4_ext_is_uninitialized(ex));
3284         BUG_ON(!in_range(map->m_lblk, ee_block, ee_len));
3285
3286         /*
3287          * Attempt to transfer newly initialized blocks from the currently
3288          * uninitialized extent to its neighbor. This is much cheaper
3289          * than an insertion followed by a merge as those involve costly
3290          * memmove() calls. Transferring to the left is the common case in
3291          * steady state for workloads doing fallocate(FALLOC_FL_KEEP_SIZE)
3292          * followed by append writes.
3293          *
3294          * Limitations of the current logic:
3295          *  - L1: we do not deal with writes covering the whole extent.
3296          *    This would require removing the extent if the transfer
3297          *    is possible.
3298          *  - L2: we only attempt to merge with an extent stored in the
3299          *    same extent tree node.
3300          */
3301         if ((map->m_lblk == ee_block) &&
3302                 /* See if we can merge left */
3303                 (map_len < ee_len) &&           /*L1*/
3304                 (ex > EXT_FIRST_EXTENT(eh))) {  /*L2*/
3305                 ext4_lblk_t prev_lblk;
3306                 ext4_fsblk_t prev_pblk, ee_pblk;
3307                 unsigned int prev_len;
3308
3309                 abut_ex = ex - 1;
3310                 prev_lblk = le32_to_cpu(abut_ex->ee_block);
3311                 prev_len = ext4_ext_get_actual_len(abut_ex);
3312                 prev_pblk = ext4_ext_pblock(abut_ex);
3313                 ee_pblk = ext4_ext_pblock(ex);
3314
3315                 /*
3316                  * A transfer of blocks from 'ex' to 'abut_ex' is allowed
3317                  * upon those conditions:
3318                  * - C1: abut_ex is initialized,
3319                  * - C2: abut_ex is logically abutting ex,
3320                  * - C3: abut_ex is physically abutting ex,
3321                  * - C4: abut_ex can receive the additional blocks without
3322                  *   overflowing the (initialized) length limit.
3323                  */
3324                 if ((!ext4_ext_is_uninitialized(abut_ex)) &&            /*C1*/
3325                         ((prev_lblk + prev_len) == ee_block) &&         /*C2*/
3326                         ((prev_pblk + prev_len) == ee_pblk) &&          /*C3*/
3327                         (prev_len < (EXT_INIT_MAX_LEN - map_len))) {    /*C4*/
3328                         err = ext4_ext_get_access(handle, inode, path + depth);
3329                         if (err)
3330                                 goto out;
3331
3332                         trace_ext4_ext_convert_to_initialized_fastpath(inode,
3333                                 map, ex, abut_ex);
3334
3335                         /* Shift the start of ex by 'map_len' blocks */
3336                         ex->ee_block = cpu_to_le32(ee_block + map_len);
3337                         ext4_ext_store_pblock(ex, ee_pblk + map_len);
3338                         ex->ee_len = cpu_to_le16(ee_len - map_len);
3339                         ext4_ext_mark_uninitialized(ex); /* Restore the flag */
3340
3341                         /* Extend abut_ex by 'map_len' blocks */
3342                         abut_ex->ee_len = cpu_to_le16(prev_len + map_len);
3343
3344                         /* Result: number of initialized blocks past m_lblk */
3345                         allocated = map_len;
3346                 }
3347         } else if (((map->m_lblk + map_len) == (ee_block + ee_len)) &&
3348                    (map_len < ee_len) &&        /*L1*/
3349                    ex < EXT_LAST_EXTENT(eh)) {  /*L2*/
3350                 /* See if we can merge right */
3351                 ext4_lblk_t next_lblk;
3352                 ext4_fsblk_t next_pblk, ee_pblk;
3353                 unsigned int next_len;
3354
3355                 abut_ex = ex + 1;
3356                 next_lblk = le32_to_cpu(abut_ex->ee_block);
3357                 next_len = ext4_ext_get_actual_len(abut_ex);
3358                 next_pblk = ext4_ext_pblock(abut_ex);
3359                 ee_pblk = ext4_ext_pblock(ex);
3360
3361                 /*
3362                  * A transfer of blocks from 'ex' to 'abut_ex' is allowed
3363                  * upon those conditions:
3364                  * - C1: abut_ex is initialized,
3365                  * - C2: abut_ex is logically abutting ex,
3366                  * - C3: abut_ex is physically abutting ex,
3367                  * - C4: abut_ex can receive the additional blocks without
3368                  *   overflowing the (initialized) length limit.
3369                  */
3370                 if ((!ext4_ext_is_uninitialized(abut_ex)) &&            /*C1*/
3371                     ((map->m_lblk + map_len) == next_lblk) &&           /*C2*/
3372                     ((ee_pblk + ee_len) == next_pblk) &&                /*C3*/
3373                     (next_len < (EXT_INIT_MAX_LEN - map_len))) {        /*C4*/
3374                         err = ext4_ext_get_access(handle, inode, path + depth);
3375                         if (err)
3376                                 goto out;
3377
3378                         trace_ext4_ext_convert_to_initialized_fastpath(inode,
3379                                 map, ex, abut_ex);
3380
3381                         /* Shift the start of abut_ex by 'map_len' blocks */
3382                         abut_ex->ee_block = cpu_to_le32(next_lblk - map_len);
3383                         ext4_ext_store_pblock(abut_ex, next_pblk - map_len);
3384                         ex->ee_len = cpu_to_le16(ee_len - map_len);
3385                         ext4_ext_mark_uninitialized(ex); /* Restore the flag */
3386
3387                         /* Extend abut_ex by 'map_len' blocks */
3388                         abut_ex->ee_len = cpu_to_le16(next_len + map_len);
3389
3390                         /* Result: number of initialized blocks past m_lblk */
3391                         allocated = map_len;
3392                 }
3393         }
3394         if (allocated) {
3395                 /* Mark the block containing both extents as dirty */
3396                 ext4_ext_dirty(handle, inode, path + depth);
3397
3398                 /* Update path to point to the right extent */
3399                 path[depth].p_ext = abut_ex;
3400                 goto out;
3401         } else
3402                 allocated = ee_len - (map->m_lblk - ee_block);
3403
3404         WARN_ON(map->m_lblk < ee_block);
3405         /*
3406          * It is safe to convert extent to initialized via explicit
3407          * zeroout only if extent is fully insde i_size or new_size.
3408          */
3409         split_flag |= ee_block + ee_len <= eof_block ? EXT4_EXT_MAY_ZEROOUT : 0;
3410
3411         if (EXT4_EXT_MAY_ZEROOUT & split_flag)
3412                 max_zeroout = sbi->s_extent_max_zeroout_kb >>
3413                         (inode->i_sb->s_blocksize_bits - 10);
3414
3415         /* If extent is less than s_max_zeroout_kb, zeroout directly */
3416         if (max_zeroout && (ee_len <= max_zeroout)) {
3417                 err = ext4_ext_zeroout(inode, ex);
3418                 if (err)
3419                         goto out;
3420                 zero_ex.ee_block = ex->ee_block;
3421                 zero_ex.ee_len = cpu_to_le16(ext4_ext_get_actual_len(ex));
3422                 ext4_ext_store_pblock(&zero_ex, ext4_ext_pblock(ex));
3423
3424                 err = ext4_ext_get_access(handle, inode, path + depth);
3425                 if (err)
3426                         goto out;
3427                 ext4_ext_mark_initialized(ex);
3428                 ext4_ext_try_to_merge(handle, inode, path, ex);
3429                 err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3430                 goto out;
3431         }
3432
3433         /*
3434          * four cases:
3435          * 1. split the extent into three extents.
3436          * 2. split the extent into two extents, zeroout the first half.
3437          * 3. split the extent into two extents, zeroout the second half.
3438          * 4. split the extent into two extents with out zeroout.
3439          */
3440         split_map.m_lblk = map->m_lblk;
3441         split_map.m_len = map->m_len;
3442
3443         if (max_zeroout && (allocated > map->m_len)) {
3444                 if (allocated <= max_zeroout) {
3445                         /* case 3 */
3446                         zero_ex.ee_block =
3447                                          cpu_to_le32(map->m_lblk);
3448                         zero_ex.ee_len = cpu_to_le16(allocated);
3449                         ext4_ext_store_pblock(&zero_ex,
3450                                 ext4_ext_pblock(ex) + map->m_lblk - ee_block);
3451                         err = ext4_ext_zeroout(inode, &zero_ex);
3452                         if (err)
3453                                 goto out;
3454                         split_map.m_lblk = map->m_lblk;
3455                         split_map.m_len = allocated;
3456                 } else if (map->m_lblk - ee_block + map->m_len < max_zeroout) {
3457                         /* case 2 */
3458                         if (map->m_lblk != ee_block) {
3459                                 zero_ex.ee_block = ex->ee_block;
3460                                 zero_ex.ee_len = cpu_to_le16(map->m_lblk -
3461                                                         ee_block);
3462                                 ext4_ext_store_pblock(&zero_ex,
3463                                                       ext4_ext_pblock(ex));
3464                                 err = ext4_ext_zeroout(inode, &zero_ex);
3465                                 if (err)
3466                                         goto out;
3467                         }
3468
3469                         split_map.m_lblk = ee_block;
3470                         split_map.m_len = map->m_lblk - ee_block + map->m_len;
3471                         allocated = map->m_len;
3472                 }
3473         }
3474
3475         allocated = ext4_split_extent(handle, inode, path,
3476                                       &split_map, split_flag, flags);
3477         if (allocated < 0)
3478                 err = allocated;
3479
3480 out:
3481         /* If we have gotten a failure, don't zero out status tree */
3482         if (!err)
3483                 err = ext4_es_zeroout(inode, &zero_ex);
3484         return err ? err : allocated;
3485 }
3486
3487 /*
3488  * This function is called by ext4_ext_map_blocks() from
3489  * ext4_get_blocks_dio_write() when DIO to write
3490  * to an uninitialized extent.
3491  *
3492  * Writing to an uninitialized extent may result in splitting the uninitialized
3493  * extent into multiple initialized/uninitialized extents (up to three)
3494  * There are three possibilities:
3495  *   a> There is no split required: Entire extent should be uninitialized
3496  *   b> Splits in two extents: Write is happening at either end of the extent
3497  *   c> Splits in three extents: Somone is writing in middle of the extent
3498  *
3499  * One of more index blocks maybe needed if the extent tree grow after
3500  * the uninitialized extent split. To prevent ENOSPC occur at the IO
3501  * complete, we need to split the uninitialized extent before DIO submit
3502  * the IO. The uninitialized extent called at this time will be split
3503  * into three uninitialized extent(at most). After IO complete, the part
3504  * being filled will be convert to initialized by the end_io callback function
3505  * via ext4_convert_unwritten_extents().
3506  *
3507  * Returns the size of uninitialized extent to be written on success.
3508  */
3509 static int ext4_split_unwritten_extents(handle_t *handle,
3510                                         struct inode *inode,
3511                                         struct ext4_map_blocks *map,
3512                                         struct ext4_ext_path *path,
3513                                         int flags)
3514 {
3515         ext4_lblk_t eof_block;
3516         ext4_lblk_t ee_block;
3517         struct ext4_extent *ex;
3518         unsigned int ee_len;
3519         int split_flag = 0, depth;
3520
3521         ext_debug("ext4_split_unwritten_extents: inode %lu, logical"
3522                 "block %llu, max_blocks %u\n", inode->i_ino,
3523                 (unsigned long long)map->m_lblk, map->m_len);
3524
3525         eof_block = (inode->i_size + inode->i_sb->s_blocksize - 1) >>
3526                 inode->i_sb->s_blocksize_bits;
3527         if (eof_block < map->m_lblk + map->m_len)
3528                 eof_block = map->m_lblk + map->m_len;
3529         /*
3530          * It is safe to convert extent to initialized via explicit
3531          * zeroout only if extent is fully insde i_size or new_size.
3532          */
3533         depth = ext_depth(inode);
3534         ex = path[depth].p_ext;
3535         ee_block = le32_to_cpu(ex->ee_block);
3536         ee_len = ext4_ext_get_actual_len(ex);
3537
3538         split_flag |= ee_block + ee_len <= eof_block ? EXT4_EXT_MAY_ZEROOUT : 0;
3539         split_flag |= EXT4_EXT_MARK_UNINIT2;
3540         if (flags & EXT4_GET_BLOCKS_CONVERT)
3541                 split_flag |= EXT4_EXT_DATA_VALID2;
3542         flags |= EXT4_GET_BLOCKS_PRE_IO;
3543         return ext4_split_extent(handle, inode, path, map, split_flag, flags);
3544 }
3545
3546 static int ext4_convert_unwritten_extents_endio(handle_t *handle,
3547                                                 struct inode *inode,
3548                                                 struct ext4_map_blocks *map,
3549                                                 struct ext4_ext_path *path)
3550 {
3551         struct ext4_extent *ex;
3552         ext4_lblk_t ee_block;
3553         unsigned int ee_len;
3554         int depth;
3555         int err = 0;
3556
3557         depth = ext_depth(inode);
3558         ex = path[depth].p_ext;
3559         ee_block = le32_to_cpu(ex->ee_block);
3560         ee_len = ext4_ext_get_actual_len(ex);
3561
3562         ext_debug("ext4_convert_unwritten_extents_endio: inode %lu, logical"
3563                 "block %llu, max_blocks %u\n", inode->i_ino,
3564                   (unsigned long long)ee_block, ee_len);
3565
3566         /* If extent is larger than requested it is a clear sign that we still
3567          * have some extent state machine issues left. So extent_split is still
3568          * required.
3569          * TODO: Once all related issues will be fixed this situation should be
3570          * illegal.
3571          */
3572         if (ee_block != map->m_lblk || ee_len > map->m_len) {
3573 #ifdef EXT4_DEBUG
3574                 ext4_warning("Inode (%ld) finished: extent logical block %llu,"
3575                              " len %u; IO logical block %llu, len %u\n",
3576                              inode->i_ino, (unsigned long long)ee_block, ee_len,
3577                              (unsigned long long)map->m_lblk, map->m_len);
3578 #endif
3579                 err = ext4_split_unwritten_extents(handle, inode, map, path,
3580                                                    EXT4_GET_BLOCKS_CONVERT);
3581                 if (err < 0)
3582                         goto out;
3583                 ext4_ext_drop_refs(path);
3584                 path = ext4_ext_find_extent(inode, map->m_lblk, path);
3585                 if (IS_ERR(path)) {
3586                         err = PTR_ERR(path);
3587                         goto out;
3588                 }
3589                 depth = ext_depth(inode);
3590                 ex = path[depth].p_ext;
3591         }
3592
3593         err = ext4_ext_get_access(handle, inode, path + depth);
3594         if (err)
3595                 goto out;
3596         /* first mark the extent as initialized */
3597         ext4_ext_mark_initialized(ex);
3598
3599         /* note: ext4_ext_correct_indexes() isn't needed here because
3600          * borders are not changed
3601          */
3602         ext4_ext_try_to_merge(handle, inode, path, ex);
3603
3604         /* Mark modified extent as dirty */
3605         err = ext4_ext_dirty(handle, inode, path + path->p_depth);
3606 out:
3607         ext4_ext_show_leaf(inode, path);
3608         return err;
3609 }
3610
3611 static void unmap_underlying_metadata_blocks(struct block_device *bdev,
3612                         sector_t block, int count)
3613 {
3614         int i;
3615         for (i = 0; i < count; i++)
3616                 unmap_underlying_metadata(bdev, block + i);
3617 }
3618
3619 /*
3620  * Handle EOFBLOCKS_FL flag, clearing it if necessary
3621  */
3622 static int check_eofblocks_fl(handle_t *handle, struct inode *inode,
3623                               ext4_lblk_t lblk,
3624                               struct ext4_ext_path *path,
3625                               unsigned int len)
3626 {
3627         int i, depth;
3628         struct ext4_extent_header *eh;
3629         struct ext4_extent *last_ex;
3630
3631         if (!ext4_test_inode_flag(inode, EXT4_INODE_EOFBLOCKS))
3632                 return 0;
3633
3634         depth = ext_depth(inode);
3635         eh = path[depth].p_hdr;
3636
3637         /*
3638          * We're going to remove EOFBLOCKS_FL entirely in future so we
3639          * do not care for this case anymore. Simply remove the flag
3640          * if there are no extents.
3641          */
3642         if (unlikely(!eh->eh_entries))
3643                 goto out;
3644         last_ex = EXT_LAST_EXTENT(eh);
3645         /*
3646          * We should clear the EOFBLOCKS_FL flag if we are writing the
3647          * last block in the last extent in the file.  We test this by
3648          * first checking to see if the caller to
3649          * ext4_ext_get_blocks() was interested in the last block (or
3650          * a block beyond the last block) in the current extent.  If
3651          * this turns out to be false, we can bail out from this
3652          * function immediately.
3653          */
3654         if (lblk + len < le32_to_cpu(last_ex->ee_block) +
3655             ext4_ext_get_actual_len(last_ex))
3656                 return 0;
3657         /*
3658          * If the caller does appear to be planning to write at or
3659          * beyond the end of the current extent, we then test to see
3660          * if the current extent is the last extent in the file, by
3661          * checking to make sure it was reached via the rightmost node
3662          * at each level of the tree.
3663          */
3664         for (i = depth-1; i >= 0; i--)
3665                 if (path[i].p_idx != EXT_LAST_INDEX(path[i].p_hdr))
3666                         return 0;
3667 out:
3668         ext4_clear_inode_flag(inode, EXT4_INODE_EOFBLOCKS);
3669         return ext4_mark_inode_dirty(handle, inode);
3670 }
3671
3672 /**
3673  * ext4_find_delalloc_range: find delayed allocated block in the given range.
3674  *
3675  * Return 1 if there is a delalloc block in the range, otherwise 0.
3676  */
3677 int ext4_find_delalloc_range(struct inode *inode,
3678                              ext4_lblk_t lblk_start,
3679                              ext4_lblk_t lblk_end)
3680 {
3681         struct extent_status es;
3682
3683         ext4_es_find_delayed_extent_range(inode, lblk_start, lblk_end, &es);
3684         if (es.es_len == 0)
3685                 return 0; /* there is no delay extent in this tree */
3686         else if (es.es_lblk <= lblk_start &&
3687                  lblk_start < es.es_lblk + es.es_len)
3688                 return 1;
3689         else if (lblk_start <= es.es_lblk && es.es_lblk <= lblk_end)
3690                 return 1;
3691         else
3692                 return 0;
3693 }
3694
3695 int ext4_find_delalloc_cluster(struct inode *inode, ext4_lblk_t lblk)
3696 {
3697         struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
3698         ext4_lblk_t lblk_start, lblk_end;
3699         lblk_start = EXT4_LBLK_CMASK(sbi, lblk);
3700         lblk_end = lblk_start + sbi->s_cluster_ratio - 1;
3701
3702         return ext4_find_delalloc_range(inode, lblk_start, lblk_end);
3703 }
3704
3705 /**
3706  * Determines how many complete clusters (out of those specified by the 'map')
3707  * are under delalloc and were reserved quota for.
3708  * This function is called when we are writing out the blocks that were
3709  * originally written with their allocation delayed, but then the space was
3710  * allocated using fallocate() before the delayed allocation could be resolved.
3711  * The cases to look for are:
3712  * ('=' indicated delayed allocated blocks
3713  *  '-' indicates non-delayed allocated blocks)
3714  * (a) partial clusters towards beginning and/or end outside of allocated range
3715  *     are not delalloc'ed.
3716  *      Ex:
3717  *      |----c---=|====c====|====c====|===-c----|
3718  *               |++++++ allocated ++++++|
3719  *      ==> 4 complete clusters in above example
3720  *
3721  * (b) partial cluster (outside of allocated range) towards either end is
3722  *     marked for delayed allocation. In this case, we will exclude that
3723  *     cluster.
3724  *      Ex:
3725  *      |----====c========|========c========|
3726  *           |++++++ allocated ++++++|
3727  *      ==> 1 complete clusters in above example
3728  *
3729  *      Ex:
3730  *      |================c================|
3731  *            |++++++ allocated ++++++|
3732  *      ==> 0 complete clusters in above example
3733  *
3734  * The ext4_da_update_reserve_space will be called only if we
3735  * determine here that there were some "entire" clusters that span
3736  * this 'allocated' range.
3737  * In the non-bigalloc case, this function will just end up returning num_blks
3738  * without ever calling ext4_find_delalloc_range.
3739  */
3740 static unsigned int
3741 get_reserved_cluster_alloc(struct inode *inode, ext4_lblk_t lblk_start,
3742                            unsigned int num_blks)
3743 {
3744         struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
3745         ext4_lblk_t alloc_cluster_start, alloc_cluster_end;
3746         ext4_lblk_t lblk_from, lblk_to, c_offset;
3747         unsigned int allocated_clusters = 0;
3748
3749         alloc_cluster_start = EXT4_B2C(sbi, lblk_start);
3750         alloc_cluster_end = EXT4_B2C(sbi, lblk_start + num_blks - 1);
3751
3752         /* max possible clusters for this allocation */
3753         allocated_clusters = alloc_cluster_end - alloc_cluster_start + 1;
3754
3755         trace_ext4_get_reserved_cluster_alloc(inode, lblk_start, num_blks);
3756
3757         /* Check towards left side */
3758         c_offset = EXT4_LBLK_COFF(sbi, lblk_start);
3759         if (c_offset) {
3760                 lblk_from = EXT4_LBLK_CMASK(sbi, lblk_start);
3761                 lblk_to = lblk_from + c_offset - 1;
3762
3763                 if (ext4_find_delalloc_range(inode, lblk_from, lblk_to))
3764                         allocated_clusters--;
3765         }
3766
3767         /* Now check towards right. */
3768         c_offset = EXT4_LBLK_COFF(sbi, lblk_start + num_blks);
3769         if (allocated_clusters && c_offset) {
3770                 lblk_from = lblk_start + num_blks;
3771                 lblk_to = lblk_from + (sbi->s_cluster_ratio - c_offset) - 1;
3772
3773                 if (ext4_find_delalloc_range(inode, lblk_from, lblk_to))
3774                         allocated_clusters--;
3775         }
3776
3777         return allocated_clusters;
3778 }
3779
3780 static int
3781 ext4_ext_handle_uninitialized_extents(handle_t *handle, struct inode *inode,
3782                         struct ext4_map_blocks *map,
3783                         struct ext4_ext_path *path, int flags,
3784                         unsigned int allocated, ext4_fsblk_t newblock)
3785 {
3786         int ret = 0;
3787         int err = 0;
3788         ext4_io_end_t *io = ext4_inode_aio(inode);
3789
3790         ext_debug("ext4_ext_handle_uninitialized_extents: inode %lu, logical "
3791                   "block %llu, max_blocks %u, flags %x, allocated %u\n",
3792                   inode->i_ino, (unsigned long long)map->m_lblk, map->m_len,
3793                   flags, allocated);
3794         ext4_ext_show_leaf(inode, path);
3795
3796         /*
3797          * When writing into uninitialized space, we should not fail to
3798          * allocate metadata blocks for the new extent block if needed.
3799          */
3800         flags |= EXT4_GET_BLOCKS_METADATA_NOFAIL;
3801
3802         trace_ext4_ext_handle_uninitialized_extents(inode, map, flags,
3803                                                     allocated, newblock);
3804
3805         /* get_block() before submit the IO, split the extent */
3806         if ((flags & EXT4_GET_BLOCKS_PRE_IO)) {
3807                 ret = ext4_split_unwritten_extents(handle, inode, map,
3808                                                    path, flags);
3809                 if (ret <= 0)
3810                         goto out;
3811                 /*
3812                  * Flag the inode(non aio case) or end_io struct (aio case)
3813                  * that this IO needs to conversion to written when IO is
3814                  * completed
3815                  */
3816                 if (io)
3817                         ext4_set_io_unwritten_flag(inode, io);
3818                 else
3819                         ext4_set_inode_state(inode, EXT4_STATE_DIO_UNWRITTEN);
3820                 map->m_flags |= EXT4_MAP_UNWRITTEN;
3821                 if (ext4_should_dioread_nolock(inode))
3822                         map->m_flags |= EXT4_MAP_UNINIT;
3823                 goto out;
3824         }
3825         /* IO end_io complete, convert the filled extent to written */
3826         if ((flags & EXT4_GET_BLOCKS_CONVERT)) {
3827                 ret = ext4_convert_unwritten_extents_endio(handle, inode, map,
3828                                                         path);
3829                 if (ret >= 0) {
3830                         ext4_update_inode_fsync_trans(handle, inode, 1);
3831                         err = check_eofblocks_fl(handle, inode, map->m_lblk,
3832                                                  path, map->m_len);
3833                 } else
3834                         err = ret;
3835                 map->m_flags |= EXT4_MAP_MAPPED;
3836                 if (allocated > map->m_len)
3837                         allocated = map->m_len;
3838                 map->m_len = allocated;
3839                 goto out2;
3840         }
3841         /* buffered IO case */
3842         /*
3843          * repeat fallocate creation request
3844          * we already have an unwritten extent
3845          */
3846         if (flags & EXT4_GET_BLOCKS_UNINIT_EXT) {
3847                 map->m_flags |= EXT4_MAP_UNWRITTEN;
3848                 goto map_out;
3849         }
3850
3851         /* buffered READ or buffered write_begin() lookup */
3852         if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
3853                 /*
3854                  * We have blocks reserved already.  We
3855                  * return allocated blocks so that delalloc
3856                  * won't do block reservation for us.  But
3857                  * the buffer head will be unmapped so that
3858                  * a read from the block returns 0s.
3859                  */
3860                 map->m_flags |= EXT4_MAP_UNWRITTEN;
3861                 goto out1;
3862         }
3863
3864         /* buffered write, writepage time, convert*/
3865         ret = ext4_ext_convert_to_initialized(handle, inode, map, path, flags);
3866         if (ret >= 0)
3867                 ext4_update_inode_fsync_trans(handle, inode, 1);
3868 out:
3869         if (ret <= 0) {
3870                 err = ret;
3871                 goto out2;
3872         } else
3873                 allocated = ret;
3874         map->m_flags |= EXT4_MAP_NEW;
3875         /*
3876          * if we allocated more blocks than requested
3877          * we need to make sure we unmap the extra block
3878          * allocated. The actual needed block will get
3879          * unmapped later when we find the buffer_head marked
3880          * new.
3881          */
3882         if (allocated > map->m_len) {
3883                 unmap_underlying_metadata_blocks(inode->i_sb->s_bdev,
3884                                         newblock + map->m_len,
3885                                         allocated - map->m_len);
3886                 allocated = map->m_len;
3887         }
3888         map->m_len = allocated;
3889
3890         /*
3891          * If we have done fallocate with the offset that is already
3892          * delayed allocated, we would have block reservation
3893          * and quota reservation done in the delayed write path.
3894          * But fallocate would have already updated quota and block
3895          * count for this offset. So cancel these reservation
3896          */
3897         if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE) {
3898                 unsigned int reserved_clusters;
3899                 reserved_clusters = get_reserved_cluster_alloc(inode,
3900                                 map->m_lblk, map->m_len);
3901                 if (reserved_clusters)
3902                         ext4_da_update_reserve_space(inode,
3903                                                      reserved_clusters,
3904                                                      0);
3905         }
3906
3907 map_out:
3908         map->m_flags |= EXT4_MAP_MAPPED;
3909         if ((flags & EXT4_GET_BLOCKS_KEEP_SIZE) == 0) {
3910                 err = check_eofblocks_fl(handle, inode, map->m_lblk, path,
3911                                          map->m_len);
3912                 if (err < 0)
3913                         goto out2;
3914         }
3915 out1:
3916         if (allocated > map->m_len)
3917                 allocated = map->m_len;
3918         ext4_ext_show_leaf(inode, path);
3919         map->m_pblk = newblock;
3920         map->m_len = allocated;
3921 out2:
3922         if (path) {
3923                 ext4_ext_drop_refs(path);
3924                 kfree(path);
3925         }
3926         return err ? err : allocated;
3927 }
3928
3929 /*
3930  * get_implied_cluster_alloc - check to see if the requested
3931  * allocation (in the map structure) overlaps with a cluster already
3932  * allocated in an extent.
3933  *      @sb     The filesystem superblock structure
3934  *      @map    The requested lblk->pblk mapping
3935  *      @ex     The extent structure which might contain an implied
3936  *                      cluster allocation
3937  *
3938  * This function is called by ext4_ext_map_blocks() after we failed to
3939  * find blocks that were already in the inode's extent tree.  Hence,
3940  * we know that the beginning of the requested region cannot overlap
3941  * the extent from the inode's extent tree.  There are three cases we
3942  * want to catch.  The first is this case:
3943  *
3944  *               |--- cluster # N--|
3945  *    |--- extent ---|  |---- requested region ---|
3946  *                      |==========|
3947  *
3948  * The second case that we need to test for is this one:
3949  *
3950  *   |--------- cluster # N ----------------|
3951  *         |--- requested region --|   |------- extent ----|
3952  *         |=======================|
3953  *
3954  * The third case is when the requested region lies between two extents
3955  * within the same cluster:
3956  *          |------------- cluster # N-------------|
3957  * |----- ex -----|                  |---- ex_right ----|
3958  *                  |------ requested region ------|
3959  *                  |================|
3960  *
3961  * In each of the above cases, we need to set the map->m_pblk and
3962  * map->m_len so it corresponds to the return the extent labelled as
3963  * "|====|" from cluster #N, since it is already in use for data in
3964  * cluster EXT4_B2C(sbi, map->m_lblk).  We will then return 1 to
3965  * signal to ext4_ext_map_blocks() that map->m_pblk should be treated
3966  * as a new "allocated" block region.  Otherwise, we will return 0 and
3967  * ext4_ext_map_blocks() will then allocate one or more new clusters
3968  * by calling ext4_mb_new_blocks().
3969  */
3970 static int get_implied_cluster_alloc(struct super_block *sb,
3971                                      struct ext4_map_blocks *map,
3972                                      struct ext4_extent *ex,
3973                                      struct ext4_ext_path *path)
3974 {
3975         struct ext4_sb_info *sbi = EXT4_SB(sb);
3976         ext4_lblk_t c_offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
3977         ext4_lblk_t ex_cluster_start, ex_cluster_end;
3978         ext4_lblk_t rr_cluster_start;
3979         ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block);
3980         ext4_fsblk_t ee_start = ext4_ext_pblock(ex);
3981         unsigned short ee_len = ext4_ext_get_actual_len(ex);
3982
3983         /* The extent passed in that we are trying to match */
3984         ex_cluster_start = EXT4_B2C(sbi, ee_block);
3985         ex_cluster_end = EXT4_B2C(sbi, ee_block + ee_len - 1);
3986
3987         /* The requested region passed into ext4_map_blocks() */
3988         rr_cluster_start = EXT4_B2C(sbi, map->m_lblk);
3989
3990         if ((rr_cluster_start == ex_cluster_end) ||
3991             (rr_cluster_start == ex_cluster_start)) {
3992                 if (rr_cluster_start == ex_cluster_end)
3993                         ee_start += ee_len - 1;
3994                 map->m_pblk = EXT4_PBLK_CMASK(sbi, ee_start) + c_offset;
3995                 map->m_len = min(map->m_len,
3996                                  (unsigned) sbi->s_cluster_ratio - c_offset);
3997                 /*
3998                  * Check for and handle this case:
3999                  *
4000                  *   |--------- cluster # N-------------|
4001                  *                     |------- extent ----|
4002                  *         |--- requested region ---|
4003                  *         |===========|
4004                  */
4005
4006                 if (map->m_lblk < ee_block)
4007                         map->m_len = min(map->m_len, ee_block - map->m_lblk);
4008
4009                 /*
4010                  * Check for the case where there is already another allocated
4011                  * block to the right of 'ex' but before the end of the cluster.
4012                  *
4013                  *          |------------- cluster # N-------------|
4014                  * |----- ex -----|                  |---- ex_right ----|
4015                  *                  |------ requested region ------|
4016                  *                  |================|
4017                  */
4018                 if (map->m_lblk > ee_block) {
4019                         ext4_lblk_t next = ext4_ext_next_allocated_block(path);
4020                         map->m_len = min(map->m_len, next - map->m_lblk);
4021                 }
4022
4023                 trace_ext4_get_implied_cluster_alloc_exit(sb, map, 1);
4024                 return 1;
4025         }
4026
4027         trace_ext4_get_implied_cluster_alloc_exit(sb, map, 0);
4028         return 0;
4029 }
4030
4031
4032 /*
4033  * Block allocation/map/preallocation routine for extents based files
4034  *
4035  *
4036  * Need to be called with
4037  * down_read(&EXT4_I(inode)->i_data_sem) if not allocating file system block
4038  * (ie, create is zero). Otherwise down_write(&EXT4_I(inode)->i_data_sem)
4039  *
4040  * return > 0, number of of blocks already mapped/allocated
4041  *          if create == 0 and these are pre-allocated blocks
4042  *              buffer head is unmapped
4043  *          otherwise blocks are mapped
4044  *
4045  * return = 0, if plain look up failed (blocks have not been allocated)
4046  *          buffer head is unmapped
4047  *
4048  * return < 0, error case.
4049  */
4050 int ext4_ext_map_blocks(handle_t *handle, struct inode *inode,
4051                         struct ext4_map_blocks *map, int flags)
4052 {
4053         struct ext4_ext_path *path = NULL;
4054         struct ext4_extent newex, *ex, *ex2;
4055         struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
4056         ext4_fsblk_t newblock = 0;
4057         int free_on_err = 0, err = 0, depth, ret;
4058         unsigned int allocated = 0, offset = 0;
4059         unsigned int allocated_clusters = 0;
4060         struct ext4_allocation_request ar;
4061         ext4_io_end_t *io = ext4_inode_aio(inode);
4062         ext4_lblk_t cluster_offset;
4063         int set_unwritten = 0;
4064
4065         ext_debug("blocks %u/%u requested for inode %lu\n",
4066                   map->m_lblk, map->m_len, inode->i_ino);
4067         trace_ext4_ext_map_blocks_enter(inode, map->m_lblk, map->m_len, flags);
4068
4069         /* find extent for this block */
4070         path = ext4_ext_find_extent(inode, map->m_lblk, NULL);
4071         if (IS_ERR(path)) {
4072                 err = PTR_ERR(path);
4073                 path = NULL;
4074                 goto out2;
4075         }
4076
4077         depth = ext_depth(inode);
4078
4079         /*
4080          * consistent leaf must not be empty;
4081          * this situation is possible, though, _during_ tree modification;
4082          * this is why assert can't be put in ext4_ext_find_extent()
4083          */
4084         if (unlikely(path[depth].p_ext == NULL && depth != 0)) {
4085                 EXT4_ERROR_INODE(inode, "bad extent address "
4086                                  "lblock: %lu, depth: %d pblock %lld",
4087                                  (unsigned long) map->m_lblk, depth,
4088                                  path[depth].p_block);
4089                 err = -EIO;
4090                 goto out2;
4091         }
4092
4093         ex = path[depth].p_ext;
4094         if (ex) {
4095                 ext4_lblk_t ee_block = le32_to_cpu(ex->ee_block);
4096                 ext4_fsblk_t ee_start = ext4_ext_pblock(ex);
4097                 unsigned short ee_len;
4098
4099                 /*
4100                  * Uninitialized extents are treated as holes, except that
4101                  * we split out initialized portions during a write.
4102                  */
4103                 ee_len = ext4_ext_get_actual_len(ex);
4104
4105                 trace_ext4_ext_show_extent(inode, ee_block, ee_start, ee_len);
4106
4107                 /* if found extent covers block, simply return it */
4108                 if (in_range(map->m_lblk, ee_block, ee_len)) {
4109                         newblock = map->m_lblk - ee_block + ee_start;
4110                         /* number of remaining blocks in the extent */
4111                         allocated = ee_len - (map->m_lblk - ee_block);
4112                         ext_debug("%u fit into %u:%d -> %llu\n", map->m_lblk,
4113                                   ee_block, ee_len, newblock);
4114
4115                         if (!ext4_ext_is_uninitialized(ex))
4116                                 goto out;
4117
4118                         ret = ext4_ext_handle_uninitialized_extents(
4119                                 handle, inode, map, path, flags,
4120                                 allocated, newblock);
4121                         if (ret < 0)
4122                                 err = ret;
4123                         else
4124                                 allocated = ret;
4125                         goto out3;
4126                 }
4127         }
4128
4129         if ((sbi->s_cluster_ratio > 1) &&
4130             ext4_find_delalloc_cluster(inode, map->m_lblk))
4131                 map->m_flags |= EXT4_MAP_FROM_CLUSTER;
4132
4133         /*
4134          * requested block isn't allocated yet;
4135          * we couldn't try to create block if create flag is zero
4136          */
4137         if ((flags & EXT4_GET_BLOCKS_CREATE) == 0) {
4138                 /*
4139                  * put just found gap into cache to speed up
4140                  * subsequent requests
4141                  */
4142                 if ((flags & EXT4_GET_BLOCKS_NO_PUT_HOLE) == 0)
4143                         ext4_ext_put_gap_in_cache(inode, path, map->m_lblk);
4144                 goto out2;
4145         }
4146
4147         /*
4148          * Okay, we need to do block allocation.
4149          */
4150         map->m_flags &= ~EXT4_MAP_FROM_CLUSTER;
4151         newex.ee_block = cpu_to_le32(map->m_lblk);
4152         cluster_offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
4153
4154         /*
4155          * If we are doing bigalloc, check to see if the extent returned
4156          * by ext4_ext_find_extent() implies a cluster we can use.
4157          */
4158         if (cluster_offset && ex &&
4159             get_implied_cluster_alloc(inode->i_sb, map, ex, path)) {
4160                 ar.len = allocated = map->m_len;
4161                 newblock = map->m_pblk;
4162                 map->m_flags |= EXT4_MAP_FROM_CLUSTER;
4163                 goto got_allocated_blocks;
4164         }
4165
4166         /* find neighbour allocated blocks */
4167         ar.lleft = map->m_lblk;
4168         err = ext4_ext_search_left(inode, path, &ar.lleft, &ar.pleft);
4169         if (err)
4170                 goto out2;
4171         ar.lright = map->m_lblk;
4172         ex2 = NULL;
4173         err = ext4_ext_search_right(inode, path, &ar.lright, &ar.pright, &ex2);
4174         if (err)
4175                 goto out2;
4176
4177         /* Check if the extent after searching to the right implies a
4178          * cluster we can use. */
4179         if ((sbi->s_cluster_ratio > 1) && ex2 &&
4180             get_implied_cluster_alloc(inode->i_sb, map, ex2, path)) {
4181                 ar.len = allocated = map->m_len;
4182                 newblock = map->m_pblk;
4183                 map->m_flags |= EXT4_MAP_FROM_CLUSTER;
4184                 goto got_allocated_blocks;
4185         }
4186
4187         /*
4188          * See if request is beyond maximum number of blocks we can have in
4189          * a single extent. For an initialized extent this limit is
4190          * EXT_INIT_MAX_LEN and for an uninitialized extent this limit is
4191          * EXT_UNINIT_MAX_LEN.
4192          */
4193         if (map->m_len > EXT_INIT_MAX_LEN &&
4194             !(flags & EXT4_GET_BLOCKS_UNINIT_EXT))
4195                 map->m_len = EXT_INIT_MAX_LEN;
4196         else if (map->m_len > EXT_UNINIT_MAX_LEN &&
4197                  (flags & EXT4_GET_BLOCKS_UNINIT_EXT))
4198                 map->m_len = EXT_UNINIT_MAX_LEN;
4199
4200         /* Check if we can really insert (m_lblk)::(m_lblk + m_len) extent */
4201         newex.ee_len = cpu_to_le16(map->m_len);
4202         err = ext4_ext_check_overlap(sbi, inode, &newex, path);
4203         if (err)
4204                 allocated = ext4_ext_get_actual_len(&newex);
4205         else
4206                 allocated = map->m_len;
4207
4208         /* allocate new block */
4209         ar.inode = inode;
4210         ar.goal = ext4_ext_find_goal(inode, path, map->m_lblk);
4211         ar.logical = map->m_lblk;
4212         /*
4213          * We calculate the offset from the beginning of the cluster
4214          * for the logical block number, since when we allocate a
4215          * physical cluster, the physical block should start at the
4216          * same offset from the beginning of the cluster.  This is
4217          * needed so that future calls to get_implied_cluster_alloc()
4218          * work correctly.
4219          */
4220         offset = EXT4_LBLK_COFF(sbi, map->m_lblk);
4221         ar.len = EXT4_NUM_B2C(sbi, offset+allocated);
4222         ar.goal -= offset;
4223         ar.logical -= offset;
4224         if (S_ISREG(inode->i_mode))
4225                 ar.flags = EXT4_MB_HINT_DATA;
4226         else
4227                 /* disable in-core preallocation for non-regular files */
4228                 ar.flags = 0;
4229         if (flags & EXT4_GET_BLOCKS_NO_NORMALIZE)
4230                 ar.flags |= EXT4_MB_HINT_NOPREALLOC;
4231         newblock = ext4_mb_new_blocks(handle, &ar, &err);
4232         if (!newblock)
4233                 goto out2;
4234         ext_debug("allocate new block: goal %llu, found %llu/%u\n",
4235                   ar.goal, newblock, allocated);
4236         free_on_err = 1;
4237         allocated_clusters = ar.len;
4238         ar.len = EXT4_C2B(sbi, ar.len) - offset;
4239         if (ar.len > allocated)
4240                 ar.len = allocated;
4241
4242 got_allocated_blocks:
4243         /* try to insert new extent into found leaf and return */
4244         ext4_ext_store_pblock(&newex, newblock + offset);
4245         newex.ee_len = cpu_to_le16(ar.len);
4246         /* Mark uninitialized */
4247         if (flags & EXT4_GET_BLOCKS_UNINIT_EXT){
4248                 ext4_ext_mark_uninitialized(&newex);
4249                 map->m_flags |= EXT4_MAP_UNWRITTEN;
4250                 /*
4251                  * io_end structure was created for every IO write to an
4252                  * uninitialized extent. To avoid unnecessary conversion,
4253                  * here we flag the IO that really needs the conversion.
4254                  * For non asycn direct IO case, flag the inode state
4255                  * that we need to perform conversion when IO is done.
4256                  */
4257                 if ((flags & EXT4_GET_BLOCKS_PRE_IO))
4258                         set_unwritten = 1;
4259                 if (ext4_should_dioread_nolock(inode))
4260                         map->m_flags |= EXT4_MAP_UNINIT;
4261         }
4262
4263         err = 0;
4264         if ((flags & EXT4_GET_BLOCKS_KEEP_SIZE) == 0)
4265                 err = check_eofblocks_fl(handle, inode, map->m_lblk,
4266                                          path, ar.len);
4267         if (!err)
4268                 err = ext4_ext_insert_extent(handle, inode, path,
4269                                              &newex, flags);
4270
4271         if (!err && set_unwritten) {
4272                 if (io)
4273                         ext4_set_io_unwritten_flag(inode, io);
4274                 else
4275                         ext4_set_inode_state(inode,
4276                                              EXT4_STATE_DIO_UNWRITTEN);
4277         }
4278
4279         if (err && free_on_err) {
4280                 int fb_flags = flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE ?
4281                         EXT4_FREE_BLOCKS_NO_QUOT_UPDATE : 0;
4282                 /* free data blocks we just allocated */
4283                 /* not a good idea to call discard here directly,
4284                  * but otherwise we'd need to call it every free() */
4285                 ext4_discard_preallocations(inode);
4286                 ext4_free_blocks(handle, inode, NULL, ext4_ext_pblock(&newex),
4287                                  ext4_ext_get_actual_len(&newex), fb_flags);
4288                 goto out2;
4289         }
4290
4291         /* previous routine could use block we allocated */
4292         newblock = ext4_ext_pblock(&newex);
4293         allocated = ext4_ext_get_actual_len(&newex);
4294         if (allocated > map->m_len)
4295                 allocated = map->m_len;
4296         map->m_flags |= EXT4_MAP_NEW;
4297
4298         /*
4299          * Update reserved blocks/metadata blocks after successful
4300          * block allocation which had been deferred till now.
4301          */
4302         if (flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE) {
4303                 unsigned int reserved_clusters;
4304                 /*
4305                  * Check how many clusters we had reserved this allocated range
4306                  */
4307                 reserved_clusters = get_reserved_cluster_alloc(inode,
4308                                                 map->m_lblk, allocated);
4309                 if (map->m_flags & EXT4_MAP_FROM_CLUSTER) {
4310                         if (reserved_clusters) {
4311                                 /*
4312                                  * We have clusters reserved for this range.
4313                                  * But since we are not doing actual allocation
4314                                  * and are simply using blocks from previously
4315                                  * allocated cluster, we should release the
4316                                  * reservation and not claim quota.
4317                                  */
4318                                 ext4_da_update_reserve_space(inode,
4319                                                 reserved_clusters, 0);
4320                         }
4321                 } else {
4322                         BUG_ON(allocated_clusters < reserved_clusters);
4323                         if (reserved_clusters < allocated_clusters) {
4324                                 struct ext4_inode_info *ei = EXT4_I(inode);
4325                                 int reservation = allocated_clusters -
4326                                                   reserved_clusters;
4327                                 /*
4328                                  * It seems we claimed few clusters outside of
4329                                  * the range of this allocation. We should give
4330                                  * it back to the reservation pool. This can
4331                                  * happen in the following case:
4332                                  *
4333                                  * * Suppose s_cluster_ratio is 4 (i.e., each
4334                                  *   cluster has 4 blocks. Thus, the clusters
4335                                  *   are [0-3],[4-7],[8-11]...
4336                                  * * First comes delayed allocation write for
4337                                  *   logical blocks 10 & 11. Since there were no
4338                                  *   previous delayed allocated blocks in the
4339                                  *   range [8-11], we would reserve 1 cluster
4340                                  *   for this write.
4341                                  * * Next comes write for logical blocks 3 to 8.
4342                                  *   In this case, we will reserve 2 clusters
4343                                  *   (for [0-3] and [4-7]; and not for [8-11] as
4344                                  *   that range has a delayed allocated blocks.
4345                                  *   Thus total reserved clusters now becomes 3.
4346                                  * * Now, during the delayed allocation writeout
4347                                  *   time, we will first write blocks [3-8] and
4348                                  *   allocate 3 clusters for writing these
4349                                  *   blocks. Also, we would claim all these
4350                                  *   three clusters above.
4351                                  * * Now when we come here to writeout the
4352                                  *   blocks [10-11], we would expect to claim
4353                                  *   the reservation of 1 cluster we had made
4354                                  *   (and we would claim it since there are no
4355                                  *   more delayed allocated blocks in the range
4356                                  *   [8-11]. But our reserved cluster count had
4357                                  *   already gone to 0.
4358                                  *
4359                                  *   Thus, at the step 4 above when we determine
4360                                  *   that there are still some unwritten delayed
4361                                  *   allocated blocks outside of our current
4362                                  *   block range, we should increment the
4363                                  *   reserved clusters count so that when the
4364                                  *   remaining blocks finally gets written, we
4365                                  *   could claim them.
4366                                  */
4367                                 dquot_reserve_block(inode,
4368                                                 EXT4_C2B(sbi, reservation));
4369                                 spin_lock(&ei->i_block_reservation_lock);
4370                                 ei->i_reserved_data_blocks += reservation;
4371                                 spin_unlock(&ei->i_block_reservation_lock);
4372                         }
4373                         /*
4374                          * We will claim quota for all newly allocated blocks.
4375                          * We're updating the reserved space *after* the
4376                          * correction above so we do not accidentally free
4377                          * all the metadata reservation because we might
4378                          * actually need it later on.
4379                          */
4380                         ext4_da_update_reserve_space(inode, allocated_clusters,
4381                                                         1);
4382                 }
4383         }
4384
4385         /*
4386          * Cache the extent and update transaction to commit on fdatasync only
4387          * when it is _not_ an uninitialized extent.
4388          */
4389         if ((flags & EXT4_GET_BLOCKS_UNINIT_EXT) == 0)
4390                 ext4_update_inode_fsync_trans(handle, inode, 1);
4391         else
4392                 ext4_update_inode_fsync_trans(handle, inode, 0);
4393 out:
4394         if (allocated > map->m_len)
4395                 allocated = map->m_len;
4396         ext4_ext_show_leaf(inode, path);
4397         map->m_flags |= EXT4_MAP_MAPPED;
4398         map->m_pblk = newblock;
4399         map->m_len = allocated;
4400 out2:
4401         if (path) {
4402                 ext4_ext_drop_refs(path);
4403                 kfree(path);
4404         }
4405
4406 out3:
4407         trace_ext4_ext_map_blocks_exit(inode, map, err ? err : allocated);
4408
4409         return err ? err : allocated;
4410 }
4411
4412 void ext4_ext_truncate(handle_t *handle, struct inode *inode)
4413 {
4414         struct super_block *sb = inode->i_sb;
4415         ext4_lblk_t last_block;
4416         int err = 0;
4417
4418         /*
4419          * TODO: optimization is possible here.
4420          * Probably we need not scan at all,
4421          * because page truncation is enough.
4422          */
4423
4424         /* we have to know where to truncate from in crash case */
4425         EXT4_I(inode)->i_disksize = inode->i_size;
4426         ext4_mark_inode_dirty(handle, inode);
4427
4428         last_block = (inode->i_size + sb->s_blocksize - 1)
4429                         >> EXT4_BLOCK_SIZE_BITS(sb);
4430 retry:
4431         err = ext4_es_remove_extent(inode, last_block,
4432                                     EXT_MAX_BLOCKS - last_block);
4433         if (err == -ENOMEM) {
4434                 cond_resched();
4435                 congestion_wait(BLK_RW_ASYNC, HZ/50);
4436                 goto retry;
4437         }
4438         if (err) {
4439                 ext4_std_error(inode->i_sb, err);
4440                 return;
4441         }
4442         err = ext4_ext_remove_space(inode, last_block, EXT_MAX_BLOCKS - 1);
4443         ext4_std_error(inode->i_sb, err);
4444 }
4445
4446 static void ext4_falloc_update_inode(struct inode *inode,
4447                                 int mode, loff_t new_size, int update_ctime)
4448 {
4449         struct timespec now;
4450
4451         if (update_ctime) {
4452                 now = current_fs_time(inode->i_sb);
4453                 if (!timespec_equal(&inode->i_ctime, &now))
4454                         inode->i_ctime = now;
4455         }
4456         /*
4457          * Update only when preallocation was requested beyond
4458          * the file size.
4459          */
4460         if (!(mode & FALLOC_FL_KEEP_SIZE)) {
4461                 if (new_size > i_size_read(inode))
4462                         i_size_write(inode, new_size);
4463                 if (new_size > EXT4_I(inode)->i_disksize)
4464                         ext4_update_i_disksize(inode, new_size);
4465         } else {
4466                 /*
4467                  * Mark that we allocate beyond EOF so the subsequent truncate
4468                  * can proceed even if the new size is the same as i_size.
4469                  */
4470                 if (new_size > i_size_read(inode))
4471                         ext4_set_inode_flag(inode, EXT4_INODE_EOFBLOCKS);
4472         }
4473
4474 }
4475
4476 /*
4477  * preallocate space for a file. This implements ext4's fallocate file
4478  * operation, which gets called from sys_fallocate system call.
4479  * For block-mapped files, posix_fallocate should fall back to the method
4480  * of writing zeroes to the required new blocks (the same behavior which is
4481  * expected for file systems which do not support fallocate() system call).
4482  */
4483 long ext4_fallocate(struct file *file, int mode, loff_t offset, loff_t len)
4484 {
4485         struct inode *inode = file_inode(file);
4486         handle_t *handle;
4487         loff_t new_size;
4488         unsigned int max_blocks;
4489         int ret = 0;
4490         int ret2 = 0;
4491         int retries = 0;
4492         int flags;
4493         struct ext4_map_blocks map;
4494         unsigned int credits, blkbits = inode->i_blkbits;
4495
4496         /* Return error if mode is not supported */
4497         if (mode & ~(FALLOC_FL_KEEP_SIZE | FALLOC_FL_PUNCH_HOLE))
4498                 return -EOPNOTSUPP;
4499
4500         if (mode & FALLOC_FL_PUNCH_HOLE)
4501                 return ext4_punch_hole(file, offset, len);
4502
4503         ret = ext4_convert_inline_data(inode);
4504         if (ret)
4505                 return ret;
4506
4507         /*
4508          * currently supporting (pre)allocate mode for extent-based
4509          * files _only_
4510          */
4511         if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)))
4512                 return -EOPNOTSUPP;
4513
4514         trace_ext4_fallocate_enter(inode, offset, len, mode);
4515         map.m_lblk = offset >> blkbits;
4516         /*
4517          * We can't just convert len to max_blocks because
4518          * If blocksize = 4096 offset = 3072 and len = 2048
4519          */
4520         max_blocks = (EXT4_BLOCK_ALIGN(len + offset, blkbits) >> blkbits)
4521                 - map.m_lblk;
4522         /*
4523          * credits to insert 1 extent into extent tree
4524          */
4525         credits = ext4_chunk_trans_blocks(inode, max_blocks);
4526         mutex_lock(&inode->i_mutex);
4527         ret = inode_newsize_ok(inode, (len + offset));
4528         if (ret) {
4529                 mutex_unlock(&inode->i_mutex);
4530                 trace_ext4_fallocate_exit(inode, offset, max_blocks, ret);
4531                 return ret;
4532         }
4533         flags = EXT4_GET_BLOCKS_CREATE_UNINIT_EXT;
4534         if (mode & FALLOC_FL_KEEP_SIZE)
4535                 flags |= EXT4_GET_BLOCKS_KEEP_SIZE;
4536         /*
4537          * Don't normalize the request if it can fit in one extent so
4538          * that it doesn't get unnecessarily split into multiple
4539          * extents.
4540          */
4541         if (len <= EXT_UNINIT_MAX_LEN << blkbits)
4542                 flags |= EXT4_GET_BLOCKS_NO_NORMALIZE;
4543
4544 retry:
4545         while (ret >= 0 && ret < max_blocks) {
4546                 map.m_lblk = map.m_lblk + ret;
4547                 map.m_len = max_blocks = max_blocks - ret;
4548                 handle = ext4_journal_start(inode, EXT4_HT_MAP_BLOCKS,
4549                                             credits);
4550                 if (IS_ERR(handle)) {
4551                         ret = PTR_ERR(handle);
4552                         break;
4553                 }
4554                 ret = ext4_map_blocks(handle, inode, &map, flags);
4555                 if (ret <= 0) {
4556 #ifdef EXT4FS_DEBUG
4557                         ext4_warning(inode->i_sb,
4558                                      "inode #%lu: block %u: len %u: "
4559                                      "ext4_ext_map_blocks returned %d",
4560                                      inode->i_ino, map.m_lblk,
4561                                      map.m_len, ret);
4562 #endif
4563                         ext4_mark_inode_dirty(handle, inode);
4564                         ret2 = ext4_journal_stop(handle);
4565                         break;
4566                 }
4567                 if ((map.m_lblk + ret) >= (EXT4_BLOCK_ALIGN(offset + len,
4568                                                 blkbits) >> blkbits))
4569                         new_size = offset + len;
4570                 else
4571                         new_size = ((loff_t) map.m_lblk + ret) << blkbits;
4572
4573                 ext4_falloc_update_inode(inode, mode, new_size,
4574                                          (map.m_flags & EXT4_MAP_NEW));
4575                 ext4_mark_inode_dirty(handle, inode);
4576                 if ((file->f_flags & O_SYNC) && ret >= max_blocks)
4577                         ext4_handle_sync(handle);
4578                 ret2 = ext4_journal_stop(handle);
4579                 if (ret2)
4580                         break;
4581         }
4582         if (ret == -ENOSPC &&
4583                         ext4_should_retry_alloc(inode->i_sb, &retries)) {
4584                 ret = 0;
4585                 goto retry;
4586         }
4587         mutex_unlock(&inode->i_mutex);
4588         trace_ext4_fallocate_exit(inode, offset, max_blocks,
4589                                 ret > 0 ? ret2 : ret);
4590         return ret > 0 ? ret2 : ret;
4591 }
4592
4593 /*
4594  * This function convert a range of blocks to written extents
4595  * The caller of this function will pass the start offset and the size.
4596  * all unwritten extents within this range will be converted to
4597  * written extents.
4598  *
4599  * This function is called from the direct IO end io call back
4600  * function, to convert the fallocated extents after IO is completed.
4601  * Returns 0 on success.
4602  */
4603 int ext4_convert_unwritten_extents(struct inode *inode, loff_t offset,
4604                                     ssize_t len)
4605 {
4606         handle_t *handle;
4607         unsigned int max_blocks;
4608         int ret = 0;
4609         int ret2 = 0;
4610         struct ext4_map_blocks map;
4611         unsigned int credits, blkbits = inode->i_blkbits;
4612
4613         map.m_lblk = offset >> blkbits;
4614         /*
4615          * We can't just convert len to max_blocks because
4616          * If blocksize = 4096 offset = 3072 and len = 2048
4617          */
4618         max_blocks = ((EXT4_BLOCK_ALIGN(len + offset, blkbits) >> blkbits) -
4619                       map.m_lblk);
4620         /*
4621          * credits to insert 1 extent into extent tree
4622          */
4623         credits = ext4_chunk_trans_blocks(inode, max_blocks);
4624         while (ret >= 0 && ret < max_blocks) {
4625                 map.m_lblk += ret;
4626                 map.m_len = (max_blocks -= ret);
4627                 handle = ext4_journal_start(inode, EXT4_HT_MAP_BLOCKS, credits);
4628                 if (IS_ERR(handle)) {
4629                         ret = PTR_ERR(handle);
4630                         break;
4631                 }
4632                 ret = ext4_map_blocks(handle, inode, &map,
4633                                       EXT4_GET_BLOCKS_IO_CONVERT_EXT);
4634                 if (ret <= 0)
4635                         ext4_warning(inode->i_sb,
4636                                      "inode #%lu: block %u: len %u: "
4637                                      "ext4_ext_map_blocks returned %d",
4638                                      inode->i_ino, map.m_lblk,
4639                                      map.m_len, ret);
4640                 ext4_mark_inode_dirty(handle, inode);
4641                 ret2 = ext4_journal_stop(handle);
4642                 if (ret <= 0 || ret2 )
4643                         break;
4644         }
4645         return ret > 0 ? ret2 : ret;
4646 }
4647
4648 /*
4649  * If newes is not existing extent (newes->ec_pblk equals zero) find
4650  * delayed extent at start of newes and update newes accordingly and
4651  * return start of the next delayed extent.
4652  *
4653  * If newes is existing extent (newes->ec_pblk is not equal zero)
4654  * return start of next delayed extent or EXT_MAX_BLOCKS if no delayed
4655  * extent found. Leave newes unmodified.
4656  */
4657 static int ext4_find_delayed_extent(struct inode *inode,
4658                                     struct extent_status *newes)
4659 {
4660         struct extent_status es;
4661         ext4_lblk_t block, next_del;
4662
4663         if (newes->es_pblk == 0) {
4664                 ext4_es_find_delayed_extent_range(inode, newes->es_lblk,
4665                                 newes->es_lblk + newes->es_len - 1, &es);
4666
4667                 /*
4668                  * No extent in extent-tree contains block @newes->es_pblk,
4669                  * then the block may stay in 1)a hole or 2)delayed-extent.
4670                  */
4671                 if (es.es_len == 0)
4672                         /* A hole found. */
4673                         return 0;
4674
4675                 if (es.es_lblk > newes->es_lblk) {
4676                         /* A hole found. */
4677                         newes->es_len = min(es.es_lblk - newes->es_lblk,
4678                                             newes->es_len);
4679                         return 0;
4680                 }
4681
4682                 newes->es_len = es.es_lblk + es.es_len - newes->es_lblk;
4683         }
4684
4685         block = newes->es_lblk + newes->es_len;
4686         ext4_es_find_delayed_extent_range(inode, block, EXT_MAX_BLOCKS, &es);
4687         if (es.es_len == 0)
4688                 next_del = EXT_MAX_BLOCKS;
4689         else
4690                 next_del = es.es_lblk;
4691
4692         return next_del;
4693 }
4694 /* fiemap flags we can handle specified here */
4695 #define EXT4_FIEMAP_FLAGS       (FIEMAP_FLAG_SYNC|FIEMAP_FLAG_XATTR)
4696
4697 static int ext4_xattr_fiemap(struct inode *inode,
4698                                 struct fiemap_extent_info *fieinfo)
4699 {
4700         __u64 physical = 0;
4701         __u64 length;
4702         __u32 flags = FIEMAP_EXTENT_LAST;
4703         int blockbits = inode->i_sb->s_blocksize_bits;
4704         int error = 0;
4705
4706         /* in-inode? */
4707         if (ext4_test_inode_state(inode, EXT4_STATE_XATTR)) {
4708                 struct ext4_iloc iloc;
4709                 int offset;     /* offset of xattr in inode */
4710
4711                 error = ext4_get_inode_loc(inode, &iloc);
4712                 if (error)
4713                         return error;
4714                 physical = (__u64)iloc.bh->b_blocknr << blockbits;
4715                 offset = EXT4_GOOD_OLD_INODE_SIZE +
4716                                 EXT4_I(inode)->i_extra_isize;
4717                 physical += offset;
4718                 length = EXT4_SB(inode->i_sb)->s_inode_size - offset;
4719                 flags |= FIEMAP_EXTENT_DATA_INLINE;
4720                 brelse(iloc.bh);
4721         } else { /* external block */
4722                 physical = (__u64)EXT4_I(inode)->i_file_acl << blockbits;
4723                 length = inode->i_sb->s_blocksize;
4724         }
4725
4726         if (physical)
4727                 error = fiemap_fill_next_extent(fieinfo, 0, physical,
4728                                                 length, flags);
4729         return (error < 0 ? error : 0);
4730 }
4731
4732 int ext4_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo,
4733                 __u64 start, __u64 len)
4734 {
4735         ext4_lblk_t start_blk;
4736         int error = 0;
4737
4738         if (ext4_has_inline_data(inode)) {
4739                 int has_inline = 1;
4740
4741                 error = ext4_inline_data_fiemap(inode, fieinfo, &has_inline);
4742
4743                 if (has_inline)
4744                         return error;
4745         }
4746
4747         /* fallback to generic here if not in extents fmt */
4748         if (!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)))
4749                 return generic_block_fiemap(inode, fieinfo, start, len,
4750                         ext4_get_block);
4751
4752         if (fiemap_check_flags(fieinfo, EXT4_FIEMAP_FLAGS))
4753                 return -EBADR;
4754
4755         if (fieinfo->fi_flags & FIEMAP_FLAG_XATTR) {
4756                 error = ext4_xattr_fiemap(inode, fieinfo);
4757         } else {
4758                 ext4_lblk_t len_blks;
4759                 __u64 last_blk;
4760
4761                 start_blk = start >> inode->i_sb->s_blocksize_bits;
4762                 last_blk = (start + len - 1) >> inode->i_sb->s_blocksize_bits;
4763                 if (last_blk >= EXT_MAX_BLOCKS)
4764                         last_blk = EXT_MAX_BLOCKS-1;
4765                 len_blks = ((ext4_lblk_t) last_blk) - start_blk + 1;
4766
4767                 /*
4768                  * Walk the extent tree gathering extent information
4769                  * and pushing extents back to the user.
4770                  */
4771                 error = ext4_fill_fiemap_extents(inode, start_blk,
4772                                                  len_blks, fieinfo);
4773         }
4774
4775         return error;
4776 }