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