1 /* 2 * linux/fs/ext4/indirect.c 3 * 4 * from 5 * 6 * linux/fs/ext4/inode.c 7 * 8 * Copyright (C) 1992, 1993, 1994, 1995 9 * Remy Card (card@masi.ibp.fr) 10 * Laboratoire MASI - Institut Blaise Pascal 11 * Universite Pierre et Marie Curie (Paris VI) 12 * 13 * from 14 * 15 * linux/fs/minix/inode.c 16 * 17 * Copyright (C) 1991, 1992 Linus Torvalds 18 * 19 * Goal-directed block allocation by Stephen Tweedie 20 * (sct@redhat.com), 1993, 1998 21 */ 22 23 #include <linux/aio.h> 24 #include "ext4_jbd2.h" 25 #include "truncate.h" 26 27 #include <trace/events/ext4.h> 28 29 typedef struct { 30 __le32 *p; 31 __le32 key; 32 struct buffer_head *bh; 33 } Indirect; 34 35 static inline void add_chain(Indirect *p, struct buffer_head *bh, __le32 *v) 36 { 37 p->key = *(p->p = v); 38 p->bh = bh; 39 } 40 41 /** 42 * ext4_block_to_path - parse the block number into array of offsets 43 * @inode: inode in question (we are only interested in its superblock) 44 * @i_block: block number to be parsed 45 * @offsets: array to store the offsets in 46 * @boundary: set this non-zero if the referred-to block is likely to be 47 * followed (on disk) by an indirect block. 48 * 49 * To store the locations of file's data ext4 uses a data structure common 50 * for UNIX filesystems - tree of pointers anchored in the inode, with 51 * data blocks at leaves and indirect blocks in intermediate nodes. 52 * This function translates the block number into path in that tree - 53 * return value is the path length and @offsets[n] is the offset of 54 * pointer to (n+1)th node in the nth one. If @block is out of range 55 * (negative or too large) warning is printed and zero returned. 56 * 57 * Note: function doesn't find node addresses, so no IO is needed. All 58 * we need to know is the capacity of indirect blocks (taken from the 59 * inode->i_sb). 60 */ 61 62 /* 63 * Portability note: the last comparison (check that we fit into triple 64 * indirect block) is spelled differently, because otherwise on an 65 * architecture with 32-bit longs and 8Kb pages we might get into trouble 66 * if our filesystem had 8Kb blocks. We might use long long, but that would 67 * kill us on x86. Oh, well, at least the sign propagation does not matter - 68 * i_block would have to be negative in the very beginning, so we would not 69 * get there at all. 70 */ 71 72 static int ext4_block_to_path(struct inode *inode, 73 ext4_lblk_t i_block, 74 ext4_lblk_t offsets[4], int *boundary) 75 { 76 int ptrs = EXT4_ADDR_PER_BLOCK(inode->i_sb); 77 int ptrs_bits = EXT4_ADDR_PER_BLOCK_BITS(inode->i_sb); 78 const long direct_blocks = EXT4_NDIR_BLOCKS, 79 indirect_blocks = ptrs, 80 double_blocks = (1 << (ptrs_bits * 2)); 81 int n = 0; 82 int final = 0; 83 84 if (i_block < direct_blocks) { 85 offsets[n++] = i_block; 86 final = direct_blocks; 87 } else if ((i_block -= direct_blocks) < indirect_blocks) { 88 offsets[n++] = EXT4_IND_BLOCK; 89 offsets[n++] = i_block; 90 final = ptrs; 91 } else if ((i_block -= indirect_blocks) < double_blocks) { 92 offsets[n++] = EXT4_DIND_BLOCK; 93 offsets[n++] = i_block >> ptrs_bits; 94 offsets[n++] = i_block & (ptrs - 1); 95 final = ptrs; 96 } else if (((i_block -= double_blocks) >> (ptrs_bits * 2)) < ptrs) { 97 offsets[n++] = EXT4_TIND_BLOCK; 98 offsets[n++] = i_block >> (ptrs_bits * 2); 99 offsets[n++] = (i_block >> ptrs_bits) & (ptrs - 1); 100 offsets[n++] = i_block & (ptrs - 1); 101 final = ptrs; 102 } else { 103 ext4_warning(inode->i_sb, "block %lu > max in inode %lu", 104 i_block + direct_blocks + 105 indirect_blocks + double_blocks, inode->i_ino); 106 } 107 if (boundary) 108 *boundary = final - 1 - (i_block & (ptrs - 1)); 109 return n; 110 } 111 112 /** 113 * ext4_get_branch - read the chain of indirect blocks leading to data 114 * @inode: inode in question 115 * @depth: depth of the chain (1 - direct pointer, etc.) 116 * @offsets: offsets of pointers in inode/indirect blocks 117 * @chain: place to store the result 118 * @err: here we store the error value 119 * 120 * Function fills the array of triples <key, p, bh> and returns %NULL 121 * if everything went OK or the pointer to the last filled triple 122 * (incomplete one) otherwise. Upon the return chain[i].key contains 123 * the number of (i+1)-th block in the chain (as it is stored in memory, 124 * i.e. little-endian 32-bit), chain[i].p contains the address of that 125 * number (it points into struct inode for i==0 and into the bh->b_data 126 * for i>0) and chain[i].bh points to the buffer_head of i-th indirect 127 * block for i>0 and NULL for i==0. In other words, it holds the block 128 * numbers of the chain, addresses they were taken from (and where we can 129 * verify that chain did not change) and buffer_heads hosting these 130 * numbers. 131 * 132 * Function stops when it stumbles upon zero pointer (absent block) 133 * (pointer to last triple returned, *@err == 0) 134 * or when it gets an IO error reading an indirect block 135 * (ditto, *@err == -EIO) 136 * or when it reads all @depth-1 indirect blocks successfully and finds 137 * the whole chain, all way to the data (returns %NULL, *err == 0). 138 * 139 * Need to be called with 140 * down_read(&EXT4_I(inode)->i_data_sem) 141 */ 142 static Indirect *ext4_get_branch(struct inode *inode, int depth, 143 ext4_lblk_t *offsets, 144 Indirect chain[4], int *err) 145 { 146 struct super_block *sb = inode->i_sb; 147 Indirect *p = chain; 148 struct buffer_head *bh; 149 int ret = -EIO; 150 151 *err = 0; 152 /* i_data is not going away, no lock needed */ 153 add_chain(chain, NULL, EXT4_I(inode)->i_data + *offsets); 154 if (!p->key) 155 goto no_block; 156 while (--depth) { 157 bh = sb_getblk(sb, le32_to_cpu(p->key)); 158 if (unlikely(!bh)) { 159 ret = -ENOMEM; 160 goto failure; 161 } 162 163 if (!bh_uptodate_or_lock(bh)) { 164 if (bh_submit_read(bh) < 0) { 165 put_bh(bh); 166 goto failure; 167 } 168 /* validate block references */ 169 if (ext4_check_indirect_blockref(inode, bh)) { 170 put_bh(bh); 171 goto failure; 172 } 173 } 174 175 add_chain(++p, bh, (__le32 *)bh->b_data + *++offsets); 176 /* Reader: end */ 177 if (!p->key) 178 goto no_block; 179 } 180 return NULL; 181 182 failure: 183 *err = ret; 184 no_block: 185 return p; 186 } 187 188 /** 189 * ext4_find_near - find a place for allocation with sufficient locality 190 * @inode: owner 191 * @ind: descriptor of indirect block. 192 * 193 * This function returns the preferred place for block allocation. 194 * It is used when heuristic for sequential allocation fails. 195 * Rules are: 196 * + if there is a block to the left of our position - allocate near it. 197 * + if pointer will live in indirect block - allocate near that block. 198 * + if pointer will live in inode - allocate in the same 199 * cylinder group. 200 * 201 * In the latter case we colour the starting block by the callers PID to 202 * prevent it from clashing with concurrent allocations for a different inode 203 * in the same block group. The PID is used here so that functionally related 204 * files will be close-by on-disk. 205 * 206 * Caller must make sure that @ind is valid and will stay that way. 207 */ 208 static ext4_fsblk_t ext4_find_near(struct inode *inode, Indirect *ind) 209 { 210 struct ext4_inode_info *ei = EXT4_I(inode); 211 __le32 *start = ind->bh ? (__le32 *) ind->bh->b_data : ei->i_data; 212 __le32 *p; 213 214 /* Try to find previous block */ 215 for (p = ind->p - 1; p >= start; p--) { 216 if (*p) 217 return le32_to_cpu(*p); 218 } 219 220 /* No such thing, so let's try location of indirect block */ 221 if (ind->bh) 222 return ind->bh->b_blocknr; 223 224 /* 225 * It is going to be referred to from the inode itself? OK, just put it 226 * into the same cylinder group then. 227 */ 228 return ext4_inode_to_goal_block(inode); 229 } 230 231 /** 232 * ext4_find_goal - find a preferred place for allocation. 233 * @inode: owner 234 * @block: block we want 235 * @partial: pointer to the last triple within a chain 236 * 237 * Normally this function find the preferred place for block allocation, 238 * returns it. 239 * Because this is only used for non-extent files, we limit the block nr 240 * to 32 bits. 241 */ 242 static ext4_fsblk_t ext4_find_goal(struct inode *inode, ext4_lblk_t block, 243 Indirect *partial) 244 { 245 ext4_fsblk_t goal; 246 247 /* 248 * XXX need to get goal block from mballoc's data structures 249 */ 250 251 goal = ext4_find_near(inode, partial); 252 goal = goal & EXT4_MAX_BLOCK_FILE_PHYS; 253 return goal; 254 } 255 256 /** 257 * ext4_blks_to_allocate - Look up the block map and count the number 258 * of direct blocks need to be allocated for the given branch. 259 * 260 * @branch: chain of indirect blocks 261 * @k: number of blocks need for indirect blocks 262 * @blks: number of data blocks to be mapped. 263 * @blocks_to_boundary: the offset in the indirect block 264 * 265 * return the total number of blocks to be allocate, including the 266 * direct and indirect blocks. 267 */ 268 static int ext4_blks_to_allocate(Indirect *branch, int k, unsigned int blks, 269 int blocks_to_boundary) 270 { 271 unsigned int count = 0; 272 273 /* 274 * Simple case, [t,d]Indirect block(s) has not allocated yet 275 * then it's clear blocks on that path have not allocated 276 */ 277 if (k > 0) { 278 /* right now we don't handle cross boundary allocation */ 279 if (blks < blocks_to_boundary + 1) 280 count += blks; 281 else 282 count += blocks_to_boundary + 1; 283 return count; 284 } 285 286 count++; 287 while (count < blks && count <= blocks_to_boundary && 288 le32_to_cpu(*(branch[0].p + count)) == 0) { 289 count++; 290 } 291 return count; 292 } 293 294 /** 295 * ext4_alloc_branch - allocate and set up a chain of blocks. 296 * @handle: handle for this transaction 297 * @inode: owner 298 * @indirect_blks: number of allocated indirect blocks 299 * @blks: number of allocated direct blocks 300 * @goal: preferred place for allocation 301 * @offsets: offsets (in the blocks) to store the pointers to next. 302 * @branch: place to store the chain in. 303 * 304 * This function allocates blocks, zeroes out all but the last one, 305 * links them into chain and (if we are synchronous) writes them to disk. 306 * In other words, it prepares a branch that can be spliced onto the 307 * inode. It stores the information about that chain in the branch[], in 308 * the same format as ext4_get_branch() would do. We are calling it after 309 * we had read the existing part of chain and partial points to the last 310 * triple of that (one with zero ->key). Upon the exit we have the same 311 * picture as after the successful ext4_get_block(), except that in one 312 * place chain is disconnected - *branch->p is still zero (we did not 313 * set the last link), but branch->key contains the number that should 314 * be placed into *branch->p to fill that gap. 315 * 316 * If allocation fails we free all blocks we've allocated (and forget 317 * their buffer_heads) and return the error value the from failed 318 * ext4_alloc_block() (normally -ENOSPC). Otherwise we set the chain 319 * as described above and return 0. 320 */ 321 static int ext4_alloc_branch(handle_t *handle, struct inode *inode, 322 ext4_lblk_t iblock, int indirect_blks, 323 int *blks, ext4_fsblk_t goal, 324 ext4_lblk_t *offsets, Indirect *branch) 325 { 326 struct ext4_allocation_request ar; 327 struct buffer_head * bh; 328 ext4_fsblk_t b, new_blocks[4]; 329 __le32 *p; 330 int i, j, err, len = 1; 331 332 /* 333 * Set up for the direct block allocation 334 */ 335 memset(&ar, 0, sizeof(ar)); 336 ar.inode = inode; 337 ar.len = *blks; 338 ar.logical = iblock; 339 if (S_ISREG(inode->i_mode)) 340 ar.flags = EXT4_MB_HINT_DATA; 341 342 for (i = 0; i <= indirect_blks; i++) { 343 if (i == indirect_blks) { 344 ar.goal = goal; 345 new_blocks[i] = ext4_mb_new_blocks(handle, &ar, &err); 346 } else 347 goal = new_blocks[i] = ext4_new_meta_blocks(handle, inode, 348 goal, 0, NULL, &err); 349 if (err) { 350 i--; 351 goto failed; 352 } 353 branch[i].key = cpu_to_le32(new_blocks[i]); 354 if (i == 0) 355 continue; 356 357 bh = branch[i].bh = sb_getblk(inode->i_sb, new_blocks[i-1]); 358 if (unlikely(!bh)) { 359 err = -ENOMEM; 360 goto failed; 361 } 362 lock_buffer(bh); 363 BUFFER_TRACE(bh, "call get_create_access"); 364 err = ext4_journal_get_create_access(handle, bh); 365 if (err) { 366 unlock_buffer(bh); 367 goto failed; 368 } 369 370 memset(bh->b_data, 0, bh->b_size); 371 p = branch[i].p = (__le32 *) bh->b_data + offsets[i]; 372 b = new_blocks[i]; 373 374 if (i == indirect_blks) 375 len = ar.len; 376 for (j = 0; j < len; j++) 377 *p++ = cpu_to_le32(b++); 378 379 BUFFER_TRACE(bh, "marking uptodate"); 380 set_buffer_uptodate(bh); 381 unlock_buffer(bh); 382 383 BUFFER_TRACE(bh, "call ext4_handle_dirty_metadata"); 384 err = ext4_handle_dirty_metadata(handle, inode, bh); 385 if (err) 386 goto failed; 387 } 388 *blks = ar.len; 389 return 0; 390 failed: 391 for (; i >= 0; i--) { 392 /* 393 * We want to ext4_forget() only freshly allocated indirect 394 * blocks. Buffer for new_blocks[i-1] is at branch[i].bh and 395 * buffer at branch[0].bh is indirect block / inode already 396 * existing before ext4_alloc_branch() was called. 397 */ 398 if (i > 0 && i != indirect_blks && branch[i].bh) 399 ext4_forget(handle, 1, inode, branch[i].bh, 400 branch[i].bh->b_blocknr); 401 ext4_free_blocks(handle, inode, NULL, new_blocks[i], 402 (i == indirect_blks) ? ar.len : 1, 0); 403 } 404 return err; 405 } 406 407 /** 408 * ext4_splice_branch - splice the allocated branch onto inode. 409 * @handle: handle for this transaction 410 * @inode: owner 411 * @block: (logical) number of block we are adding 412 * @chain: chain of indirect blocks (with a missing link - see 413 * ext4_alloc_branch) 414 * @where: location of missing link 415 * @num: number of indirect blocks we are adding 416 * @blks: number of direct blocks we are adding 417 * 418 * This function fills the missing link and does all housekeeping needed in 419 * inode (->i_blocks, etc.). In case of success we end up with the full 420 * chain to new block and return 0. 421 */ 422 static int ext4_splice_branch(handle_t *handle, struct inode *inode, 423 ext4_lblk_t block, Indirect *where, int num, 424 int blks) 425 { 426 int i; 427 int err = 0; 428 ext4_fsblk_t current_block; 429 430 /* 431 * If we're splicing into a [td]indirect block (as opposed to the 432 * inode) then we need to get write access to the [td]indirect block 433 * before the splice. 434 */ 435 if (where->bh) { 436 BUFFER_TRACE(where->bh, "get_write_access"); 437 err = ext4_journal_get_write_access(handle, where->bh); 438 if (err) 439 goto err_out; 440 } 441 /* That's it */ 442 443 *where->p = where->key; 444 445 /* 446 * Update the host buffer_head or inode to point to more just allocated 447 * direct blocks blocks 448 */ 449 if (num == 0 && blks > 1) { 450 current_block = le32_to_cpu(where->key) + 1; 451 for (i = 1; i < blks; i++) 452 *(where->p + i) = cpu_to_le32(current_block++); 453 } 454 455 /* We are done with atomic stuff, now do the rest of housekeeping */ 456 /* had we spliced it onto indirect block? */ 457 if (where->bh) { 458 /* 459 * If we spliced it onto an indirect block, we haven't 460 * altered the inode. Note however that if it is being spliced 461 * onto an indirect block at the very end of the file (the 462 * file is growing) then we *will* alter the inode to reflect 463 * the new i_size. But that is not done here - it is done in 464 * generic_commit_write->__mark_inode_dirty->ext4_dirty_inode. 465 */ 466 jbd_debug(5, "splicing indirect only\n"); 467 BUFFER_TRACE(where->bh, "call ext4_handle_dirty_metadata"); 468 err = ext4_handle_dirty_metadata(handle, inode, where->bh); 469 if (err) 470 goto err_out; 471 } else { 472 /* 473 * OK, we spliced it into the inode itself on a direct block. 474 */ 475 ext4_mark_inode_dirty(handle, inode); 476 jbd_debug(5, "splicing direct\n"); 477 } 478 return err; 479 480 err_out: 481 for (i = 1; i <= num; i++) { 482 /* 483 * branch[i].bh is newly allocated, so there is no 484 * need to revoke the block, which is why we don't 485 * need to set EXT4_FREE_BLOCKS_METADATA. 486 */ 487 ext4_free_blocks(handle, inode, where[i].bh, 0, 1, 488 EXT4_FREE_BLOCKS_FORGET); 489 } 490 ext4_free_blocks(handle, inode, NULL, le32_to_cpu(where[num].key), 491 blks, 0); 492 493 return err; 494 } 495 496 /* 497 * The ext4_ind_map_blocks() function handles non-extents inodes 498 * (i.e., using the traditional indirect/double-indirect i_blocks 499 * scheme) for ext4_map_blocks(). 500 * 501 * Allocation strategy is simple: if we have to allocate something, we will 502 * have to go the whole way to leaf. So let's do it before attaching anything 503 * to tree, set linkage between the newborn blocks, write them if sync is 504 * required, recheck the path, free and repeat if check fails, otherwise 505 * set the last missing link (that will protect us from any truncate-generated 506 * removals - all blocks on the path are immune now) and possibly force the 507 * write on the parent block. 508 * That has a nice additional property: no special recovery from the failed 509 * allocations is needed - we simply release blocks and do not touch anything 510 * reachable from inode. 511 * 512 * `handle' can be NULL if create == 0. 513 * 514 * return > 0, # of blocks mapped or allocated. 515 * return = 0, if plain lookup failed. 516 * return < 0, error case. 517 * 518 * The ext4_ind_get_blocks() function should be called with 519 * down_write(&EXT4_I(inode)->i_data_sem) if allocating filesystem 520 * blocks (i.e., flags has EXT4_GET_BLOCKS_CREATE set) or 521 * down_read(&EXT4_I(inode)->i_data_sem) if not allocating file system 522 * blocks. 523 */ 524 int ext4_ind_map_blocks(handle_t *handle, struct inode *inode, 525 struct ext4_map_blocks *map, 526 int flags) 527 { 528 int err = -EIO; 529 ext4_lblk_t offsets[4]; 530 Indirect chain[4]; 531 Indirect *partial; 532 ext4_fsblk_t goal; 533 int indirect_blks; 534 int blocks_to_boundary = 0; 535 int depth; 536 int count = 0; 537 ext4_fsblk_t first_block = 0; 538 539 trace_ext4_ind_map_blocks_enter(inode, map->m_lblk, map->m_len, flags); 540 J_ASSERT(!(ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))); 541 J_ASSERT(handle != NULL || (flags & EXT4_GET_BLOCKS_CREATE) == 0); 542 depth = ext4_block_to_path(inode, map->m_lblk, offsets, 543 &blocks_to_boundary); 544 545 if (depth == 0) 546 goto out; 547 548 partial = ext4_get_branch(inode, depth, offsets, chain, &err); 549 550 /* Simplest case - block found, no allocation needed */ 551 if (!partial) { 552 first_block = le32_to_cpu(chain[depth - 1].key); 553 count++; 554 /*map more blocks*/ 555 while (count < map->m_len && count <= blocks_to_boundary) { 556 ext4_fsblk_t blk; 557 558 blk = le32_to_cpu(*(chain[depth-1].p + count)); 559 560 if (blk == first_block + count) 561 count++; 562 else 563 break; 564 } 565 goto got_it; 566 } 567 568 /* Next simple case - plain lookup or failed read of indirect block */ 569 if ((flags & EXT4_GET_BLOCKS_CREATE) == 0 || err == -EIO) 570 goto cleanup; 571 572 /* 573 * Okay, we need to do block allocation. 574 */ 575 if (EXT4_HAS_RO_COMPAT_FEATURE(inode->i_sb, 576 EXT4_FEATURE_RO_COMPAT_BIGALLOC)) { 577 EXT4_ERROR_INODE(inode, "Can't allocate blocks for " 578 "non-extent mapped inodes with bigalloc"); 579 return -ENOSPC; 580 } 581 582 goal = ext4_find_goal(inode, map->m_lblk, partial); 583 584 /* the number of blocks need to allocate for [d,t]indirect blocks */ 585 indirect_blks = (chain + depth) - partial - 1; 586 587 /* 588 * Next look up the indirect map to count the totoal number of 589 * direct blocks to allocate for this branch. 590 */ 591 count = ext4_blks_to_allocate(partial, indirect_blks, 592 map->m_len, blocks_to_boundary); 593 /* 594 * Block out ext4_truncate while we alter the tree 595 */ 596 err = ext4_alloc_branch(handle, inode, map->m_lblk, indirect_blks, 597 &count, goal, 598 offsets + (partial - chain), partial); 599 600 /* 601 * The ext4_splice_branch call will free and forget any buffers 602 * on the new chain if there is a failure, but that risks using 603 * up transaction credits, especially for bitmaps where the 604 * credits cannot be returned. Can we handle this somehow? We 605 * may need to return -EAGAIN upwards in the worst case. --sct 606 */ 607 if (!err) 608 err = ext4_splice_branch(handle, inode, map->m_lblk, 609 partial, indirect_blks, count); 610 if (err) 611 goto cleanup; 612 613 map->m_flags |= EXT4_MAP_NEW; 614 615 ext4_update_inode_fsync_trans(handle, inode, 1); 616 got_it: 617 map->m_flags |= EXT4_MAP_MAPPED; 618 map->m_pblk = le32_to_cpu(chain[depth-1].key); 619 map->m_len = count; 620 if (count > blocks_to_boundary) 621 map->m_flags |= EXT4_MAP_BOUNDARY; 622 err = count; 623 /* Clean up and exit */ 624 partial = chain + depth - 1; /* the whole chain */ 625 cleanup: 626 while (partial > chain) { 627 BUFFER_TRACE(partial->bh, "call brelse"); 628 brelse(partial->bh); 629 partial--; 630 } 631 out: 632 trace_ext4_ind_map_blocks_exit(inode, flags, map, err); 633 return err; 634 } 635 636 /* 637 * O_DIRECT for ext3 (or indirect map) based files 638 * 639 * If the O_DIRECT write will extend the file then add this inode to the 640 * orphan list. So recovery will truncate it back to the original size 641 * if the machine crashes during the write. 642 * 643 * If the O_DIRECT write is intantiating holes inside i_size and the machine 644 * crashes then stale disk data _may_ be exposed inside the file. But current 645 * VFS code falls back into buffered path in that case so we are safe. 646 */ 647 ssize_t ext4_ind_direct_IO(int rw, struct kiocb *iocb, 648 struct iov_iter *iter, loff_t offset) 649 { 650 struct file *file = iocb->ki_filp; 651 struct inode *inode = file->f_mapping->host; 652 struct ext4_inode_info *ei = EXT4_I(inode); 653 handle_t *handle; 654 ssize_t ret; 655 int orphan = 0; 656 size_t count = iov_iter_count(iter); 657 int retries = 0; 658 659 if (rw == WRITE) { 660 loff_t final_size = offset + count; 661 662 if (final_size > inode->i_size) { 663 /* Credits for sb + inode write */ 664 handle = ext4_journal_start(inode, EXT4_HT_INODE, 2); 665 if (IS_ERR(handle)) { 666 ret = PTR_ERR(handle); 667 goto out; 668 } 669 ret = ext4_orphan_add(handle, inode); 670 if (ret) { 671 ext4_journal_stop(handle); 672 goto out; 673 } 674 orphan = 1; 675 ei->i_disksize = inode->i_size; 676 ext4_journal_stop(handle); 677 } 678 } 679 680 retry: 681 if (rw == READ && ext4_should_dioread_nolock(inode)) { 682 /* 683 * Nolock dioread optimization may be dynamically disabled 684 * via ext4_inode_block_unlocked_dio(). Check inode's state 685 * while holding extra i_dio_count ref. 686 */ 687 atomic_inc(&inode->i_dio_count); 688 smp_mb(); 689 if (unlikely(ext4_test_inode_state(inode, 690 EXT4_STATE_DIOREAD_LOCK))) { 691 inode_dio_done(inode); 692 goto locked; 693 } 694 ret = __blockdev_direct_IO(rw, iocb, inode, 695 inode->i_sb->s_bdev, iter, offset, 696 ext4_get_block, NULL, NULL, 0); 697 inode_dio_done(inode); 698 } else { 699 locked: 700 ret = blockdev_direct_IO(rw, iocb, inode, iter, 701 offset, ext4_get_block); 702 703 if (unlikely((rw & WRITE) && ret < 0)) { 704 loff_t isize = i_size_read(inode); 705 loff_t end = offset + count; 706 707 if (end > isize) 708 ext4_truncate_failed_write(inode); 709 } 710 } 711 if (ret == -ENOSPC && ext4_should_retry_alloc(inode->i_sb, &retries)) 712 goto retry; 713 714 if (orphan) { 715 int err; 716 717 /* Credits for sb + inode write */ 718 handle = ext4_journal_start(inode, EXT4_HT_INODE, 2); 719 if (IS_ERR(handle)) { 720 /* This is really bad luck. We've written the data 721 * but cannot extend i_size. Bail out and pretend 722 * the write failed... */ 723 ret = PTR_ERR(handle); 724 if (inode->i_nlink) 725 ext4_orphan_del(NULL, inode); 726 727 goto out; 728 } 729 if (inode->i_nlink) 730 ext4_orphan_del(handle, inode); 731 if (ret > 0) { 732 loff_t end = offset + ret; 733 if (end > inode->i_size) { 734 ei->i_disksize = end; 735 i_size_write(inode, end); 736 /* 737 * We're going to return a positive `ret' 738 * here due to non-zero-length I/O, so there's 739 * no way of reporting error returns from 740 * ext4_mark_inode_dirty() to userspace. So 741 * ignore it. 742 */ 743 ext4_mark_inode_dirty(handle, inode); 744 } 745 } 746 err = ext4_journal_stop(handle); 747 if (ret == 0) 748 ret = err; 749 } 750 out: 751 return ret; 752 } 753 754 /* 755 * Calculate the number of metadata blocks need to reserve 756 * to allocate a new block at @lblocks for non extent file based file 757 */ 758 int ext4_ind_calc_metadata_amount(struct inode *inode, sector_t lblock) 759 { 760 struct ext4_inode_info *ei = EXT4_I(inode); 761 sector_t dind_mask = ~((sector_t)EXT4_ADDR_PER_BLOCK(inode->i_sb) - 1); 762 int blk_bits; 763 764 if (lblock < EXT4_NDIR_BLOCKS) 765 return 0; 766 767 lblock -= EXT4_NDIR_BLOCKS; 768 769 if (ei->i_da_metadata_calc_len && 770 (lblock & dind_mask) == ei->i_da_metadata_calc_last_lblock) { 771 ei->i_da_metadata_calc_len++; 772 return 0; 773 } 774 ei->i_da_metadata_calc_last_lblock = lblock & dind_mask; 775 ei->i_da_metadata_calc_len = 1; 776 blk_bits = order_base_2(lblock); 777 return (blk_bits / EXT4_ADDR_PER_BLOCK_BITS(inode->i_sb)) + 1; 778 } 779 780 /* 781 * Calculate number of indirect blocks touched by mapping @nrblocks logically 782 * contiguous blocks 783 */ 784 int ext4_ind_trans_blocks(struct inode *inode, int nrblocks) 785 { 786 /* 787 * With N contiguous data blocks, we need at most 788 * N/EXT4_ADDR_PER_BLOCK(inode->i_sb) + 1 indirect blocks, 789 * 2 dindirect blocks, and 1 tindirect block 790 */ 791 return DIV_ROUND_UP(nrblocks, EXT4_ADDR_PER_BLOCK(inode->i_sb)) + 4; 792 } 793 794 /* 795 * Truncate transactions can be complex and absolutely huge. So we need to 796 * be able to restart the transaction at a conventient checkpoint to make 797 * sure we don't overflow the journal. 798 * 799 * Try to extend this transaction for the purposes of truncation. If 800 * extend fails, we need to propagate the failure up and restart the 801 * transaction in the top-level truncate loop. --sct 802 * 803 * Returns 0 if we managed to create more room. If we can't create more 804 * room, and the transaction must be restarted we return 1. 805 */ 806 static int try_to_extend_transaction(handle_t *handle, struct inode *inode) 807 { 808 if (!ext4_handle_valid(handle)) 809 return 0; 810 if (ext4_handle_has_enough_credits(handle, EXT4_RESERVE_TRANS_BLOCKS+1)) 811 return 0; 812 if (!ext4_journal_extend(handle, ext4_blocks_for_truncate(inode))) 813 return 0; 814 return 1; 815 } 816 817 /* 818 * Probably it should be a library function... search for first non-zero word 819 * or memcmp with zero_page, whatever is better for particular architecture. 820 * Linus? 821 */ 822 static inline int all_zeroes(__le32 *p, __le32 *q) 823 { 824 while (p < q) 825 if (*p++) 826 return 0; 827 return 1; 828 } 829 830 /** 831 * ext4_find_shared - find the indirect blocks for partial truncation. 832 * @inode: inode in question 833 * @depth: depth of the affected branch 834 * @offsets: offsets of pointers in that branch (see ext4_block_to_path) 835 * @chain: place to store the pointers to partial indirect blocks 836 * @top: place to the (detached) top of branch 837 * 838 * This is a helper function used by ext4_truncate(). 839 * 840 * When we do truncate() we may have to clean the ends of several 841 * indirect blocks but leave the blocks themselves alive. Block is 842 * partially truncated if some data below the new i_size is referred 843 * from it (and it is on the path to the first completely truncated 844 * data block, indeed). We have to free the top of that path along 845 * with everything to the right of the path. Since no allocation 846 * past the truncation point is possible until ext4_truncate() 847 * finishes, we may safely do the latter, but top of branch may 848 * require special attention - pageout below the truncation point 849 * might try to populate it. 850 * 851 * We atomically detach the top of branch from the tree, store the 852 * block number of its root in *@top, pointers to buffer_heads of 853 * partially truncated blocks - in @chain[].bh and pointers to 854 * their last elements that should not be removed - in 855 * @chain[].p. Return value is the pointer to last filled element 856 * of @chain. 857 * 858 * The work left to caller to do the actual freeing of subtrees: 859 * a) free the subtree starting from *@top 860 * b) free the subtrees whose roots are stored in 861 * (@chain[i].p+1 .. end of @chain[i].bh->b_data) 862 * c) free the subtrees growing from the inode past the @chain[0]. 863 * (no partially truncated stuff there). */ 864 865 static Indirect *ext4_find_shared(struct inode *inode, int depth, 866 ext4_lblk_t offsets[4], Indirect chain[4], 867 __le32 *top) 868 { 869 Indirect *partial, *p; 870 int k, err; 871 872 *top = 0; 873 /* Make k index the deepest non-null offset + 1 */ 874 for (k = depth; k > 1 && !offsets[k-1]; k--) 875 ; 876 partial = ext4_get_branch(inode, k, offsets, chain, &err); 877 /* Writer: pointers */ 878 if (!partial) 879 partial = chain + k-1; 880 /* 881 * If the branch acquired continuation since we've looked at it - 882 * fine, it should all survive and (new) top doesn't belong to us. 883 */ 884 if (!partial->key && *partial->p) 885 /* Writer: end */ 886 goto no_top; 887 for (p = partial; (p > chain) && all_zeroes((__le32 *) p->bh->b_data, p->p); p--) 888 ; 889 /* 890 * OK, we've found the last block that must survive. The rest of our 891 * branch should be detached before unlocking. However, if that rest 892 * of branch is all ours and does not grow immediately from the inode 893 * it's easier to cheat and just decrement partial->p. 894 */ 895 if (p == chain + k - 1 && p > chain) { 896 p->p--; 897 } else { 898 *top = *p->p; 899 /* Nope, don't do this in ext4. Must leave the tree intact */ 900 #if 0 901 *p->p = 0; 902 #endif 903 } 904 /* Writer: end */ 905 906 while (partial > p) { 907 brelse(partial->bh); 908 partial--; 909 } 910 no_top: 911 return partial; 912 } 913 914 /* 915 * Zero a number of block pointers in either an inode or an indirect block. 916 * If we restart the transaction we must again get write access to the 917 * indirect block for further modification. 918 * 919 * We release `count' blocks on disk, but (last - first) may be greater 920 * than `count' because there can be holes in there. 921 * 922 * Return 0 on success, 1 on invalid block range 923 * and < 0 on fatal error. 924 */ 925 static int ext4_clear_blocks(handle_t *handle, struct inode *inode, 926 struct buffer_head *bh, 927 ext4_fsblk_t block_to_free, 928 unsigned long count, __le32 *first, 929 __le32 *last) 930 { 931 __le32 *p; 932 int flags = EXT4_FREE_BLOCKS_VALIDATED; 933 int err; 934 935 if (S_ISDIR(inode->i_mode) || S_ISLNK(inode->i_mode)) 936 flags |= EXT4_FREE_BLOCKS_FORGET | EXT4_FREE_BLOCKS_METADATA; 937 else if (ext4_should_journal_data(inode)) 938 flags |= EXT4_FREE_BLOCKS_FORGET; 939 940 if (!ext4_data_block_valid(EXT4_SB(inode->i_sb), block_to_free, 941 count)) { 942 EXT4_ERROR_INODE(inode, "attempt to clear invalid " 943 "blocks %llu len %lu", 944 (unsigned long long) block_to_free, count); 945 return 1; 946 } 947 948 if (try_to_extend_transaction(handle, inode)) { 949 if (bh) { 950 BUFFER_TRACE(bh, "call ext4_handle_dirty_metadata"); 951 err = ext4_handle_dirty_metadata(handle, inode, bh); 952 if (unlikely(err)) 953 goto out_err; 954 } 955 err = ext4_mark_inode_dirty(handle, inode); 956 if (unlikely(err)) 957 goto out_err; 958 err = ext4_truncate_restart_trans(handle, inode, 959 ext4_blocks_for_truncate(inode)); 960 if (unlikely(err)) 961 goto out_err; 962 if (bh) { 963 BUFFER_TRACE(bh, "retaking write access"); 964 err = ext4_journal_get_write_access(handle, bh); 965 if (unlikely(err)) 966 goto out_err; 967 } 968 } 969 970 for (p = first; p < last; p++) 971 *p = 0; 972 973 ext4_free_blocks(handle, inode, NULL, block_to_free, count, flags); 974 return 0; 975 out_err: 976 ext4_std_error(inode->i_sb, err); 977 return err; 978 } 979 980 /** 981 * ext4_free_data - free a list of data blocks 982 * @handle: handle for this transaction 983 * @inode: inode we are dealing with 984 * @this_bh: indirect buffer_head which contains *@first and *@last 985 * @first: array of block numbers 986 * @last: points immediately past the end of array 987 * 988 * We are freeing all blocks referred from that array (numbers are stored as 989 * little-endian 32-bit) and updating @inode->i_blocks appropriately. 990 * 991 * We accumulate contiguous runs of blocks to free. Conveniently, if these 992 * blocks are contiguous then releasing them at one time will only affect one 993 * or two bitmap blocks (+ group descriptor(s) and superblock) and we won't 994 * actually use a lot of journal space. 995 * 996 * @this_bh will be %NULL if @first and @last point into the inode's direct 997 * block pointers. 998 */ 999 static void ext4_free_data(handle_t *handle, struct inode *inode, 1000 struct buffer_head *this_bh, 1001 __le32 *first, __le32 *last) 1002 { 1003 ext4_fsblk_t block_to_free = 0; /* Starting block # of a run */ 1004 unsigned long count = 0; /* Number of blocks in the run */ 1005 __le32 *block_to_free_p = NULL; /* Pointer into inode/ind 1006 corresponding to 1007 block_to_free */ 1008 ext4_fsblk_t nr; /* Current block # */ 1009 __le32 *p; /* Pointer into inode/ind 1010 for current block */ 1011 int err = 0; 1012 1013 if (this_bh) { /* For indirect block */ 1014 BUFFER_TRACE(this_bh, "get_write_access"); 1015 err = ext4_journal_get_write_access(handle, this_bh); 1016 /* Important: if we can't update the indirect pointers 1017 * to the blocks, we can't free them. */ 1018 if (err) 1019 return; 1020 } 1021 1022 for (p = first; p < last; p++) { 1023 nr = le32_to_cpu(*p); 1024 if (nr) { 1025 /* accumulate blocks to free if they're contiguous */ 1026 if (count == 0) { 1027 block_to_free = nr; 1028 block_to_free_p = p; 1029 count = 1; 1030 } else if (nr == block_to_free + count) { 1031 count++; 1032 } else { 1033 err = ext4_clear_blocks(handle, inode, this_bh, 1034 block_to_free, count, 1035 block_to_free_p, p); 1036 if (err) 1037 break; 1038 block_to_free = nr; 1039 block_to_free_p = p; 1040 count = 1; 1041 } 1042 } 1043 } 1044 1045 if (!err && count > 0) 1046 err = ext4_clear_blocks(handle, inode, this_bh, block_to_free, 1047 count, block_to_free_p, p); 1048 if (err < 0) 1049 /* fatal error */ 1050 return; 1051 1052 if (this_bh) { 1053 BUFFER_TRACE(this_bh, "call ext4_handle_dirty_metadata"); 1054 1055 /* 1056 * The buffer head should have an attached journal head at this 1057 * point. However, if the data is corrupted and an indirect 1058 * block pointed to itself, it would have been detached when 1059 * the block was cleared. Check for this instead of OOPSing. 1060 */ 1061 if ((EXT4_JOURNAL(inode) == NULL) || bh2jh(this_bh)) 1062 ext4_handle_dirty_metadata(handle, inode, this_bh); 1063 else 1064 EXT4_ERROR_INODE(inode, 1065 "circular indirect block detected at " 1066 "block %llu", 1067 (unsigned long long) this_bh->b_blocknr); 1068 } 1069 } 1070 1071 /** 1072 * ext4_free_branches - free an array of branches 1073 * @handle: JBD handle for this transaction 1074 * @inode: inode we are dealing with 1075 * @parent_bh: the buffer_head which contains *@first and *@last 1076 * @first: array of block numbers 1077 * @last: pointer immediately past the end of array 1078 * @depth: depth of the branches to free 1079 * 1080 * We are freeing all blocks referred from these branches (numbers are 1081 * stored as little-endian 32-bit) and updating @inode->i_blocks 1082 * appropriately. 1083 */ 1084 static void ext4_free_branches(handle_t *handle, struct inode *inode, 1085 struct buffer_head *parent_bh, 1086 __le32 *first, __le32 *last, int depth) 1087 { 1088 ext4_fsblk_t nr; 1089 __le32 *p; 1090 1091 if (ext4_handle_is_aborted(handle)) 1092 return; 1093 1094 if (depth--) { 1095 struct buffer_head *bh; 1096 int addr_per_block = EXT4_ADDR_PER_BLOCK(inode->i_sb); 1097 p = last; 1098 while (--p >= first) { 1099 nr = le32_to_cpu(*p); 1100 if (!nr) 1101 continue; /* A hole */ 1102 1103 if (!ext4_data_block_valid(EXT4_SB(inode->i_sb), 1104 nr, 1)) { 1105 EXT4_ERROR_INODE(inode, 1106 "invalid indirect mapped " 1107 "block %lu (level %d)", 1108 (unsigned long) nr, depth); 1109 break; 1110 } 1111 1112 /* Go read the buffer for the next level down */ 1113 bh = sb_bread(inode->i_sb, nr); 1114 1115 /* 1116 * A read failure? Report error and clear slot 1117 * (should be rare). 1118 */ 1119 if (!bh) { 1120 EXT4_ERROR_INODE_BLOCK(inode, nr, 1121 "Read failure"); 1122 continue; 1123 } 1124 1125 /* This zaps the entire block. Bottom up. */ 1126 BUFFER_TRACE(bh, "free child branches"); 1127 ext4_free_branches(handle, inode, bh, 1128 (__le32 *) bh->b_data, 1129 (__le32 *) bh->b_data + addr_per_block, 1130 depth); 1131 brelse(bh); 1132 1133 /* 1134 * Everything below this this pointer has been 1135 * released. Now let this top-of-subtree go. 1136 * 1137 * We want the freeing of this indirect block to be 1138 * atomic in the journal with the updating of the 1139 * bitmap block which owns it. So make some room in 1140 * the journal. 1141 * 1142 * We zero the parent pointer *after* freeing its 1143 * pointee in the bitmaps, so if extend_transaction() 1144 * for some reason fails to put the bitmap changes and 1145 * the release into the same transaction, recovery 1146 * will merely complain about releasing a free block, 1147 * rather than leaking blocks. 1148 */ 1149 if (ext4_handle_is_aborted(handle)) 1150 return; 1151 if (try_to_extend_transaction(handle, inode)) { 1152 ext4_mark_inode_dirty(handle, inode); 1153 ext4_truncate_restart_trans(handle, inode, 1154 ext4_blocks_for_truncate(inode)); 1155 } 1156 1157 /* 1158 * The forget flag here is critical because if 1159 * we are journaling (and not doing data 1160 * journaling), we have to make sure a revoke 1161 * record is written to prevent the journal 1162 * replay from overwriting the (former) 1163 * indirect block if it gets reallocated as a 1164 * data block. This must happen in the same 1165 * transaction where the data blocks are 1166 * actually freed. 1167 */ 1168 ext4_free_blocks(handle, inode, NULL, nr, 1, 1169 EXT4_FREE_BLOCKS_METADATA| 1170 EXT4_FREE_BLOCKS_FORGET); 1171 1172 if (parent_bh) { 1173 /* 1174 * The block which we have just freed is 1175 * pointed to by an indirect block: journal it 1176 */ 1177 BUFFER_TRACE(parent_bh, "get_write_access"); 1178 if (!ext4_journal_get_write_access(handle, 1179 parent_bh)){ 1180 *p = 0; 1181 BUFFER_TRACE(parent_bh, 1182 "call ext4_handle_dirty_metadata"); 1183 ext4_handle_dirty_metadata(handle, 1184 inode, 1185 parent_bh); 1186 } 1187 } 1188 } 1189 } else { 1190 /* We have reached the bottom of the tree. */ 1191 BUFFER_TRACE(parent_bh, "free data blocks"); 1192 ext4_free_data(handle, inode, parent_bh, first, last); 1193 } 1194 } 1195 1196 void ext4_ind_truncate(handle_t *handle, struct inode *inode) 1197 { 1198 struct ext4_inode_info *ei = EXT4_I(inode); 1199 __le32 *i_data = ei->i_data; 1200 int addr_per_block = EXT4_ADDR_PER_BLOCK(inode->i_sb); 1201 ext4_lblk_t offsets[4]; 1202 Indirect chain[4]; 1203 Indirect *partial; 1204 __le32 nr = 0; 1205 int n = 0; 1206 ext4_lblk_t last_block, max_block; 1207 unsigned blocksize = inode->i_sb->s_blocksize; 1208 1209 last_block = (inode->i_size + blocksize-1) 1210 >> EXT4_BLOCK_SIZE_BITS(inode->i_sb); 1211 max_block = (EXT4_SB(inode->i_sb)->s_bitmap_maxbytes + blocksize-1) 1212 >> EXT4_BLOCK_SIZE_BITS(inode->i_sb); 1213 1214 if (last_block != max_block) { 1215 n = ext4_block_to_path(inode, last_block, offsets, NULL); 1216 if (n == 0) 1217 return; 1218 } 1219 1220 ext4_es_remove_extent(inode, last_block, EXT_MAX_BLOCKS - last_block); 1221 1222 /* 1223 * The orphan list entry will now protect us from any crash which 1224 * occurs before the truncate completes, so it is now safe to propagate 1225 * the new, shorter inode size (held for now in i_size) into the 1226 * on-disk inode. We do this via i_disksize, which is the value which 1227 * ext4 *really* writes onto the disk inode. 1228 */ 1229 ei->i_disksize = inode->i_size; 1230 1231 if (last_block == max_block) { 1232 /* 1233 * It is unnecessary to free any data blocks if last_block is 1234 * equal to the indirect block limit. 1235 */ 1236 return; 1237 } else if (n == 1) { /* direct blocks */ 1238 ext4_free_data(handle, inode, NULL, i_data+offsets[0], 1239 i_data + EXT4_NDIR_BLOCKS); 1240 goto do_indirects; 1241 } 1242 1243 partial = ext4_find_shared(inode, n, offsets, chain, &nr); 1244 /* Kill the top of shared branch (not detached) */ 1245 if (nr) { 1246 if (partial == chain) { 1247 /* Shared branch grows from the inode */ 1248 ext4_free_branches(handle, inode, NULL, 1249 &nr, &nr+1, (chain+n-1) - partial); 1250 *partial->p = 0; 1251 /* 1252 * We mark the inode dirty prior to restart, 1253 * and prior to stop. No need for it here. 1254 */ 1255 } else { 1256 /* Shared branch grows from an indirect block */ 1257 BUFFER_TRACE(partial->bh, "get_write_access"); 1258 ext4_free_branches(handle, inode, partial->bh, 1259 partial->p, 1260 partial->p+1, (chain+n-1) - partial); 1261 } 1262 } 1263 /* Clear the ends of indirect blocks on the shared branch */ 1264 while (partial > chain) { 1265 ext4_free_branches(handle, inode, partial->bh, partial->p + 1, 1266 (__le32*)partial->bh->b_data+addr_per_block, 1267 (chain+n-1) - partial); 1268 BUFFER_TRACE(partial->bh, "call brelse"); 1269 brelse(partial->bh); 1270 partial--; 1271 } 1272 do_indirects: 1273 /* Kill the remaining (whole) subtrees */ 1274 switch (offsets[0]) { 1275 default: 1276 nr = i_data[EXT4_IND_BLOCK]; 1277 if (nr) { 1278 ext4_free_branches(handle, inode, NULL, &nr, &nr+1, 1); 1279 i_data[EXT4_IND_BLOCK] = 0; 1280 } 1281 case EXT4_IND_BLOCK: 1282 nr = i_data[EXT4_DIND_BLOCK]; 1283 if (nr) { 1284 ext4_free_branches(handle, inode, NULL, &nr, &nr+1, 2); 1285 i_data[EXT4_DIND_BLOCK] = 0; 1286 } 1287 case EXT4_DIND_BLOCK: 1288 nr = i_data[EXT4_TIND_BLOCK]; 1289 if (nr) { 1290 ext4_free_branches(handle, inode, NULL, &nr, &nr+1, 3); 1291 i_data[EXT4_TIND_BLOCK] = 0; 1292 } 1293 case EXT4_TIND_BLOCK: 1294 ; 1295 } 1296 } 1297 1298 /** 1299 * ext4_ind_remove_space - remove space from the range 1300 * @handle: JBD handle for this transaction 1301 * @inode: inode we are dealing with 1302 * @start: First block to remove 1303 * @end: One block after the last block to remove (exclusive) 1304 * 1305 * Free the blocks in the defined range (end is exclusive endpoint of 1306 * range). This is used by ext4_punch_hole(). 1307 */ 1308 int ext4_ind_remove_space(handle_t *handle, struct inode *inode, 1309 ext4_lblk_t start, ext4_lblk_t end) 1310 { 1311 struct ext4_inode_info *ei = EXT4_I(inode); 1312 __le32 *i_data = ei->i_data; 1313 int addr_per_block = EXT4_ADDR_PER_BLOCK(inode->i_sb); 1314 ext4_lblk_t offsets[4], offsets2[4]; 1315 Indirect chain[4], chain2[4]; 1316 Indirect *partial, *partial2; 1317 ext4_lblk_t max_block; 1318 __le32 nr = 0, nr2 = 0; 1319 int n = 0, n2 = 0; 1320 unsigned blocksize = inode->i_sb->s_blocksize; 1321 1322 max_block = (EXT4_SB(inode->i_sb)->s_bitmap_maxbytes + blocksize-1) 1323 >> EXT4_BLOCK_SIZE_BITS(inode->i_sb); 1324 if (end >= max_block) 1325 end = max_block; 1326 if ((start >= end) || (start > max_block)) 1327 return 0; 1328 1329 n = ext4_block_to_path(inode, start, offsets, NULL); 1330 n2 = ext4_block_to_path(inode, end, offsets2, NULL); 1331 1332 BUG_ON(n > n2); 1333 1334 if ((n == 1) && (n == n2)) { 1335 /* We're punching only within direct block range */ 1336 ext4_free_data(handle, inode, NULL, i_data + offsets[0], 1337 i_data + offsets2[0]); 1338 return 0; 1339 } else if (n2 > n) { 1340 /* 1341 * Start and end are on a different levels so we're going to 1342 * free partial block at start, and partial block at end of 1343 * the range. If there are some levels in between then 1344 * do_indirects label will take care of that. 1345 */ 1346 1347 if (n == 1) { 1348 /* 1349 * Start is at the direct block level, free 1350 * everything to the end of the level. 1351 */ 1352 ext4_free_data(handle, inode, NULL, i_data + offsets[0], 1353 i_data + EXT4_NDIR_BLOCKS); 1354 goto end_range; 1355 } 1356 1357 1358 partial = ext4_find_shared(inode, n, offsets, chain, &nr); 1359 if (nr) { 1360 if (partial == chain) { 1361 /* Shared branch grows from the inode */ 1362 ext4_free_branches(handle, inode, NULL, 1363 &nr, &nr+1, (chain+n-1) - partial); 1364 *partial->p = 0; 1365 } else { 1366 /* Shared branch grows from an indirect block */ 1367 BUFFER_TRACE(partial->bh, "get_write_access"); 1368 ext4_free_branches(handle, inode, partial->bh, 1369 partial->p, 1370 partial->p+1, (chain+n-1) - partial); 1371 } 1372 } 1373 1374 /* 1375 * Clear the ends of indirect blocks on the shared branch 1376 * at the start of the range 1377 */ 1378 while (partial > chain) { 1379 ext4_free_branches(handle, inode, partial->bh, 1380 partial->p + 1, 1381 (__le32 *)partial->bh->b_data+addr_per_block, 1382 (chain+n-1) - partial); 1383 BUFFER_TRACE(partial->bh, "call brelse"); 1384 brelse(partial->bh); 1385 partial--; 1386 } 1387 1388 end_range: 1389 partial2 = ext4_find_shared(inode, n2, offsets2, chain2, &nr2); 1390 if (nr2) { 1391 if (partial2 == chain2) { 1392 /* 1393 * Remember, end is exclusive so here we're at 1394 * the start of the next level we're not going 1395 * to free. Everything was covered by the start 1396 * of the range. 1397 */ 1398 return 0; 1399 } else { 1400 /* Shared branch grows from an indirect block */ 1401 partial2--; 1402 } 1403 } else { 1404 /* 1405 * ext4_find_shared returns Indirect structure which 1406 * points to the last element which should not be 1407 * removed by truncate. But this is end of the range 1408 * in punch_hole so we need to point to the next element 1409 */ 1410 partial2->p++; 1411 } 1412 1413 /* 1414 * Clear the ends of indirect blocks on the shared branch 1415 * at the end of the range 1416 */ 1417 while (partial2 > chain2) { 1418 ext4_free_branches(handle, inode, partial2->bh, 1419 (__le32 *)partial2->bh->b_data, 1420 partial2->p, 1421 (chain2+n2-1) - partial2); 1422 BUFFER_TRACE(partial2->bh, "call brelse"); 1423 brelse(partial2->bh); 1424 partial2--; 1425 } 1426 goto do_indirects; 1427 } 1428 1429 /* Punch happened within the same level (n == n2) */ 1430 partial = ext4_find_shared(inode, n, offsets, chain, &nr); 1431 partial2 = ext4_find_shared(inode, n2, offsets2, chain2, &nr2); 1432 /* 1433 * ext4_find_shared returns Indirect structure which 1434 * points to the last element which should not be 1435 * removed by truncate. But this is end of the range 1436 * in punch_hole so we need to point to the next element 1437 */ 1438 partial2->p++; 1439 while ((partial > chain) || (partial2 > chain2)) { 1440 /* We're at the same block, so we're almost finished */ 1441 if ((partial->bh && partial2->bh) && 1442 (partial->bh->b_blocknr == partial2->bh->b_blocknr)) { 1443 if ((partial > chain) && (partial2 > chain2)) { 1444 ext4_free_branches(handle, inode, partial->bh, 1445 partial->p + 1, 1446 partial2->p, 1447 (chain+n-1) - partial); 1448 BUFFER_TRACE(partial->bh, "call brelse"); 1449 brelse(partial->bh); 1450 BUFFER_TRACE(partial2->bh, "call brelse"); 1451 brelse(partial2->bh); 1452 } 1453 return 0; 1454 } 1455 /* 1456 * Clear the ends of indirect blocks on the shared branch 1457 * at the start of the range 1458 */ 1459 if (partial > chain) { 1460 ext4_free_branches(handle, inode, partial->bh, 1461 partial->p + 1, 1462 (__le32 *)partial->bh->b_data+addr_per_block, 1463 (chain+n-1) - partial); 1464 BUFFER_TRACE(partial->bh, "call brelse"); 1465 brelse(partial->bh); 1466 partial--; 1467 } 1468 /* 1469 * Clear the ends of indirect blocks on the shared branch 1470 * at the end of the range 1471 */ 1472 if (partial2 > chain2) { 1473 ext4_free_branches(handle, inode, partial2->bh, 1474 (__le32 *)partial2->bh->b_data, 1475 partial2->p, 1476 (chain2+n-1) - partial2); 1477 BUFFER_TRACE(partial2->bh, "call brelse"); 1478 brelse(partial2->bh); 1479 partial2--; 1480 } 1481 } 1482 1483 do_indirects: 1484 /* Kill the remaining (whole) subtrees */ 1485 switch (offsets[0]) { 1486 default: 1487 if (++n >= n2) 1488 return 0; 1489 nr = i_data[EXT4_IND_BLOCK]; 1490 if (nr) { 1491 ext4_free_branches(handle, inode, NULL, &nr, &nr+1, 1); 1492 i_data[EXT4_IND_BLOCK] = 0; 1493 } 1494 case EXT4_IND_BLOCK: 1495 if (++n >= n2) 1496 return 0; 1497 nr = i_data[EXT4_DIND_BLOCK]; 1498 if (nr) { 1499 ext4_free_branches(handle, inode, NULL, &nr, &nr+1, 2); 1500 i_data[EXT4_DIND_BLOCK] = 0; 1501 } 1502 case EXT4_DIND_BLOCK: 1503 if (++n >= n2) 1504 return 0; 1505 nr = i_data[EXT4_TIND_BLOCK]; 1506 if (nr) { 1507 ext4_free_branches(handle, inode, NULL, &nr, &nr+1, 3); 1508 i_data[EXT4_TIND_BLOCK] = 0; 1509 } 1510 case EXT4_TIND_BLOCK: 1511 ; 1512 } 1513 return 0; 1514 } 1515