1// SPDX-License-Identifier: GPL-2.0 2/* 3 * fs/ext4/extents_status.c 4 * 5 * Written by Yongqiang Yang <xiaoqiangnk@gmail.com> 6 * Modified by 7 * Allison Henderson <achender@linux.vnet.ibm.com> 8 * Hugh Dickins <hughd@google.com> 9 * Zheng Liu <wenqing.lz@taobao.com> 10 * 11 * Ext4 extents status tree core functions. 12 */ 13#include <linux/list_sort.h> 14#include <linux/proc_fs.h> 15#include <linux/seq_file.h> 16#include "ext4.h" 17 18#include <trace/events/ext4.h> 19 20/* 21 * According to previous discussion in Ext4 Developer Workshop, we 22 * will introduce a new structure called io tree to track all extent 23 * status in order to solve some problems that we have met 24 * (e.g. Reservation space warning), and provide extent-level locking. 25 * Delay extent tree is the first step to achieve this goal. It is 26 * original built by Yongqiang Yang. At that time it is called delay 27 * extent tree, whose goal is only track delayed extents in memory to 28 * simplify the implementation of fiemap and bigalloc, and introduce 29 * lseek SEEK_DATA/SEEK_HOLE support. That is why it is still called 30 * delay extent tree at the first commit. But for better understand 31 * what it does, it has been rename to extent status tree. 32 * 33 * Step1: 34 * Currently the first step has been done. All delayed extents are 35 * tracked in the tree. It maintains the delayed extent when a delayed 36 * allocation is issued, and the delayed extent is written out or 37 * invalidated. Therefore the implementation of fiemap and bigalloc 38 * are simplified, and SEEK_DATA/SEEK_HOLE are introduced. 39 * 40 * The following comment describes the implemenmtation of extent 41 * status tree and future works. 42 * 43 * Step2: 44 * In this step all extent status are tracked by extent status tree. 45 * Thus, we can first try to lookup a block mapping in this tree before 46 * finding it in extent tree. Hence, single extent cache can be removed 47 * because extent status tree can do a better job. Extents in status 48 * tree are loaded on-demand. Therefore, the extent status tree may not 49 * contain all of the extents in a file. Meanwhile we define a shrinker 50 * to reclaim memory from extent status tree because fragmented extent 51 * tree will make status tree cost too much memory. written/unwritten/- 52 * hole extents in the tree will be reclaimed by this shrinker when we 53 * are under high memory pressure. Delayed extents will not be 54 * reclimed because fiemap, bigalloc, and seek_data/hole need it. 55 */ 56 57/* 58 * Extent status tree implementation for ext4. 59 * 60 * 61 * ========================================================================== 62 * Extent status tree tracks all extent status. 63 * 64 * 1. Why we need to implement extent status tree? 65 * 66 * Without extent status tree, ext4 identifies a delayed extent by looking 67 * up page cache, this has several deficiencies - complicated, buggy, 68 * and inefficient code. 69 * 70 * FIEMAP, SEEK_HOLE/DATA, bigalloc, and writeout all need to know if a 71 * block or a range of blocks are belonged to a delayed extent. 72 * 73 * Let us have a look at how they do without extent status tree. 74 * -- FIEMAP 75 * FIEMAP looks up page cache to identify delayed allocations from holes. 76 * 77 * -- SEEK_HOLE/DATA 78 * SEEK_HOLE/DATA has the same problem as FIEMAP. 79 * 80 * -- bigalloc 81 * bigalloc looks up page cache to figure out if a block is 82 * already under delayed allocation or not to determine whether 83 * quota reserving is needed for the cluster. 84 * 85 * -- writeout 86 * Writeout looks up whole page cache to see if a buffer is 87 * mapped, If there are not very many delayed buffers, then it is 88 * time consuming. 89 * 90 * With extent status tree implementation, FIEMAP, SEEK_HOLE/DATA, 91 * bigalloc and writeout can figure out if a block or a range of 92 * blocks is under delayed allocation(belonged to a delayed extent) or 93 * not by searching the extent tree. 94 * 95 * 96 * ========================================================================== 97 * 2. Ext4 extent status tree impelmentation 98 * 99 * -- extent 100 * A extent is a range of blocks which are contiguous logically and 101 * physically. Unlike extent in extent tree, this extent in ext4 is 102 * a in-memory struct, there is no corresponding on-disk data. There 103 * is no limit on length of extent, so an extent can contain as many 104 * blocks as they are contiguous logically and physically. 105 * 106 * -- extent status tree 107 * Every inode has an extent status tree and all allocation blocks 108 * are added to the tree with different status. The extent in the 109 * tree are ordered by logical block no. 110 * 111 * -- operations on a extent status tree 112 * There are three important operations on a delayed extent tree: find 113 * next extent, adding a extent(a range of blocks) and removing a extent. 114 * 115 * -- race on a extent status tree 116 * Extent status tree is protected by inode->i_es_lock. 117 * 118 * -- memory consumption 119 * Fragmented extent tree will make extent status tree cost too much 120 * memory. Hence, we will reclaim written/unwritten/hole extents from 121 * the tree under a heavy memory pressure. 122 * 123 * 124 * ========================================================================== 125 * 3. Performance analysis 126 * 127 * -- overhead 128 * 1. There is a cache extent for write access, so if writes are 129 * not very random, adding space operaions are in O(1) time. 130 * 131 * -- gain 132 * 2. Code is much simpler, more readable, more maintainable and 133 * more efficient. 134 * 135 * 136 * ========================================================================== 137 * 4. TODO list 138 * 139 * -- Refactor delayed space reservation 140 * 141 * -- Extent-level locking 142 */ 143 144static struct kmem_cache *ext4_es_cachep; 145static struct kmem_cache *ext4_pending_cachep; 146 147static int __es_insert_extent(struct inode *inode, struct extent_status *newes, 148 struct extent_status *prealloc); 149static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk, 150 ext4_lblk_t end, int *reserved, 151 struct extent_status *prealloc); 152static int es_reclaim_extents(struct ext4_inode_info *ei, int *nr_to_scan); 153static int __es_shrink(struct ext4_sb_info *sbi, int nr_to_scan, 154 struct ext4_inode_info *locked_ei); 155static int __revise_pending(struct inode *inode, ext4_lblk_t lblk, 156 ext4_lblk_t len, 157 struct pending_reservation **prealloc); 158 159int __init ext4_init_es(void) 160{ 161 ext4_es_cachep = kmem_cache_create("ext4_extent_status", 162 sizeof(struct extent_status), 163 0, (SLAB_RECLAIM_ACCOUNT), NULL); 164 if (ext4_es_cachep == NULL) 165 return -ENOMEM; 166 return 0; 167} 168 169void ext4_exit_es(void) 170{ 171 kmem_cache_destroy(ext4_es_cachep); 172} 173 174void ext4_es_init_tree(struct ext4_es_tree *tree) 175{ 176 tree->root = RB_ROOT; 177 tree->cache_es = NULL; 178} 179 180#ifdef ES_DEBUG__ 181static void ext4_es_print_tree(struct inode *inode) 182{ 183 struct ext4_es_tree *tree; 184 struct rb_node *node; 185 186 printk(KERN_DEBUG "status extents for inode %lu:", inode->i_ino); 187 tree = &EXT4_I(inode)->i_es_tree; 188 node = rb_first(&tree->root); 189 while (node) { 190 struct extent_status *es; 191 es = rb_entry(node, struct extent_status, rb_node); 192 printk(KERN_DEBUG " [%u/%u) %llu %x", 193 es->es_lblk, es->es_len, 194 ext4_es_pblock(es), ext4_es_status(es)); 195 node = rb_next(node); 196 } 197 printk(KERN_DEBUG "\n"); 198} 199#else 200#define ext4_es_print_tree(inode) 201#endif 202 203static inline ext4_lblk_t ext4_es_end(struct extent_status *es) 204{ 205 BUG_ON(es->es_lblk + es->es_len < es->es_lblk); 206 return es->es_lblk + es->es_len - 1; 207} 208 209/* 210 * search through the tree for an delayed extent with a given offset. If 211 * it can't be found, try to find next extent. 212 */ 213static struct extent_status *__es_tree_search(struct rb_root *root, 214 ext4_lblk_t lblk) 215{ 216 struct rb_node *node = root->rb_node; 217 struct extent_status *es = NULL; 218 219 while (node) { 220 es = rb_entry(node, struct extent_status, rb_node); 221 if (lblk < es->es_lblk) 222 node = node->rb_left; 223 else if (lblk > ext4_es_end(es)) 224 node = node->rb_right; 225 else 226 return es; 227 } 228 229 if (es && lblk < es->es_lblk) 230 return es; 231 232 if (es && lblk > ext4_es_end(es)) { 233 node = rb_next(&es->rb_node); 234 return node ? rb_entry(node, struct extent_status, rb_node) : 235 NULL; 236 } 237 238 return NULL; 239} 240 241/* 242 * ext4_es_find_extent_range - find extent with specified status within block 243 * range or next extent following block range in 244 * extents status tree 245 * 246 * @inode - file containing the range 247 * @matching_fn - pointer to function that matches extents with desired status 248 * @lblk - logical block defining start of range 249 * @end - logical block defining end of range 250 * @es - extent found, if any 251 * 252 * Find the first extent within the block range specified by @lblk and @end 253 * in the extents status tree that satisfies @matching_fn. If a match 254 * is found, it's returned in @es. If not, and a matching extent is found 255 * beyond the block range, it's returned in @es. If no match is found, an 256 * extent is returned in @es whose es_lblk, es_len, and es_pblk components 257 * are 0. 258 */ 259static void __es_find_extent_range(struct inode *inode, 260 int (*matching_fn)(struct extent_status *es), 261 ext4_lblk_t lblk, ext4_lblk_t end, 262 struct extent_status *es) 263{ 264 struct ext4_es_tree *tree = NULL; 265 struct extent_status *es1 = NULL; 266 struct rb_node *node; 267 268 WARN_ON(es == NULL); 269 WARN_ON(end < lblk); 270 271 tree = &EXT4_I(inode)->i_es_tree; 272 273 /* see if the extent has been cached */ 274 es->es_lblk = es->es_len = es->es_pblk = 0; 275 es1 = READ_ONCE(tree->cache_es); 276 if (es1 && in_range(lblk, es1->es_lblk, es1->es_len)) { 277 es_debug("%u cached by [%u/%u) %llu %x\n", 278 lblk, es1->es_lblk, es1->es_len, 279 ext4_es_pblock(es1), ext4_es_status(es1)); 280 goto out; 281 } 282 283 es1 = __es_tree_search(&tree->root, lblk); 284 285out: 286 if (es1 && !matching_fn(es1)) { 287 while ((node = rb_next(&es1->rb_node)) != NULL) { 288 es1 = rb_entry(node, struct extent_status, rb_node); 289 if (es1->es_lblk > end) { 290 es1 = NULL; 291 break; 292 } 293 if (matching_fn(es1)) 294 break; 295 } 296 } 297 298 if (es1 && matching_fn(es1)) { 299 WRITE_ONCE(tree->cache_es, es1); 300 es->es_lblk = es1->es_lblk; 301 es->es_len = es1->es_len; 302 es->es_pblk = es1->es_pblk; 303 } 304 305} 306 307/* 308 * Locking for __es_find_extent_range() for external use 309 */ 310void ext4_es_find_extent_range(struct inode *inode, 311 int (*matching_fn)(struct extent_status *es), 312 ext4_lblk_t lblk, ext4_lblk_t end, 313 struct extent_status *es) 314{ 315 es->es_lblk = es->es_len = es->es_pblk = 0; 316 317 if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY) 318 return; 319 320 trace_ext4_es_find_extent_range_enter(inode, lblk); 321 322 read_lock(&EXT4_I(inode)->i_es_lock); 323 __es_find_extent_range(inode, matching_fn, lblk, end, es); 324 read_unlock(&EXT4_I(inode)->i_es_lock); 325 326 trace_ext4_es_find_extent_range_exit(inode, es); 327} 328 329/* 330 * __es_scan_range - search block range for block with specified status 331 * in extents status tree 332 * 333 * @inode - file containing the range 334 * @matching_fn - pointer to function that matches extents with desired status 335 * @lblk - logical block defining start of range 336 * @end - logical block defining end of range 337 * 338 * Returns true if at least one block in the specified block range satisfies 339 * the criterion specified by @matching_fn, and false if not. If at least 340 * one extent has the specified status, then there is at least one block 341 * in the cluster with that status. Should only be called by code that has 342 * taken i_es_lock. 343 */ 344static bool __es_scan_range(struct inode *inode, 345 int (*matching_fn)(struct extent_status *es), 346 ext4_lblk_t start, ext4_lblk_t end) 347{ 348 struct extent_status es; 349 350 __es_find_extent_range(inode, matching_fn, start, end, &es); 351 if (es.es_len == 0) 352 return false; /* no matching extent in the tree */ 353 else if (es.es_lblk <= start && 354 start < es.es_lblk + es.es_len) 355 return true; 356 else if (start <= es.es_lblk && es.es_lblk <= end) 357 return true; 358 else 359 return false; 360} 361/* 362 * Locking for __es_scan_range() for external use 363 */ 364bool ext4_es_scan_range(struct inode *inode, 365 int (*matching_fn)(struct extent_status *es), 366 ext4_lblk_t lblk, ext4_lblk_t end) 367{ 368 bool ret; 369 370 if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY) 371 return false; 372 373 read_lock(&EXT4_I(inode)->i_es_lock); 374 ret = __es_scan_range(inode, matching_fn, lblk, end); 375 read_unlock(&EXT4_I(inode)->i_es_lock); 376 377 return ret; 378} 379 380/* 381 * __es_scan_clu - search cluster for block with specified status in 382 * extents status tree 383 * 384 * @inode - file containing the cluster 385 * @matching_fn - pointer to function that matches extents with desired status 386 * @lblk - logical block in cluster to be searched 387 * 388 * Returns true if at least one extent in the cluster containing @lblk 389 * satisfies the criterion specified by @matching_fn, and false if not. If at 390 * least one extent has the specified status, then there is at least one block 391 * in the cluster with that status. Should only be called by code that has 392 * taken i_es_lock. 393 */ 394static bool __es_scan_clu(struct inode *inode, 395 int (*matching_fn)(struct extent_status *es), 396 ext4_lblk_t lblk) 397{ 398 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb); 399 ext4_lblk_t lblk_start, lblk_end; 400 401 lblk_start = EXT4_LBLK_CMASK(sbi, lblk); 402 lblk_end = lblk_start + sbi->s_cluster_ratio - 1; 403 404 return __es_scan_range(inode, matching_fn, lblk_start, lblk_end); 405} 406 407/* 408 * Locking for __es_scan_clu() for external use 409 */ 410bool ext4_es_scan_clu(struct inode *inode, 411 int (*matching_fn)(struct extent_status *es), 412 ext4_lblk_t lblk) 413{ 414 bool ret; 415 416 if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY) 417 return false; 418 419 read_lock(&EXT4_I(inode)->i_es_lock); 420 ret = __es_scan_clu(inode, matching_fn, lblk); 421 read_unlock(&EXT4_I(inode)->i_es_lock); 422 423 return ret; 424} 425 426static void ext4_es_list_add(struct inode *inode) 427{ 428 struct ext4_inode_info *ei = EXT4_I(inode); 429 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb); 430 431 if (!list_empty(&ei->i_es_list)) 432 return; 433 434 spin_lock(&sbi->s_es_lock); 435 if (list_empty(&ei->i_es_list)) { 436 list_add_tail(&ei->i_es_list, &sbi->s_es_list); 437 sbi->s_es_nr_inode++; 438 } 439 spin_unlock(&sbi->s_es_lock); 440} 441 442static void ext4_es_list_del(struct inode *inode) 443{ 444 struct ext4_inode_info *ei = EXT4_I(inode); 445 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb); 446 447 spin_lock(&sbi->s_es_lock); 448 if (!list_empty(&ei->i_es_list)) { 449 list_del_init(&ei->i_es_list); 450 sbi->s_es_nr_inode--; 451 WARN_ON_ONCE(sbi->s_es_nr_inode < 0); 452 } 453 spin_unlock(&sbi->s_es_lock); 454} 455 456static inline struct pending_reservation *__alloc_pending(bool nofail) 457{ 458 if (!nofail) 459 return kmem_cache_alloc(ext4_pending_cachep, GFP_ATOMIC); 460 461 return kmem_cache_zalloc(ext4_pending_cachep, GFP_KERNEL | __GFP_NOFAIL); 462} 463 464static inline void __free_pending(struct pending_reservation *pr) 465{ 466 kmem_cache_free(ext4_pending_cachep, pr); 467} 468 469/* 470 * Returns true if we cannot fail to allocate memory for this extent_status 471 * entry and cannot reclaim it until its status changes. 472 */ 473static inline bool ext4_es_must_keep(struct extent_status *es) 474{ 475 /* fiemap, bigalloc, and seek_data/hole need to use it. */ 476 if (ext4_es_is_delayed(es)) 477 return true; 478 479 return false; 480} 481 482static inline struct extent_status *__es_alloc_extent(bool nofail) 483{ 484 if (!nofail) 485 return kmem_cache_alloc(ext4_es_cachep, GFP_ATOMIC); 486 487 return kmem_cache_zalloc(ext4_es_cachep, GFP_KERNEL | __GFP_NOFAIL); 488} 489 490static void ext4_es_init_extent(struct inode *inode, struct extent_status *es, 491 ext4_lblk_t lblk, ext4_lblk_t len, ext4_fsblk_t pblk) 492{ 493 es->es_lblk = lblk; 494 es->es_len = len; 495 es->es_pblk = pblk; 496 497 /* We never try to reclaim a must kept extent, so we don't count it. */ 498 if (!ext4_es_must_keep(es)) { 499 if (!EXT4_I(inode)->i_es_shk_nr++) 500 ext4_es_list_add(inode); 501 percpu_counter_inc(&EXT4_SB(inode->i_sb)-> 502 s_es_stats.es_stats_shk_cnt); 503 } 504 505 EXT4_I(inode)->i_es_all_nr++; 506 percpu_counter_inc(&EXT4_SB(inode->i_sb)->s_es_stats.es_stats_all_cnt); 507} 508 509static inline void __es_free_extent(struct extent_status *es) 510{ 511 kmem_cache_free(ext4_es_cachep, es); 512} 513 514static void ext4_es_free_extent(struct inode *inode, struct extent_status *es) 515{ 516 EXT4_I(inode)->i_es_all_nr--; 517 percpu_counter_dec(&EXT4_SB(inode->i_sb)->s_es_stats.es_stats_all_cnt); 518 519 /* Decrease the shrink counter when we can reclaim the extent. */ 520 if (!ext4_es_must_keep(es)) { 521 BUG_ON(EXT4_I(inode)->i_es_shk_nr == 0); 522 if (!--EXT4_I(inode)->i_es_shk_nr) 523 ext4_es_list_del(inode); 524 percpu_counter_dec(&EXT4_SB(inode->i_sb)-> 525 s_es_stats.es_stats_shk_cnt); 526 } 527 528 __es_free_extent(es); 529} 530 531/* 532 * Check whether or not two extents can be merged 533 * Condition: 534 * - logical block number is contiguous 535 * - physical block number is contiguous 536 * - status is equal 537 */ 538static int ext4_es_can_be_merged(struct extent_status *es1, 539 struct extent_status *es2) 540{ 541 if (ext4_es_type(es1) != ext4_es_type(es2)) 542 return 0; 543 544 if (((__u64) es1->es_len) + es2->es_len > EXT_MAX_BLOCKS) { 545 pr_warn("ES assertion failed when merging extents. " 546 "The sum of lengths of es1 (%d) and es2 (%d) " 547 "is bigger than allowed file size (%d)\n", 548 es1->es_len, es2->es_len, EXT_MAX_BLOCKS); 549 WARN_ON(1); 550 return 0; 551 } 552 553 if (((__u64) es1->es_lblk) + es1->es_len != es2->es_lblk) 554 return 0; 555 556 if ((ext4_es_is_written(es1) || ext4_es_is_unwritten(es1)) && 557 (ext4_es_pblock(es1) + es1->es_len == ext4_es_pblock(es2))) 558 return 1; 559 560 if (ext4_es_is_hole(es1)) 561 return 1; 562 563 /* we need to check delayed extent is without unwritten status */ 564 if (ext4_es_is_delayed(es1) && !ext4_es_is_unwritten(es1)) 565 return 1; 566 567 return 0; 568} 569 570static struct extent_status * 571ext4_es_try_to_merge_left(struct inode *inode, struct extent_status *es) 572{ 573 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree; 574 struct extent_status *es1; 575 struct rb_node *node; 576 577 node = rb_prev(&es->rb_node); 578 if (!node) 579 return es; 580 581 es1 = rb_entry(node, struct extent_status, rb_node); 582 if (ext4_es_can_be_merged(es1, es)) { 583 es1->es_len += es->es_len; 584 if (ext4_es_is_referenced(es)) 585 ext4_es_set_referenced(es1); 586 rb_erase(&es->rb_node, &tree->root); 587 ext4_es_free_extent(inode, es); 588 es = es1; 589 } 590 591 return es; 592} 593 594static struct extent_status * 595ext4_es_try_to_merge_right(struct inode *inode, struct extent_status *es) 596{ 597 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree; 598 struct extent_status *es1; 599 struct rb_node *node; 600 601 node = rb_next(&es->rb_node); 602 if (!node) 603 return es; 604 605 es1 = rb_entry(node, struct extent_status, rb_node); 606 if (ext4_es_can_be_merged(es, es1)) { 607 es->es_len += es1->es_len; 608 if (ext4_es_is_referenced(es1)) 609 ext4_es_set_referenced(es); 610 rb_erase(node, &tree->root); 611 ext4_es_free_extent(inode, es1); 612 } 613 614 return es; 615} 616 617#ifdef ES_AGGRESSIVE_TEST 618#include "ext4_extents.h" /* Needed when ES_AGGRESSIVE_TEST is defined */ 619 620static void ext4_es_insert_extent_ext_check(struct inode *inode, 621 struct extent_status *es) 622{ 623 struct ext4_ext_path *path = NULL; 624 struct ext4_extent *ex; 625 ext4_lblk_t ee_block; 626 ext4_fsblk_t ee_start; 627 unsigned short ee_len; 628 int depth, ee_status, es_status; 629 630 path = ext4_find_extent(inode, es->es_lblk, NULL, EXT4_EX_NOCACHE); 631 if (IS_ERR(path)) 632 return; 633 634 depth = ext_depth(inode); 635 ex = path[depth].p_ext; 636 637 if (ex) { 638 639 ee_block = le32_to_cpu(ex->ee_block); 640 ee_start = ext4_ext_pblock(ex); 641 ee_len = ext4_ext_get_actual_len(ex); 642 643 ee_status = ext4_ext_is_unwritten(ex) ? 1 : 0; 644 es_status = ext4_es_is_unwritten(es) ? 1 : 0; 645 646 /* 647 * Make sure ex and es are not overlap when we try to insert 648 * a delayed/hole extent. 649 */ 650 if (!ext4_es_is_written(es) && !ext4_es_is_unwritten(es)) { 651 if (in_range(es->es_lblk, ee_block, ee_len)) { 652 pr_warn("ES insert assertion failed for " 653 "inode: %lu we can find an extent " 654 "at block [%d/%d/%llu/%c], but we " 655 "want to add a delayed/hole extent " 656 "[%d/%d/%llu/%x]\n", 657 inode->i_ino, ee_block, ee_len, 658 ee_start, ee_status ? 'u' : 'w', 659 es->es_lblk, es->es_len, 660 ext4_es_pblock(es), ext4_es_status(es)); 661 } 662 goto out; 663 } 664 665 /* 666 * We don't check ee_block == es->es_lblk, etc. because es 667 * might be a part of whole extent, vice versa. 668 */ 669 if (es->es_lblk < ee_block || 670 ext4_es_pblock(es) != ee_start + es->es_lblk - ee_block) { 671 pr_warn("ES insert assertion failed for inode: %lu " 672 "ex_status [%d/%d/%llu/%c] != " 673 "es_status [%d/%d/%llu/%c]\n", inode->i_ino, 674 ee_block, ee_len, ee_start, 675 ee_status ? 'u' : 'w', es->es_lblk, es->es_len, 676 ext4_es_pblock(es), es_status ? 'u' : 'w'); 677 goto out; 678 } 679 680 if (ee_status ^ es_status) { 681 pr_warn("ES insert assertion failed for inode: %lu " 682 "ex_status [%d/%d/%llu/%c] != " 683 "es_status [%d/%d/%llu/%c]\n", inode->i_ino, 684 ee_block, ee_len, ee_start, 685 ee_status ? 'u' : 'w', es->es_lblk, es->es_len, 686 ext4_es_pblock(es), es_status ? 'u' : 'w'); 687 } 688 } else { 689 /* 690 * We can't find an extent on disk. So we need to make sure 691 * that we don't want to add an written/unwritten extent. 692 */ 693 if (!ext4_es_is_delayed(es) && !ext4_es_is_hole(es)) { 694 pr_warn("ES insert assertion failed for inode: %lu " 695 "can't find an extent at block %d but we want " 696 "to add a written/unwritten extent " 697 "[%d/%d/%llu/%x]\n", inode->i_ino, 698 es->es_lblk, es->es_lblk, es->es_len, 699 ext4_es_pblock(es), ext4_es_status(es)); 700 } 701 } 702out: 703 ext4_ext_drop_refs(path); 704 kfree(path); 705} 706 707static void ext4_es_insert_extent_ind_check(struct inode *inode, 708 struct extent_status *es) 709{ 710 struct ext4_map_blocks map; 711 int retval; 712 713 /* 714 * Here we call ext4_ind_map_blocks to lookup a block mapping because 715 * 'Indirect' structure is defined in indirect.c. So we couldn't 716 * access direct/indirect tree from outside. It is too dirty to define 717 * this function in indirect.c file. 718 */ 719 720 map.m_lblk = es->es_lblk; 721 map.m_len = es->es_len; 722 723 retval = ext4_ind_map_blocks(NULL, inode, &map, 0); 724 if (retval > 0) { 725 if (ext4_es_is_delayed(es) || ext4_es_is_hole(es)) { 726 /* 727 * We want to add a delayed/hole extent but this 728 * block has been allocated. 729 */ 730 pr_warn("ES insert assertion failed for inode: %lu " 731 "We can find blocks but we want to add a " 732 "delayed/hole extent [%d/%d/%llu/%x]\n", 733 inode->i_ino, es->es_lblk, es->es_len, 734 ext4_es_pblock(es), ext4_es_status(es)); 735 return; 736 } else if (ext4_es_is_written(es)) { 737 if (retval != es->es_len) { 738 pr_warn("ES insert assertion failed for " 739 "inode: %lu retval %d != es_len %d\n", 740 inode->i_ino, retval, es->es_len); 741 return; 742 } 743 if (map.m_pblk != ext4_es_pblock(es)) { 744 pr_warn("ES insert assertion failed for " 745 "inode: %lu m_pblk %llu != " 746 "es_pblk %llu\n", 747 inode->i_ino, map.m_pblk, 748 ext4_es_pblock(es)); 749 return; 750 } 751 } else { 752 /* 753 * We don't need to check unwritten extent because 754 * indirect-based file doesn't have it. 755 */ 756 BUG(); 757 } 758 } else if (retval == 0) { 759 if (ext4_es_is_written(es)) { 760 pr_warn("ES insert assertion failed for inode: %lu " 761 "We can't find the block but we want to add " 762 "a written extent [%d/%d/%llu/%x]\n", 763 inode->i_ino, es->es_lblk, es->es_len, 764 ext4_es_pblock(es), ext4_es_status(es)); 765 return; 766 } 767 } 768} 769 770static inline void ext4_es_insert_extent_check(struct inode *inode, 771 struct extent_status *es) 772{ 773 /* 774 * We don't need to worry about the race condition because 775 * caller takes i_data_sem locking. 776 */ 777 BUG_ON(!rwsem_is_locked(&EXT4_I(inode)->i_data_sem)); 778 if (ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)) 779 ext4_es_insert_extent_ext_check(inode, es); 780 else 781 ext4_es_insert_extent_ind_check(inode, es); 782} 783#else 784static inline void ext4_es_insert_extent_check(struct inode *inode, 785 struct extent_status *es) 786{ 787} 788#endif 789 790static int __es_insert_extent(struct inode *inode, struct extent_status *newes, 791 struct extent_status *prealloc) 792{ 793 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree; 794 struct rb_node **p = &tree->root.rb_node; 795 struct rb_node *parent = NULL; 796 struct extent_status *es; 797 798 while (*p) { 799 parent = *p; 800 es = rb_entry(parent, struct extent_status, rb_node); 801 802 if (newes->es_lblk < es->es_lblk) { 803 if (ext4_es_can_be_merged(newes, es)) { 804 /* 805 * Here we can modify es_lblk directly 806 * because it isn't overlapped. 807 */ 808 es->es_lblk = newes->es_lblk; 809 es->es_len += newes->es_len; 810 if (ext4_es_is_written(es) || 811 ext4_es_is_unwritten(es)) 812 ext4_es_store_pblock(es, 813 newes->es_pblk); 814 es = ext4_es_try_to_merge_left(inode, es); 815 goto out; 816 } 817 p = &(*p)->rb_left; 818 } else if (newes->es_lblk > ext4_es_end(es)) { 819 if (ext4_es_can_be_merged(es, newes)) { 820 es->es_len += newes->es_len; 821 es = ext4_es_try_to_merge_right(inode, es); 822 goto out; 823 } 824 p = &(*p)->rb_right; 825 } else { 826 BUG(); 827 return -EINVAL; 828 } 829 } 830 831 if (prealloc) 832 es = prealloc; 833 else 834 es = __es_alloc_extent(false); 835 if (!es) 836 return -ENOMEM; 837 ext4_es_init_extent(inode, es, newes->es_lblk, newes->es_len, 838 newes->es_pblk); 839 840 rb_link_node(&es->rb_node, parent, p); 841 rb_insert_color(&es->rb_node, &tree->root); 842 843out: 844 tree->cache_es = es; 845 return 0; 846} 847 848/* 849 * ext4_es_insert_extent() adds information to an inode's extent 850 * status tree. 851 * 852 * Return 0 on success, error code on failure. 853 */ 854int ext4_es_insert_extent(struct inode *inode, ext4_lblk_t lblk, 855 ext4_lblk_t len, ext4_fsblk_t pblk, 856 unsigned int status) 857{ 858 struct extent_status newes; 859 ext4_lblk_t end = lblk + len - 1; 860 int err1 = 0, err2 = 0, err3 = 0; 861 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb); 862 struct extent_status *es1 = NULL; 863 struct extent_status *es2 = NULL; 864 struct pending_reservation *pr = NULL; 865 bool revise_pending = false; 866 867 if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY) 868 return 0; 869 870 es_debug("add [%u/%u) %llu %x to extent status tree of inode %lu\n", 871 lblk, len, pblk, status, inode->i_ino); 872 873 if (!len) 874 return 0; 875 876 BUG_ON(end < lblk); 877 878 if ((status & EXTENT_STATUS_DELAYED) && 879 (status & EXTENT_STATUS_WRITTEN)) { 880 ext4_warning(inode->i_sb, "Inserting extent [%u/%u] as " 881 " delayed and written which can potentially " 882 " cause data loss.", lblk, len); 883 WARN_ON(1); 884 } 885 886 newes.es_lblk = lblk; 887 newes.es_len = len; 888 ext4_es_store_pblock_status(&newes, pblk, status); 889 trace_ext4_es_insert_extent(inode, &newes); 890 891 ext4_es_insert_extent_check(inode, &newes); 892 893 revise_pending = sbi->s_cluster_ratio > 1 && 894 test_opt(inode->i_sb, DELALLOC) && 895 (status & (EXTENT_STATUS_WRITTEN | 896 EXTENT_STATUS_UNWRITTEN)); 897retry: 898 if (err1 && !es1) 899 es1 = __es_alloc_extent(true); 900 if ((err1 || err2) && !es2) 901 es2 = __es_alloc_extent(true); 902 if ((err1 || err2 || err3) && revise_pending && !pr) 903 pr = __alloc_pending(true); 904 write_lock(&EXT4_I(inode)->i_es_lock); 905 906 err1 = __es_remove_extent(inode, lblk, end, NULL, es1); 907 if (err1 != 0) 908 goto error; 909 /* Free preallocated extent if it didn't get used. */ 910 if (es1) { 911 if (!es1->es_len) 912 __es_free_extent(es1); 913 es1 = NULL; 914 } 915 916 err2 = __es_insert_extent(inode, &newes, es2); 917 if (err2 == -ENOMEM && !ext4_es_must_keep(&newes)) 918 err2 = 0; 919 if (err2 != 0) 920 goto error; 921 /* Free preallocated extent if it didn't get used. */ 922 if (es2) { 923 if (!es2->es_len) 924 __es_free_extent(es2); 925 es2 = NULL; 926 } 927 928 if (revise_pending) { 929 err3 = __revise_pending(inode, lblk, len, &pr); 930 if (err3 != 0) 931 goto error; 932 if (pr) { 933 __free_pending(pr); 934 pr = NULL; 935 } 936 } 937error: 938 write_unlock(&EXT4_I(inode)->i_es_lock); 939 if (err1 || err2 || err3) 940 goto retry; 941 942 ext4_es_print_tree(inode); 943 return 0; 944} 945 946/* 947 * ext4_es_cache_extent() inserts information into the extent status 948 * tree if and only if there isn't information about the range in 949 * question already. 950 */ 951void ext4_es_cache_extent(struct inode *inode, ext4_lblk_t lblk, 952 ext4_lblk_t len, ext4_fsblk_t pblk, 953 unsigned int status) 954{ 955 struct extent_status *es; 956 struct extent_status newes; 957 ext4_lblk_t end = lblk + len - 1; 958 959 if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY) 960 return; 961 962 newes.es_lblk = lblk; 963 newes.es_len = len; 964 ext4_es_store_pblock_status(&newes, pblk, status); 965 trace_ext4_es_cache_extent(inode, &newes); 966 967 if (!len) 968 return; 969 970 BUG_ON(end < lblk); 971 972 write_lock(&EXT4_I(inode)->i_es_lock); 973 974 es = __es_tree_search(&EXT4_I(inode)->i_es_tree.root, lblk); 975 if (!es || es->es_lblk > end) 976 __es_insert_extent(inode, &newes, NULL); 977 write_unlock(&EXT4_I(inode)->i_es_lock); 978} 979 980/* 981 * ext4_es_lookup_extent() looks up an extent in extent status tree. 982 * 983 * ext4_es_lookup_extent is called by ext4_map_blocks/ext4_da_map_blocks. 984 * 985 * Return: 1 on found, 0 on not 986 */ 987int ext4_es_lookup_extent(struct inode *inode, ext4_lblk_t lblk, 988 ext4_lblk_t *next_lblk, 989 struct extent_status *es) 990{ 991 struct ext4_es_tree *tree; 992 struct ext4_es_stats *stats; 993 struct extent_status *es1 = NULL; 994 struct rb_node *node; 995 int found = 0; 996 997 if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY) 998 return 0; 999 1000 trace_ext4_es_lookup_extent_enter(inode, lblk); 1001 es_debug("lookup extent in block %u\n", lblk); 1002 1003 tree = &EXT4_I(inode)->i_es_tree; 1004 read_lock(&EXT4_I(inode)->i_es_lock); 1005 1006 /* find extent in cache firstly */ 1007 es->es_lblk = es->es_len = es->es_pblk = 0; 1008 es1 = READ_ONCE(tree->cache_es); 1009 if (es1 && in_range(lblk, es1->es_lblk, es1->es_len)) { 1010 es_debug("%u cached by [%u/%u)\n", 1011 lblk, es1->es_lblk, es1->es_len); 1012 found = 1; 1013 goto out; 1014 } 1015 1016 node = tree->root.rb_node; 1017 while (node) { 1018 es1 = rb_entry(node, struct extent_status, rb_node); 1019 if (lblk < es1->es_lblk) 1020 node = node->rb_left; 1021 else if (lblk > ext4_es_end(es1)) 1022 node = node->rb_right; 1023 else { 1024 found = 1; 1025 break; 1026 } 1027 } 1028 1029out: 1030 stats = &EXT4_SB(inode->i_sb)->s_es_stats; 1031 if (found) { 1032 BUG_ON(!es1); 1033 es->es_lblk = es1->es_lblk; 1034 es->es_len = es1->es_len; 1035 es->es_pblk = es1->es_pblk; 1036 if (!ext4_es_is_referenced(es1)) 1037 ext4_es_set_referenced(es1); 1038 percpu_counter_inc(&stats->es_stats_cache_hits); 1039 if (next_lblk) { 1040 node = rb_next(&es1->rb_node); 1041 if (node) { 1042 es1 = rb_entry(node, struct extent_status, 1043 rb_node); 1044 *next_lblk = es1->es_lblk; 1045 } else 1046 *next_lblk = 0; 1047 } 1048 } else { 1049 percpu_counter_inc(&stats->es_stats_cache_misses); 1050 } 1051 1052 read_unlock(&EXT4_I(inode)->i_es_lock); 1053 1054 trace_ext4_es_lookup_extent_exit(inode, es, found); 1055 return found; 1056} 1057 1058struct rsvd_count { 1059 int ndelonly; 1060 bool first_do_lblk_found; 1061 ext4_lblk_t first_do_lblk; 1062 ext4_lblk_t last_do_lblk; 1063 struct extent_status *left_es; 1064 bool partial; 1065 ext4_lblk_t lclu; 1066}; 1067 1068/* 1069 * init_rsvd - initialize reserved count data before removing block range 1070 * in file from extent status tree 1071 * 1072 * @inode - file containing range 1073 * @lblk - first block in range 1074 * @es - pointer to first extent in range 1075 * @rc - pointer to reserved count data 1076 * 1077 * Assumes es is not NULL 1078 */ 1079static void init_rsvd(struct inode *inode, ext4_lblk_t lblk, 1080 struct extent_status *es, struct rsvd_count *rc) 1081{ 1082 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb); 1083 struct rb_node *node; 1084 1085 rc->ndelonly = 0; 1086 1087 /* 1088 * for bigalloc, note the first delonly block in the range has not 1089 * been found, record the extent containing the block to the left of 1090 * the region to be removed, if any, and note that there's no partial 1091 * cluster to track 1092 */ 1093 if (sbi->s_cluster_ratio > 1) { 1094 rc->first_do_lblk_found = false; 1095 if (lblk > es->es_lblk) { 1096 rc->left_es = es; 1097 } else { 1098 node = rb_prev(&es->rb_node); 1099 rc->left_es = node ? rb_entry(node, 1100 struct extent_status, 1101 rb_node) : NULL; 1102 } 1103 rc->partial = false; 1104 } 1105} 1106 1107/* 1108 * count_rsvd - count the clusters containing delayed and not unwritten 1109 * (delonly) blocks in a range within an extent and add to 1110 * the running tally in rsvd_count 1111 * 1112 * @inode - file containing extent 1113 * @lblk - first block in range 1114 * @len - length of range in blocks 1115 * @es - pointer to extent containing clusters to be counted 1116 * @rc - pointer to reserved count data 1117 * 1118 * Tracks partial clusters found at the beginning and end of extents so 1119 * they aren't overcounted when they span adjacent extents 1120 */ 1121static void count_rsvd(struct inode *inode, ext4_lblk_t lblk, long len, 1122 struct extent_status *es, struct rsvd_count *rc) 1123{ 1124 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb); 1125 ext4_lblk_t i, end, nclu; 1126 1127 if (!ext4_es_is_delonly(es)) 1128 return; 1129 1130 WARN_ON(len <= 0); 1131 1132 if (sbi->s_cluster_ratio == 1) { 1133 rc->ndelonly += (int) len; 1134 return; 1135 } 1136 1137 /* bigalloc */ 1138 1139 i = (lblk < es->es_lblk) ? es->es_lblk : lblk; 1140 end = lblk + (ext4_lblk_t) len - 1; 1141 end = (end > ext4_es_end(es)) ? ext4_es_end(es) : end; 1142 1143 /* record the first block of the first delonly extent seen */ 1144 if (!rc->first_do_lblk_found) { 1145 rc->first_do_lblk = i; 1146 rc->first_do_lblk_found = true; 1147 } 1148 1149 /* update the last lblk in the region seen so far */ 1150 rc->last_do_lblk = end; 1151 1152 /* 1153 * if we're tracking a partial cluster and the current extent 1154 * doesn't start with it, count it and stop tracking 1155 */ 1156 if (rc->partial && (rc->lclu != EXT4_B2C(sbi, i))) { 1157 rc->ndelonly++; 1158 rc->partial = false; 1159 } 1160 1161 /* 1162 * if the first cluster doesn't start on a cluster boundary but 1163 * ends on one, count it 1164 */ 1165 if (EXT4_LBLK_COFF(sbi, i) != 0) { 1166 if (end >= EXT4_LBLK_CFILL(sbi, i)) { 1167 rc->ndelonly++; 1168 rc->partial = false; 1169 i = EXT4_LBLK_CFILL(sbi, i) + 1; 1170 } 1171 } 1172 1173 /* 1174 * if the current cluster starts on a cluster boundary, count the 1175 * number of whole delonly clusters in the extent 1176 */ 1177 if ((i + sbi->s_cluster_ratio - 1) <= end) { 1178 nclu = (end - i + 1) >> sbi->s_cluster_bits; 1179 rc->ndelonly += nclu; 1180 i += nclu << sbi->s_cluster_bits; 1181 } 1182 1183 /* 1184 * start tracking a partial cluster if there's a partial at the end 1185 * of the current extent and we're not already tracking one 1186 */ 1187 if (!rc->partial && i <= end) { 1188 rc->partial = true; 1189 rc->lclu = EXT4_B2C(sbi, i); 1190 } 1191} 1192 1193/* 1194 * __pr_tree_search - search for a pending cluster reservation 1195 * 1196 * @root - root of pending reservation tree 1197 * @lclu - logical cluster to search for 1198 * 1199 * Returns the pending reservation for the cluster identified by @lclu 1200 * if found. If not, returns a reservation for the next cluster if any, 1201 * and if not, returns NULL. 1202 */ 1203static struct pending_reservation *__pr_tree_search(struct rb_root *root, 1204 ext4_lblk_t lclu) 1205{ 1206 struct rb_node *node = root->rb_node; 1207 struct pending_reservation *pr = NULL; 1208 1209 while (node) { 1210 pr = rb_entry(node, struct pending_reservation, rb_node); 1211 if (lclu < pr->lclu) 1212 node = node->rb_left; 1213 else if (lclu > pr->lclu) 1214 node = node->rb_right; 1215 else 1216 return pr; 1217 } 1218 if (pr && lclu < pr->lclu) 1219 return pr; 1220 if (pr && lclu > pr->lclu) { 1221 node = rb_next(&pr->rb_node); 1222 return node ? rb_entry(node, struct pending_reservation, 1223 rb_node) : NULL; 1224 } 1225 return NULL; 1226} 1227 1228/* 1229 * get_rsvd - calculates and returns the number of cluster reservations to be 1230 * released when removing a block range from the extent status tree 1231 * and releases any pending reservations within the range 1232 * 1233 * @inode - file containing block range 1234 * @end - last block in range 1235 * @right_es - pointer to extent containing next block beyond end or NULL 1236 * @rc - pointer to reserved count data 1237 * 1238 * The number of reservations to be released is equal to the number of 1239 * clusters containing delayed and not unwritten (delonly) blocks within 1240 * the range, minus the number of clusters still containing delonly blocks 1241 * at the ends of the range, and minus the number of pending reservations 1242 * within the range. 1243 */ 1244static unsigned int get_rsvd(struct inode *inode, ext4_lblk_t end, 1245 struct extent_status *right_es, 1246 struct rsvd_count *rc) 1247{ 1248 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb); 1249 struct pending_reservation *pr; 1250 struct ext4_pending_tree *tree = &EXT4_I(inode)->i_pending_tree; 1251 struct rb_node *node; 1252 ext4_lblk_t first_lclu, last_lclu; 1253 bool left_delonly, right_delonly, count_pending; 1254 struct extent_status *es; 1255 1256 if (sbi->s_cluster_ratio > 1) { 1257 /* count any remaining partial cluster */ 1258 if (rc->partial) 1259 rc->ndelonly++; 1260 1261 if (rc->ndelonly == 0) 1262 return 0; 1263 1264 first_lclu = EXT4_B2C(sbi, rc->first_do_lblk); 1265 last_lclu = EXT4_B2C(sbi, rc->last_do_lblk); 1266 1267 /* 1268 * decrease the delonly count by the number of clusters at the 1269 * ends of the range that still contain delonly blocks - 1270 * these clusters still need to be reserved 1271 */ 1272 left_delonly = right_delonly = false; 1273 1274 es = rc->left_es; 1275 while (es && ext4_es_end(es) >= 1276 EXT4_LBLK_CMASK(sbi, rc->first_do_lblk)) { 1277 if (ext4_es_is_delonly(es)) { 1278 rc->ndelonly--; 1279 left_delonly = true; 1280 break; 1281 } 1282 node = rb_prev(&es->rb_node); 1283 if (!node) 1284 break; 1285 es = rb_entry(node, struct extent_status, rb_node); 1286 } 1287 if (right_es && (!left_delonly || first_lclu != last_lclu)) { 1288 if (end < ext4_es_end(right_es)) { 1289 es = right_es; 1290 } else { 1291 node = rb_next(&right_es->rb_node); 1292 es = node ? rb_entry(node, struct extent_status, 1293 rb_node) : NULL; 1294 } 1295 while (es && es->es_lblk <= 1296 EXT4_LBLK_CFILL(sbi, rc->last_do_lblk)) { 1297 if (ext4_es_is_delonly(es)) { 1298 rc->ndelonly--; 1299 right_delonly = true; 1300 break; 1301 } 1302 node = rb_next(&es->rb_node); 1303 if (!node) 1304 break; 1305 es = rb_entry(node, struct extent_status, 1306 rb_node); 1307 } 1308 } 1309 1310 /* 1311 * Determine the block range that should be searched for 1312 * pending reservations, if any. Clusters on the ends of the 1313 * original removed range containing delonly blocks are 1314 * excluded. They've already been accounted for and it's not 1315 * possible to determine if an associated pending reservation 1316 * should be released with the information available in the 1317 * extents status tree. 1318 */ 1319 if (first_lclu == last_lclu) { 1320 if (left_delonly | right_delonly) 1321 count_pending = false; 1322 else 1323 count_pending = true; 1324 } else { 1325 if (left_delonly) 1326 first_lclu++; 1327 if (right_delonly) 1328 last_lclu--; 1329 if (first_lclu <= last_lclu) 1330 count_pending = true; 1331 else 1332 count_pending = false; 1333 } 1334 1335 /* 1336 * a pending reservation found between first_lclu and last_lclu 1337 * represents an allocated cluster that contained at least one 1338 * delonly block, so the delonly total must be reduced by one 1339 * for each pending reservation found and released 1340 */ 1341 if (count_pending) { 1342 pr = __pr_tree_search(&tree->root, first_lclu); 1343 while (pr && pr->lclu <= last_lclu) { 1344 rc->ndelonly--; 1345 node = rb_next(&pr->rb_node); 1346 rb_erase(&pr->rb_node, &tree->root); 1347 __free_pending(pr); 1348 if (!node) 1349 break; 1350 pr = rb_entry(node, struct pending_reservation, 1351 rb_node); 1352 } 1353 } 1354 } 1355 return rc->ndelonly; 1356} 1357 1358 1359/* 1360 * __es_remove_extent - removes block range from extent status tree 1361 * 1362 * @inode - file containing range 1363 * @lblk - first block in range 1364 * @end - last block in range 1365 * @reserved - number of cluster reservations released 1366 * @prealloc - pre-allocated es to avoid memory allocation failures 1367 * 1368 * If @reserved is not NULL and delayed allocation is enabled, counts 1369 * block/cluster reservations freed by removing range and if bigalloc 1370 * enabled cancels pending reservations as needed. Returns 0 on success, 1371 * error code on failure. 1372 */ 1373static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk, 1374 ext4_lblk_t end, int *reserved, 1375 struct extent_status *prealloc) 1376{ 1377 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree; 1378 struct rb_node *node; 1379 struct extent_status *es; 1380 struct extent_status orig_es; 1381 ext4_lblk_t len1, len2; 1382 ext4_fsblk_t block; 1383 int err = 0; 1384 bool count_reserved = true; 1385 struct rsvd_count rc; 1386 1387 if (reserved == NULL || !test_opt(inode->i_sb, DELALLOC)) 1388 count_reserved = false; 1389 1390 es = __es_tree_search(&tree->root, lblk); 1391 if (!es) 1392 goto out; 1393 if (es->es_lblk > end) 1394 goto out; 1395 1396 /* Simply invalidate cache_es. */ 1397 tree->cache_es = NULL; 1398 if (count_reserved) 1399 init_rsvd(inode, lblk, es, &rc); 1400 1401 orig_es.es_lblk = es->es_lblk; 1402 orig_es.es_len = es->es_len; 1403 orig_es.es_pblk = es->es_pblk; 1404 1405 len1 = lblk > es->es_lblk ? lblk - es->es_lblk : 0; 1406 len2 = ext4_es_end(es) > end ? ext4_es_end(es) - end : 0; 1407 if (len1 > 0) 1408 es->es_len = len1; 1409 if (len2 > 0) { 1410 if (len1 > 0) { 1411 struct extent_status newes; 1412 1413 newes.es_lblk = end + 1; 1414 newes.es_len = len2; 1415 block = 0x7FDEADBEEFULL; 1416 if (ext4_es_is_written(&orig_es) || 1417 ext4_es_is_unwritten(&orig_es)) 1418 block = ext4_es_pblock(&orig_es) + 1419 orig_es.es_len - len2; 1420 ext4_es_store_pblock_status(&newes, block, 1421 ext4_es_status(&orig_es)); 1422 err = __es_insert_extent(inode, &newes, prealloc); 1423 if (err) { 1424 if (!ext4_es_must_keep(&newes)) 1425 return 0; 1426 1427 es->es_lblk = orig_es.es_lblk; 1428 es->es_len = orig_es.es_len; 1429 goto out; 1430 } 1431 } else { 1432 es->es_lblk = end + 1; 1433 es->es_len = len2; 1434 if (ext4_es_is_written(es) || 1435 ext4_es_is_unwritten(es)) { 1436 block = orig_es.es_pblk + orig_es.es_len - len2; 1437 ext4_es_store_pblock(es, block); 1438 } 1439 } 1440 if (count_reserved) 1441 count_rsvd(inode, orig_es.es_lblk + len1, 1442 orig_es.es_len - len1 - len2, &orig_es, &rc); 1443 goto out_get_reserved; 1444 } 1445 1446 if (len1 > 0) { 1447 if (count_reserved) 1448 count_rsvd(inode, lblk, orig_es.es_len - len1, 1449 &orig_es, &rc); 1450 node = rb_next(&es->rb_node); 1451 if (node) 1452 es = rb_entry(node, struct extent_status, rb_node); 1453 else 1454 es = NULL; 1455 } 1456 1457 while (es && ext4_es_end(es) <= end) { 1458 if (count_reserved) 1459 count_rsvd(inode, es->es_lblk, es->es_len, es, &rc); 1460 node = rb_next(&es->rb_node); 1461 rb_erase(&es->rb_node, &tree->root); 1462 ext4_es_free_extent(inode, es); 1463 if (!node) { 1464 es = NULL; 1465 break; 1466 } 1467 es = rb_entry(node, struct extent_status, rb_node); 1468 } 1469 1470 if (es && es->es_lblk < end + 1) { 1471 ext4_lblk_t orig_len = es->es_len; 1472 1473 len1 = ext4_es_end(es) - end; 1474 if (count_reserved) 1475 count_rsvd(inode, es->es_lblk, orig_len - len1, 1476 es, &rc); 1477 es->es_lblk = end + 1; 1478 es->es_len = len1; 1479 if (ext4_es_is_written(es) || ext4_es_is_unwritten(es)) { 1480 block = es->es_pblk + orig_len - len1; 1481 ext4_es_store_pblock(es, block); 1482 } 1483 } 1484 1485out_get_reserved: 1486 if (count_reserved) 1487 *reserved = get_rsvd(inode, end, es, &rc); 1488out: 1489 return err; 1490} 1491 1492/* 1493 * ext4_es_remove_extent - removes block range from extent status tree 1494 * 1495 * @inode - file containing range 1496 * @lblk - first block in range 1497 * @len - number of blocks to remove 1498 * 1499 * Reduces block/cluster reservation count and for bigalloc cancels pending 1500 * reservations as needed. Returns 0 on success, error code on failure. 1501 */ 1502int ext4_es_remove_extent(struct inode *inode, ext4_lblk_t lblk, 1503 ext4_lblk_t len) 1504{ 1505 ext4_lblk_t end; 1506 int err = 0; 1507 int reserved = 0; 1508 struct extent_status *es = NULL; 1509 1510 if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY) 1511 return 0; 1512 1513 trace_ext4_es_remove_extent(inode, lblk, len); 1514 es_debug("remove [%u/%u) from extent status tree of inode %lu\n", 1515 lblk, len, inode->i_ino); 1516 1517 if (!len) 1518 return err; 1519 1520 end = lblk + len - 1; 1521 BUG_ON(end < lblk); 1522 1523retry: 1524 if (err && !es) 1525 es = __es_alloc_extent(true); 1526 /* 1527 * ext4_clear_inode() depends on us taking i_es_lock unconditionally 1528 * so that we are sure __es_shrink() is done with the inode before it 1529 * is reclaimed. 1530 */ 1531 write_lock(&EXT4_I(inode)->i_es_lock); 1532 err = __es_remove_extent(inode, lblk, end, &reserved, es); 1533 /* Free preallocated extent if it didn't get used. */ 1534 if (es) { 1535 if (!es->es_len) 1536 __es_free_extent(es); 1537 es = NULL; 1538 } 1539 write_unlock(&EXT4_I(inode)->i_es_lock); 1540 if (err) 1541 goto retry; 1542 1543 ext4_es_print_tree(inode); 1544 ext4_da_release_space(inode, reserved); 1545 return 0; 1546} 1547 1548static int __es_shrink(struct ext4_sb_info *sbi, int nr_to_scan, 1549 struct ext4_inode_info *locked_ei) 1550{ 1551 struct ext4_inode_info *ei; 1552 struct ext4_es_stats *es_stats; 1553 ktime_t start_time; 1554 u64 scan_time; 1555 int nr_to_walk; 1556 int nr_shrunk = 0; 1557 int retried = 0, nr_skipped = 0; 1558 1559 es_stats = &sbi->s_es_stats; 1560 start_time = ktime_get(); 1561 1562retry: 1563 spin_lock(&sbi->s_es_lock); 1564 nr_to_walk = sbi->s_es_nr_inode; 1565 while (nr_to_walk-- > 0) { 1566 if (list_empty(&sbi->s_es_list)) { 1567 spin_unlock(&sbi->s_es_lock); 1568 goto out; 1569 } 1570 ei = list_first_entry(&sbi->s_es_list, struct ext4_inode_info, 1571 i_es_list); 1572 /* Move the inode to the tail */ 1573 list_move_tail(&ei->i_es_list, &sbi->s_es_list); 1574 1575 /* 1576 * Normally we try hard to avoid shrinking precached inodes, 1577 * but we will as a last resort. 1578 */ 1579 if (!retried && ext4_test_inode_state(&ei->vfs_inode, 1580 EXT4_STATE_EXT_PRECACHED)) { 1581 nr_skipped++; 1582 continue; 1583 } 1584 1585 if (ei == locked_ei || !write_trylock(&ei->i_es_lock)) { 1586 nr_skipped++; 1587 continue; 1588 } 1589 /* 1590 * Now we hold i_es_lock which protects us from inode reclaim 1591 * freeing inode under us 1592 */ 1593 spin_unlock(&sbi->s_es_lock); 1594 1595 nr_shrunk += es_reclaim_extents(ei, &nr_to_scan); 1596 write_unlock(&ei->i_es_lock); 1597 1598 if (nr_to_scan <= 0) 1599 goto out; 1600 spin_lock(&sbi->s_es_lock); 1601 } 1602 spin_unlock(&sbi->s_es_lock); 1603 1604 /* 1605 * If we skipped any inodes, and we weren't able to make any 1606 * forward progress, try again to scan precached inodes. 1607 */ 1608 if ((nr_shrunk == 0) && nr_skipped && !retried) { 1609 retried++; 1610 goto retry; 1611 } 1612 1613 if (locked_ei && nr_shrunk == 0) 1614 nr_shrunk = es_reclaim_extents(locked_ei, &nr_to_scan); 1615 1616out: 1617 scan_time = ktime_to_ns(ktime_sub(ktime_get(), start_time)); 1618 if (likely(es_stats->es_stats_scan_time)) 1619 es_stats->es_stats_scan_time = (scan_time + 1620 es_stats->es_stats_scan_time*3) / 4; 1621 else 1622 es_stats->es_stats_scan_time = scan_time; 1623 if (scan_time > es_stats->es_stats_max_scan_time) 1624 es_stats->es_stats_max_scan_time = scan_time; 1625 if (likely(es_stats->es_stats_shrunk)) 1626 es_stats->es_stats_shrunk = (nr_shrunk + 1627 es_stats->es_stats_shrunk*3) / 4; 1628 else 1629 es_stats->es_stats_shrunk = nr_shrunk; 1630 1631 trace_ext4_es_shrink(sbi->s_sb, nr_shrunk, scan_time, 1632 nr_skipped, retried); 1633 return nr_shrunk; 1634} 1635 1636static unsigned long ext4_es_count(struct shrinker *shrink, 1637 struct shrink_control *sc) 1638{ 1639 unsigned long nr; 1640 struct ext4_sb_info *sbi; 1641 1642 sbi = container_of(shrink, struct ext4_sb_info, s_es_shrinker); 1643 nr = percpu_counter_read_positive(&sbi->s_es_stats.es_stats_shk_cnt); 1644 trace_ext4_es_shrink_count(sbi->s_sb, sc->nr_to_scan, nr); 1645 return nr; 1646} 1647 1648static unsigned long ext4_es_scan(struct shrinker *shrink, 1649 struct shrink_control *sc) 1650{ 1651 struct ext4_sb_info *sbi = container_of(shrink, 1652 struct ext4_sb_info, s_es_shrinker); 1653 int nr_to_scan = sc->nr_to_scan; 1654 int ret, nr_shrunk; 1655 1656 ret = percpu_counter_read_positive(&sbi->s_es_stats.es_stats_shk_cnt); 1657 trace_ext4_es_shrink_scan_enter(sbi->s_sb, nr_to_scan, ret); 1658 1659 nr_shrunk = __es_shrink(sbi, nr_to_scan, NULL); 1660 1661 ret = percpu_counter_read_positive(&sbi->s_es_stats.es_stats_shk_cnt); 1662 trace_ext4_es_shrink_scan_exit(sbi->s_sb, nr_shrunk, ret); 1663 return nr_shrunk; 1664} 1665 1666int ext4_seq_es_shrinker_info_show(struct seq_file *seq, void *v) 1667{ 1668 struct ext4_sb_info *sbi = EXT4_SB((struct super_block *) seq->private); 1669 struct ext4_es_stats *es_stats = &sbi->s_es_stats; 1670 struct ext4_inode_info *ei, *max = NULL; 1671 unsigned int inode_cnt = 0; 1672 1673 if (v != SEQ_START_TOKEN) 1674 return 0; 1675 1676 /* here we just find an inode that has the max nr. of objects */ 1677 spin_lock(&sbi->s_es_lock); 1678 list_for_each_entry(ei, &sbi->s_es_list, i_es_list) { 1679 inode_cnt++; 1680 if (max && max->i_es_all_nr < ei->i_es_all_nr) 1681 max = ei; 1682 else if (!max) 1683 max = ei; 1684 } 1685 spin_unlock(&sbi->s_es_lock); 1686 1687 seq_printf(seq, "stats:\n %lld objects\n %lld reclaimable objects\n", 1688 percpu_counter_sum_positive(&es_stats->es_stats_all_cnt), 1689 percpu_counter_sum_positive(&es_stats->es_stats_shk_cnt)); 1690 seq_printf(seq, " %lld/%lld cache hits/misses\n", 1691 percpu_counter_sum_positive(&es_stats->es_stats_cache_hits), 1692 percpu_counter_sum_positive(&es_stats->es_stats_cache_misses)); 1693 if (inode_cnt) 1694 seq_printf(seq, " %d inodes on list\n", inode_cnt); 1695 1696 seq_printf(seq, "average:\n %llu us scan time\n", 1697 div_u64(es_stats->es_stats_scan_time, 1000)); 1698 seq_printf(seq, " %lu shrunk objects\n", es_stats->es_stats_shrunk); 1699 if (inode_cnt) 1700 seq_printf(seq, 1701 "maximum:\n %lu inode (%u objects, %u reclaimable)\n" 1702 " %llu us max scan time\n", 1703 max->vfs_inode.i_ino, max->i_es_all_nr, max->i_es_shk_nr, 1704 div_u64(es_stats->es_stats_max_scan_time, 1000)); 1705 1706 return 0; 1707} 1708 1709int ext4_es_register_shrinker(struct ext4_sb_info *sbi) 1710{ 1711 int err; 1712 1713 /* Make sure we have enough bits for physical block number */ 1714 BUILD_BUG_ON(ES_SHIFT < 48); 1715 INIT_LIST_HEAD(&sbi->s_es_list); 1716 sbi->s_es_nr_inode = 0; 1717 spin_lock_init(&sbi->s_es_lock); 1718 sbi->s_es_stats.es_stats_shrunk = 0; 1719 err = percpu_counter_init(&sbi->s_es_stats.es_stats_cache_hits, 0, 1720 GFP_KERNEL); 1721 if (err) 1722 return err; 1723 err = percpu_counter_init(&sbi->s_es_stats.es_stats_cache_misses, 0, 1724 GFP_KERNEL); 1725 if (err) 1726 goto err1; 1727 sbi->s_es_stats.es_stats_scan_time = 0; 1728 sbi->s_es_stats.es_stats_max_scan_time = 0; 1729 err = percpu_counter_init(&sbi->s_es_stats.es_stats_all_cnt, 0, GFP_KERNEL); 1730 if (err) 1731 goto err2; 1732 err = percpu_counter_init(&sbi->s_es_stats.es_stats_shk_cnt, 0, GFP_KERNEL); 1733 if (err) 1734 goto err3; 1735 1736 sbi->s_es_shrinker.scan_objects = ext4_es_scan; 1737 sbi->s_es_shrinker.count_objects = ext4_es_count; 1738 sbi->s_es_shrinker.seeks = DEFAULT_SEEKS; 1739 err = register_shrinker(&sbi->s_es_shrinker); 1740 if (err) 1741 goto err4; 1742 1743 return 0; 1744err4: 1745 percpu_counter_destroy(&sbi->s_es_stats.es_stats_shk_cnt); 1746err3: 1747 percpu_counter_destroy(&sbi->s_es_stats.es_stats_all_cnt); 1748err2: 1749 percpu_counter_destroy(&sbi->s_es_stats.es_stats_cache_misses); 1750err1: 1751 percpu_counter_destroy(&sbi->s_es_stats.es_stats_cache_hits); 1752 return err; 1753} 1754 1755void ext4_es_unregister_shrinker(struct ext4_sb_info *sbi) 1756{ 1757 percpu_counter_destroy(&sbi->s_es_stats.es_stats_cache_hits); 1758 percpu_counter_destroy(&sbi->s_es_stats.es_stats_cache_misses); 1759 percpu_counter_destroy(&sbi->s_es_stats.es_stats_all_cnt); 1760 percpu_counter_destroy(&sbi->s_es_stats.es_stats_shk_cnt); 1761 unregister_shrinker(&sbi->s_es_shrinker); 1762} 1763 1764/* 1765 * Shrink extents in given inode from ei->i_es_shrink_lblk till end. Scan at 1766 * most *nr_to_scan extents, update *nr_to_scan accordingly. 1767 * 1768 * Return 0 if we hit end of tree / interval, 1 if we exhausted nr_to_scan. 1769 * Increment *nr_shrunk by the number of reclaimed extents. Also update 1770 * ei->i_es_shrink_lblk to where we should continue scanning. 1771 */ 1772static int es_do_reclaim_extents(struct ext4_inode_info *ei, ext4_lblk_t end, 1773 int *nr_to_scan, int *nr_shrunk) 1774{ 1775 struct inode *inode = &ei->vfs_inode; 1776 struct ext4_es_tree *tree = &ei->i_es_tree; 1777 struct extent_status *es; 1778 struct rb_node *node; 1779 1780 es = __es_tree_search(&tree->root, ei->i_es_shrink_lblk); 1781 if (!es) 1782 goto out_wrap; 1783 1784 while (*nr_to_scan > 0) { 1785 if (es->es_lblk > end) { 1786 ei->i_es_shrink_lblk = end + 1; 1787 return 0; 1788 } 1789 1790 (*nr_to_scan)--; 1791 node = rb_next(&es->rb_node); 1792 1793 if (ext4_es_must_keep(es)) 1794 goto next; 1795 if (ext4_es_is_referenced(es)) { 1796 ext4_es_clear_referenced(es); 1797 goto next; 1798 } 1799 1800 rb_erase(&es->rb_node, &tree->root); 1801 ext4_es_free_extent(inode, es); 1802 (*nr_shrunk)++; 1803next: 1804 if (!node) 1805 goto out_wrap; 1806 es = rb_entry(node, struct extent_status, rb_node); 1807 } 1808 ei->i_es_shrink_lblk = es->es_lblk; 1809 return 1; 1810out_wrap: 1811 ei->i_es_shrink_lblk = 0; 1812 return 0; 1813} 1814 1815static int es_reclaim_extents(struct ext4_inode_info *ei, int *nr_to_scan) 1816{ 1817 struct inode *inode = &ei->vfs_inode; 1818 int nr_shrunk = 0; 1819 ext4_lblk_t start = ei->i_es_shrink_lblk; 1820 static DEFINE_RATELIMIT_STATE(_rs, DEFAULT_RATELIMIT_INTERVAL, 1821 DEFAULT_RATELIMIT_BURST); 1822 1823 if (ei->i_es_shk_nr == 0) 1824 return 0; 1825 1826 if (ext4_test_inode_state(inode, EXT4_STATE_EXT_PRECACHED) && 1827 __ratelimit(&_rs)) 1828 ext4_warning(inode->i_sb, "forced shrink of precached extents"); 1829 1830 if (!es_do_reclaim_extents(ei, EXT_MAX_BLOCKS, nr_to_scan, &nr_shrunk) && 1831 start != 0) 1832 es_do_reclaim_extents(ei, start - 1, nr_to_scan, &nr_shrunk); 1833 1834 ei->i_es_tree.cache_es = NULL; 1835 return nr_shrunk; 1836} 1837 1838/* 1839 * Called to support EXT4_IOC_CLEAR_ES_CACHE. We can only remove 1840 * discretionary entries from the extent status cache. (Some entries 1841 * must be present for proper operations.) 1842 */ 1843void ext4_clear_inode_es(struct inode *inode) 1844{ 1845 struct ext4_inode_info *ei = EXT4_I(inode); 1846 struct extent_status *es; 1847 struct ext4_es_tree *tree; 1848 struct rb_node *node; 1849 1850 write_lock(&ei->i_es_lock); 1851 tree = &EXT4_I(inode)->i_es_tree; 1852 tree->cache_es = NULL; 1853 node = rb_first(&tree->root); 1854 while (node) { 1855 es = rb_entry(node, struct extent_status, rb_node); 1856 node = rb_next(node); 1857 if (!ext4_es_must_keep(es)) { 1858 rb_erase(&es->rb_node, &tree->root); 1859 ext4_es_free_extent(inode, es); 1860 } 1861 } 1862 ext4_clear_inode_state(inode, EXT4_STATE_EXT_PRECACHED); 1863 write_unlock(&ei->i_es_lock); 1864} 1865 1866#ifdef ES_DEBUG__ 1867static void ext4_print_pending_tree(struct inode *inode) 1868{ 1869 struct ext4_pending_tree *tree; 1870 struct rb_node *node; 1871 struct pending_reservation *pr; 1872 1873 printk(KERN_DEBUG "pending reservations for inode %lu:", inode->i_ino); 1874 tree = &EXT4_I(inode)->i_pending_tree; 1875 node = rb_first(&tree->root); 1876 while (node) { 1877 pr = rb_entry(node, struct pending_reservation, rb_node); 1878 printk(KERN_DEBUG " %u", pr->lclu); 1879 node = rb_next(node); 1880 } 1881 printk(KERN_DEBUG "\n"); 1882} 1883#else 1884#define ext4_print_pending_tree(inode) 1885#endif 1886 1887int __init ext4_init_pending(void) 1888{ 1889 ext4_pending_cachep = kmem_cache_create("ext4_pending_reservation", 1890 sizeof(struct pending_reservation), 1891 0, (SLAB_RECLAIM_ACCOUNT), NULL); 1892 if (ext4_pending_cachep == NULL) 1893 return -ENOMEM; 1894 return 0; 1895} 1896 1897void ext4_exit_pending(void) 1898{ 1899 kmem_cache_destroy(ext4_pending_cachep); 1900} 1901 1902void ext4_init_pending_tree(struct ext4_pending_tree *tree) 1903{ 1904 tree->root = RB_ROOT; 1905} 1906 1907/* 1908 * __get_pending - retrieve a pointer to a pending reservation 1909 * 1910 * @inode - file containing the pending cluster reservation 1911 * @lclu - logical cluster of interest 1912 * 1913 * Returns a pointer to a pending reservation if it's a member of 1914 * the set, and NULL if not. Must be called holding i_es_lock. 1915 */ 1916static struct pending_reservation *__get_pending(struct inode *inode, 1917 ext4_lblk_t lclu) 1918{ 1919 struct ext4_pending_tree *tree; 1920 struct rb_node *node; 1921 struct pending_reservation *pr = NULL; 1922 1923 tree = &EXT4_I(inode)->i_pending_tree; 1924 node = (&tree->root)->rb_node; 1925 1926 while (node) { 1927 pr = rb_entry(node, struct pending_reservation, rb_node); 1928 if (lclu < pr->lclu) 1929 node = node->rb_left; 1930 else if (lclu > pr->lclu) 1931 node = node->rb_right; 1932 else if (lclu == pr->lclu) 1933 return pr; 1934 } 1935 return NULL; 1936} 1937 1938/* 1939 * __insert_pending - adds a pending cluster reservation to the set of 1940 * pending reservations 1941 * 1942 * @inode - file containing the cluster 1943 * @lblk - logical block in the cluster to be added 1944 * @prealloc - preallocated pending entry 1945 * 1946 * Returns 0 on successful insertion and -ENOMEM on failure. If the 1947 * pending reservation is already in the set, returns successfully. 1948 */ 1949static int __insert_pending(struct inode *inode, ext4_lblk_t lblk, 1950 struct pending_reservation **prealloc) 1951{ 1952 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb); 1953 struct ext4_pending_tree *tree = &EXT4_I(inode)->i_pending_tree; 1954 struct rb_node **p = &tree->root.rb_node; 1955 struct rb_node *parent = NULL; 1956 struct pending_reservation *pr; 1957 ext4_lblk_t lclu; 1958 int ret = 0; 1959 1960 lclu = EXT4_B2C(sbi, lblk); 1961 /* search to find parent for insertion */ 1962 while (*p) { 1963 parent = *p; 1964 pr = rb_entry(parent, struct pending_reservation, rb_node); 1965 1966 if (lclu < pr->lclu) { 1967 p = &(*p)->rb_left; 1968 } else if (lclu > pr->lclu) { 1969 p = &(*p)->rb_right; 1970 } else { 1971 /* pending reservation already inserted */ 1972 goto out; 1973 } 1974 } 1975 1976 if (likely(*prealloc == NULL)) { 1977 pr = __alloc_pending(false); 1978 if (!pr) { 1979 ret = -ENOMEM; 1980 goto out; 1981 } 1982 } else { 1983 pr = *prealloc; 1984 *prealloc = NULL; 1985 } 1986 pr->lclu = lclu; 1987 1988 rb_link_node(&pr->rb_node, parent, p); 1989 rb_insert_color(&pr->rb_node, &tree->root); 1990 1991out: 1992 return ret; 1993} 1994 1995/* 1996 * __remove_pending - removes a pending cluster reservation from the set 1997 * of pending reservations 1998 * 1999 * @inode - file containing the cluster 2000 * @lblk - logical block in the pending cluster reservation to be removed 2001 * 2002 * Returns successfully if pending reservation is not a member of the set. 2003 */ 2004static void __remove_pending(struct inode *inode, ext4_lblk_t lblk) 2005{ 2006 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb); 2007 struct pending_reservation *pr; 2008 struct ext4_pending_tree *tree; 2009 2010 pr = __get_pending(inode, EXT4_B2C(sbi, lblk)); 2011 if (pr != NULL) { 2012 tree = &EXT4_I(inode)->i_pending_tree; 2013 rb_erase(&pr->rb_node, &tree->root); 2014 __free_pending(pr); 2015 } 2016} 2017 2018/* 2019 * ext4_remove_pending - removes a pending cluster reservation from the set 2020 * of pending reservations 2021 * 2022 * @inode - file containing the cluster 2023 * @lblk - logical block in the pending cluster reservation to be removed 2024 * 2025 * Locking for external use of __remove_pending. 2026 */ 2027void ext4_remove_pending(struct inode *inode, ext4_lblk_t lblk) 2028{ 2029 struct ext4_inode_info *ei = EXT4_I(inode); 2030 2031 write_lock(&ei->i_es_lock); 2032 __remove_pending(inode, lblk); 2033 write_unlock(&ei->i_es_lock); 2034} 2035 2036/* 2037 * ext4_is_pending - determine whether a cluster has a pending reservation 2038 * on it 2039 * 2040 * @inode - file containing the cluster 2041 * @lblk - logical block in the cluster 2042 * 2043 * Returns true if there's a pending reservation for the cluster in the 2044 * set of pending reservations, and false if not. 2045 */ 2046bool ext4_is_pending(struct inode *inode, ext4_lblk_t lblk) 2047{ 2048 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb); 2049 struct ext4_inode_info *ei = EXT4_I(inode); 2050 bool ret; 2051 2052 read_lock(&ei->i_es_lock); 2053 ret = (bool)(__get_pending(inode, EXT4_B2C(sbi, lblk)) != NULL); 2054 read_unlock(&ei->i_es_lock); 2055 2056 return ret; 2057} 2058 2059/* 2060 * ext4_es_insert_delayed_block - adds a delayed block to the extents status 2061 * tree, adding a pending reservation where 2062 * needed 2063 * 2064 * @inode - file containing the newly added block 2065 * @lblk - logical block to be added 2066 * @allocated - indicates whether a physical cluster has been allocated for 2067 * the logical cluster that contains the block 2068 * 2069 * Returns 0 on success, negative error code on failure. 2070 */ 2071int ext4_es_insert_delayed_block(struct inode *inode, ext4_lblk_t lblk, 2072 bool allocated) 2073{ 2074 struct extent_status newes; 2075 int err1 = 0, err2 = 0, err3 = 0; 2076 struct extent_status *es1 = NULL; 2077 struct extent_status *es2 = NULL; 2078 struct pending_reservation *pr = NULL; 2079 2080 if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY) 2081 return 0; 2082 2083 es_debug("add [%u/1) delayed to extent status tree of inode %lu\n", 2084 lblk, inode->i_ino); 2085 2086 newes.es_lblk = lblk; 2087 newes.es_len = 1; 2088 ext4_es_store_pblock_status(&newes, ~0, EXTENT_STATUS_DELAYED); 2089 trace_ext4_es_insert_delayed_block(inode, &newes, allocated); 2090 2091 ext4_es_insert_extent_check(inode, &newes); 2092 2093retry: 2094 if (err1 && !es1) 2095 es1 = __es_alloc_extent(true); 2096 if ((err1 || err2) && !es2) 2097 es2 = __es_alloc_extent(true); 2098 if ((err1 || err2 || err3) && allocated && !pr) 2099 pr = __alloc_pending(true); 2100 write_lock(&EXT4_I(inode)->i_es_lock); 2101 2102 err1 = __es_remove_extent(inode, lblk, lblk, NULL, es1); 2103 if (err1 != 0) 2104 goto error; 2105 /* Free preallocated extent if it didn't get used. */ 2106 if (es1) { 2107 if (!es1->es_len) 2108 __es_free_extent(es1); 2109 es1 = NULL; 2110 } 2111 2112 err2 = __es_insert_extent(inode, &newes, es2); 2113 if (err2 != 0) 2114 goto error; 2115 /* Free preallocated extent if it didn't get used. */ 2116 if (es2) { 2117 if (!es2->es_len) 2118 __es_free_extent(es2); 2119 es2 = NULL; 2120 } 2121 2122 if (allocated) { 2123 err3 = __insert_pending(inode, lblk, &pr); 2124 if (err3 != 0) 2125 goto error; 2126 if (pr) { 2127 __free_pending(pr); 2128 pr = NULL; 2129 } 2130 } 2131error: 2132 write_unlock(&EXT4_I(inode)->i_es_lock); 2133 if (err1 || err2 || err3) 2134 goto retry; 2135 2136 ext4_es_print_tree(inode); 2137 ext4_print_pending_tree(inode); 2138 return 0; 2139} 2140 2141/* 2142 * __es_delayed_clu - count number of clusters containing blocks that 2143 * are delayed only 2144 * 2145 * @inode - file containing block range 2146 * @start - logical block defining start of range 2147 * @end - logical block defining end of range 2148 * 2149 * Returns the number of clusters containing only delayed (not delayed 2150 * and unwritten) blocks in the range specified by @start and @end. Any 2151 * cluster or part of a cluster within the range and containing a delayed 2152 * and not unwritten block within the range is counted as a whole cluster. 2153 */ 2154static unsigned int __es_delayed_clu(struct inode *inode, ext4_lblk_t start, 2155 ext4_lblk_t end) 2156{ 2157 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree; 2158 struct extent_status *es; 2159 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb); 2160 struct rb_node *node; 2161 ext4_lblk_t first_lclu, last_lclu; 2162 unsigned long long last_counted_lclu; 2163 unsigned int n = 0; 2164 2165 /* guaranteed to be unequal to any ext4_lblk_t value */ 2166 last_counted_lclu = ~0ULL; 2167 2168 es = __es_tree_search(&tree->root, start); 2169 2170 while (es && (es->es_lblk <= end)) { 2171 if (ext4_es_is_delonly(es)) { 2172 if (es->es_lblk <= start) 2173 first_lclu = EXT4_B2C(sbi, start); 2174 else 2175 first_lclu = EXT4_B2C(sbi, es->es_lblk); 2176 2177 if (ext4_es_end(es) >= end) 2178 last_lclu = EXT4_B2C(sbi, end); 2179 else 2180 last_lclu = EXT4_B2C(sbi, ext4_es_end(es)); 2181 2182 if (first_lclu == last_counted_lclu) 2183 n += last_lclu - first_lclu; 2184 else 2185 n += last_lclu - first_lclu + 1; 2186 last_counted_lclu = last_lclu; 2187 } 2188 node = rb_next(&es->rb_node); 2189 if (!node) 2190 break; 2191 es = rb_entry(node, struct extent_status, rb_node); 2192 } 2193 2194 return n; 2195} 2196 2197/* 2198 * ext4_es_delayed_clu - count number of clusters containing blocks that 2199 * are both delayed and unwritten 2200 * 2201 * @inode - file containing block range 2202 * @lblk - logical block defining start of range 2203 * @len - number of blocks in range 2204 * 2205 * Locking for external use of __es_delayed_clu(). 2206 */ 2207unsigned int ext4_es_delayed_clu(struct inode *inode, ext4_lblk_t lblk, 2208 ext4_lblk_t len) 2209{ 2210 struct ext4_inode_info *ei = EXT4_I(inode); 2211 ext4_lblk_t end; 2212 unsigned int n; 2213 2214 if (len == 0) 2215 return 0; 2216 2217 end = lblk + len - 1; 2218 WARN_ON(end < lblk); 2219 2220 read_lock(&ei->i_es_lock); 2221 2222 n = __es_delayed_clu(inode, lblk, end); 2223 2224 read_unlock(&ei->i_es_lock); 2225 2226 return n; 2227} 2228 2229/* 2230 * __revise_pending - makes, cancels, or leaves unchanged pending cluster 2231 * reservations for a specified block range depending 2232 * upon the presence or absence of delayed blocks 2233 * outside the range within clusters at the ends of the 2234 * range 2235 * 2236 * @inode - file containing the range 2237 * @lblk - logical block defining the start of range 2238 * @len - length of range in blocks 2239 * @prealloc - preallocated pending entry 2240 * 2241 * Used after a newly allocated extent is added to the extents status tree. 2242 * Requires that the extents in the range have either written or unwritten 2243 * status. Must be called while holding i_es_lock. 2244 */ 2245static int __revise_pending(struct inode *inode, ext4_lblk_t lblk, 2246 ext4_lblk_t len, 2247 struct pending_reservation **prealloc) 2248{ 2249 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb); 2250 ext4_lblk_t end = lblk + len - 1; 2251 ext4_lblk_t first, last; 2252 bool f_del = false, l_del = false; 2253 int ret = 0; 2254 2255 if (len == 0) 2256 return 0; 2257 2258 /* 2259 * Two cases - block range within single cluster and block range 2260 * spanning two or more clusters. Note that a cluster belonging 2261 * to a range starting and/or ending on a cluster boundary is treated 2262 * as if it does not contain a delayed extent. The new range may 2263 * have allocated space for previously delayed blocks out to the 2264 * cluster boundary, requiring that any pre-existing pending 2265 * reservation be canceled. Because this code only looks at blocks 2266 * outside the range, it should revise pending reservations 2267 * correctly even if the extent represented by the range can't be 2268 * inserted in the extents status tree due to ENOSPC. 2269 */ 2270 2271 if (EXT4_B2C(sbi, lblk) == EXT4_B2C(sbi, end)) { 2272 first = EXT4_LBLK_CMASK(sbi, lblk); 2273 if (first != lblk) 2274 f_del = __es_scan_range(inode, &ext4_es_is_delonly, 2275 first, lblk - 1); 2276 if (f_del) { 2277 ret = __insert_pending(inode, first, prealloc); 2278 if (ret < 0) 2279 goto out; 2280 } else { 2281 last = EXT4_LBLK_CMASK(sbi, end) + 2282 sbi->s_cluster_ratio - 1; 2283 if (last != end) 2284 l_del = __es_scan_range(inode, 2285 &ext4_es_is_delonly, 2286 end + 1, last); 2287 if (l_del) { 2288 ret = __insert_pending(inode, last, prealloc); 2289 if (ret < 0) 2290 goto out; 2291 } else 2292 __remove_pending(inode, last); 2293 } 2294 } else { 2295 first = EXT4_LBLK_CMASK(sbi, lblk); 2296 if (first != lblk) 2297 f_del = __es_scan_range(inode, &ext4_es_is_delonly, 2298 first, lblk - 1); 2299 if (f_del) { 2300 ret = __insert_pending(inode, first, prealloc); 2301 if (ret < 0) 2302 goto out; 2303 } else 2304 __remove_pending(inode, first); 2305 2306 last = EXT4_LBLK_CMASK(sbi, end) + sbi->s_cluster_ratio - 1; 2307 if (last != end) 2308 l_del = __es_scan_range(inode, &ext4_es_is_delonly, 2309 end + 1, last); 2310 if (l_del) { 2311 ret = __insert_pending(inode, last, prealloc); 2312 if (ret < 0) 2313 goto out; 2314 } else 2315 __remove_pending(inode, last); 2316 } 2317out: 2318 return ret; 2319} 2320