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