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