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