1 /* 2 * fs/ext4/extents_status.c 3 * 4 * Written by Yongqiang Yang <xiaoqiangnk@gmail.com> 5 * Modified by 6 * Allison Henderson <achender@linux.vnet.ibm.com> 7 * Hugh Dickins <hughd@google.com> 8 * Zheng Liu <wenqing.lz@taobao.com> 9 * 10 * Ext4 extents status tree core functions. 11 */ 12 #include <linux/rbtree.h> 13 #include "ext4.h" 14 #include "extents_status.h" 15 #include "ext4_extents.h" 16 17 #include <trace/events/ext4.h> 18 19 /* 20 * According to previous discussion in Ext4 Developer Workshop, we 21 * will introduce a new structure called io tree to track all extent 22 * status in order to solve some problems that we have met 23 * (e.g. Reservation space warning), and provide extent-level locking. 24 * Delay extent tree is the first step to achieve this goal. It is 25 * original built by Yongqiang Yang. At that time it is called delay 26 * extent tree, whose goal is only track delayed extents in memory to 27 * simplify the implementation of fiemap and bigalloc, and introduce 28 * lseek SEEK_DATA/SEEK_HOLE support. That is why it is still called 29 * delay extent tree at the first commit. But for better understand 30 * what it does, it has been rename to extent status tree. 31 * 32 * Step1: 33 * Currently the first step has been done. All delayed extents are 34 * tracked in the tree. It maintains the delayed extent when a delayed 35 * allocation is issued, and the delayed extent is written out or 36 * invalidated. Therefore the implementation of fiemap and bigalloc 37 * are simplified, and SEEK_DATA/SEEK_HOLE are introduced. 38 * 39 * The following comment describes the implemenmtation of extent 40 * status tree and future works. 41 * 42 * Step2: 43 * In this step all extent status are tracked by extent status tree. 44 * Thus, we can first try to lookup a block mapping in this tree before 45 * finding it in extent tree. Hence, single extent cache can be removed 46 * because extent status tree can do a better job. Extents in status 47 * tree are loaded on-demand. Therefore, the extent status tree may not 48 * contain all of the extents in a file. Meanwhile we define a shrinker 49 * to reclaim memory from extent status tree because fragmented extent 50 * tree will make status tree cost too much memory. written/unwritten/- 51 * hole extents in the tree will be reclaimed by this shrinker when we 52 * are under high memory pressure. Delayed extents will not be 53 * reclimed because fiemap, bigalloc, and seek_data/hole need it. 54 */ 55 56 /* 57 * Extent status tree implementation for ext4. 58 * 59 * 60 * ========================================================================== 61 * Extent status tree tracks all extent status. 62 * 63 * 1. Why we need to implement extent status tree? 64 * 65 * Without extent status tree, ext4 identifies a delayed extent by looking 66 * up page cache, this has several deficiencies - complicated, buggy, 67 * and inefficient code. 68 * 69 * FIEMAP, SEEK_HOLE/DATA, bigalloc, and writeout all need to know if a 70 * block or a range of blocks are belonged to a delayed extent. 71 * 72 * Let us have a look at how they do without extent status tree. 73 * -- FIEMAP 74 * FIEMAP looks up page cache to identify delayed allocations from holes. 75 * 76 * -- SEEK_HOLE/DATA 77 * SEEK_HOLE/DATA has the same problem as FIEMAP. 78 * 79 * -- bigalloc 80 * bigalloc looks up page cache to figure out if a block is 81 * already under delayed allocation or not to determine whether 82 * quota reserving is needed for the cluster. 83 * 84 * -- writeout 85 * Writeout looks up whole page cache to see if a buffer is 86 * mapped, If there are not very many delayed buffers, then it is 87 * time comsuming. 88 * 89 * With extent status tree implementation, FIEMAP, SEEK_HOLE/DATA, 90 * bigalloc and writeout can figure out if a block or a range of 91 * blocks is under delayed allocation(belonged to a delayed extent) or 92 * not by searching the extent tree. 93 * 94 * 95 * ========================================================================== 96 * 2. Ext4 extent status tree impelmentation 97 * 98 * -- extent 99 * A extent is a range of blocks which are contiguous logically and 100 * physically. Unlike extent in extent tree, this extent in ext4 is 101 * a in-memory struct, there is no corresponding on-disk data. There 102 * is no limit on length of extent, so an extent can contain as many 103 * blocks as they are contiguous logically and physically. 104 * 105 * -- extent status tree 106 * Every inode has an extent status tree and all allocation blocks 107 * are added to the tree with different status. The extent in the 108 * tree are ordered by logical block no. 109 * 110 * -- operations on a extent status tree 111 * There are three important operations on a delayed extent tree: find 112 * next extent, adding a extent(a range of blocks) and removing a extent. 113 * 114 * -- race on a extent status tree 115 * Extent status tree is protected by inode->i_es_lock. 116 * 117 * -- memory consumption 118 * Fragmented extent tree will make extent status tree cost too much 119 * memory. Hence, we will reclaim written/unwritten/hole extents from 120 * the tree under a heavy memory pressure. 121 * 122 * 123 * ========================================================================== 124 * 3. Performance analysis 125 * 126 * -- overhead 127 * 1. There is a cache extent for write access, so if writes are 128 * not very random, adding space operaions are in O(1) time. 129 * 130 * -- gain 131 * 2. Code is much simpler, more readable, more maintainable and 132 * more efficient. 133 * 134 * 135 * ========================================================================== 136 * 4. TODO list 137 * 138 * -- Refactor delayed space reservation 139 * 140 * -- Extent-level locking 141 */ 142 143 static struct kmem_cache *ext4_es_cachep; 144 145 static int __es_insert_extent(struct inode *inode, struct extent_status *newes); 146 static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk, 147 ext4_lblk_t end); 148 static int __es_try_to_reclaim_extents(struct ext4_inode_info *ei, 149 int nr_to_scan); 150 151 int __init ext4_init_es(void) 152 { 153 ext4_es_cachep = kmem_cache_create("ext4_extent_status", 154 sizeof(struct extent_status), 155 0, (SLAB_RECLAIM_ACCOUNT), NULL); 156 if (ext4_es_cachep == NULL) 157 return -ENOMEM; 158 return 0; 159 } 160 161 void ext4_exit_es(void) 162 { 163 if (ext4_es_cachep) 164 kmem_cache_destroy(ext4_es_cachep); 165 } 166 167 void ext4_es_init_tree(struct ext4_es_tree *tree) 168 { 169 tree->root = RB_ROOT; 170 tree->cache_es = NULL; 171 } 172 173 #ifdef ES_DEBUG__ 174 static void ext4_es_print_tree(struct inode *inode) 175 { 176 struct ext4_es_tree *tree; 177 struct rb_node *node; 178 179 printk(KERN_DEBUG "status extents for inode %lu:", inode->i_ino); 180 tree = &EXT4_I(inode)->i_es_tree; 181 node = rb_first(&tree->root); 182 while (node) { 183 struct extent_status *es; 184 es = rb_entry(node, struct extent_status, rb_node); 185 printk(KERN_DEBUG " [%u/%u) %llu %llx", 186 es->es_lblk, es->es_len, 187 ext4_es_pblock(es), ext4_es_status(es)); 188 node = rb_next(node); 189 } 190 printk(KERN_DEBUG "\n"); 191 } 192 #else 193 #define ext4_es_print_tree(inode) 194 #endif 195 196 static inline ext4_lblk_t ext4_es_end(struct extent_status *es) 197 { 198 BUG_ON(es->es_lblk + es->es_len < es->es_lblk); 199 return es->es_lblk + es->es_len - 1; 200 } 201 202 /* 203 * search through the tree for an delayed extent with a given offset. If 204 * it can't be found, try to find next extent. 205 */ 206 static struct extent_status *__es_tree_search(struct rb_root *root, 207 ext4_lblk_t lblk) 208 { 209 struct rb_node *node = root->rb_node; 210 struct extent_status *es = NULL; 211 212 while (node) { 213 es = rb_entry(node, struct extent_status, rb_node); 214 if (lblk < es->es_lblk) 215 node = node->rb_left; 216 else if (lblk > ext4_es_end(es)) 217 node = node->rb_right; 218 else 219 return es; 220 } 221 222 if (es && lblk < es->es_lblk) 223 return es; 224 225 if (es && lblk > ext4_es_end(es)) { 226 node = rb_next(&es->rb_node); 227 return node ? rb_entry(node, struct extent_status, rb_node) : 228 NULL; 229 } 230 231 return NULL; 232 } 233 234 /* 235 * ext4_es_find_delayed_extent: find the 1st delayed extent covering @es->lblk 236 * if it exists, otherwise, the next extent after @es->lblk. 237 * 238 * @inode: the inode which owns delayed extents 239 * @lblk: the offset where we start to search 240 * @es: delayed extent that we found 241 */ 242 void ext4_es_find_delayed_extent(struct inode *inode, ext4_lblk_t lblk, 243 struct extent_status *es) 244 { 245 struct ext4_es_tree *tree = NULL; 246 struct extent_status *es1 = NULL; 247 struct rb_node *node; 248 249 BUG_ON(es == NULL); 250 trace_ext4_es_find_delayed_extent_enter(inode, lblk); 251 252 read_lock(&EXT4_I(inode)->i_es_lock); 253 tree = &EXT4_I(inode)->i_es_tree; 254 255 /* find extent in cache firstly */ 256 es->es_lblk = es->es_len = es->es_pblk = 0; 257 if (tree->cache_es) { 258 es1 = tree->cache_es; 259 if (in_range(lblk, es1->es_lblk, es1->es_len)) { 260 es_debug("%u cached by [%u/%u) %llu %llx\n", 261 lblk, es1->es_lblk, es1->es_len, 262 ext4_es_pblock(es1), ext4_es_status(es1)); 263 goto out; 264 } 265 } 266 267 es1 = __es_tree_search(&tree->root, lblk); 268 269 out: 270 if (es1 && !ext4_es_is_delayed(es1)) { 271 while ((node = rb_next(&es1->rb_node)) != NULL) { 272 es1 = rb_entry(node, struct extent_status, rb_node); 273 if (ext4_es_is_delayed(es1)) 274 break; 275 } 276 } 277 278 if (es1 && ext4_es_is_delayed(es1)) { 279 tree->cache_es = es1; 280 es->es_lblk = es1->es_lblk; 281 es->es_len = es1->es_len; 282 es->es_pblk = es1->es_pblk; 283 } 284 285 read_unlock(&EXT4_I(inode)->i_es_lock); 286 287 ext4_es_lru_add(inode); 288 trace_ext4_es_find_delayed_extent_exit(inode, es); 289 } 290 291 static struct extent_status * 292 ext4_es_alloc_extent(struct inode *inode, ext4_lblk_t lblk, ext4_lblk_t len, 293 ext4_fsblk_t pblk) 294 { 295 struct extent_status *es; 296 es = kmem_cache_alloc(ext4_es_cachep, GFP_ATOMIC); 297 if (es == NULL) 298 return NULL; 299 es->es_lblk = lblk; 300 es->es_len = len; 301 es->es_pblk = pblk; 302 303 /* 304 * We don't count delayed extent because we never try to reclaim them 305 */ 306 if (!ext4_es_is_delayed(es)) { 307 EXT4_I(inode)->i_es_lru_nr++; 308 percpu_counter_inc(&EXT4_SB(inode->i_sb)->s_extent_cache_cnt); 309 } 310 311 return es; 312 } 313 314 static void ext4_es_free_extent(struct inode *inode, struct extent_status *es) 315 { 316 /* Decrease the lru counter when this es is not delayed */ 317 if (!ext4_es_is_delayed(es)) { 318 BUG_ON(EXT4_I(inode)->i_es_lru_nr == 0); 319 EXT4_I(inode)->i_es_lru_nr--; 320 percpu_counter_dec(&EXT4_SB(inode->i_sb)->s_extent_cache_cnt); 321 } 322 323 kmem_cache_free(ext4_es_cachep, es); 324 } 325 326 /* 327 * Check whether or not two extents can be merged 328 * Condition: 329 * - logical block number is contiguous 330 * - physical block number is contiguous 331 * - status is equal 332 */ 333 static int ext4_es_can_be_merged(struct extent_status *es1, 334 struct extent_status *es2) 335 { 336 if (ext4_es_status(es1) != ext4_es_status(es2)) 337 return 0; 338 339 if (((__u64) es1->es_len) + es2->es_len > 0xFFFFFFFFULL) 340 return 0; 341 342 if (((__u64) es1->es_lblk) + es1->es_len != es2->es_lblk) 343 return 0; 344 345 if ((ext4_es_is_written(es1) || ext4_es_is_unwritten(es1)) && 346 (ext4_es_pblock(es1) + es1->es_len == ext4_es_pblock(es2))) 347 return 1; 348 349 if (ext4_es_is_hole(es1)) 350 return 1; 351 352 /* we need to check delayed extent is without unwritten status */ 353 if (ext4_es_is_delayed(es1) && !ext4_es_is_unwritten(es1)) 354 return 1; 355 356 return 0; 357 } 358 359 static struct extent_status * 360 ext4_es_try_to_merge_left(struct inode *inode, struct extent_status *es) 361 { 362 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree; 363 struct extent_status *es1; 364 struct rb_node *node; 365 366 node = rb_prev(&es->rb_node); 367 if (!node) 368 return es; 369 370 es1 = rb_entry(node, struct extent_status, rb_node); 371 if (ext4_es_can_be_merged(es1, es)) { 372 es1->es_len += es->es_len; 373 rb_erase(&es->rb_node, &tree->root); 374 ext4_es_free_extent(inode, es); 375 es = es1; 376 } 377 378 return es; 379 } 380 381 static struct extent_status * 382 ext4_es_try_to_merge_right(struct inode *inode, struct extent_status *es) 383 { 384 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree; 385 struct extent_status *es1; 386 struct rb_node *node; 387 388 node = rb_next(&es->rb_node); 389 if (!node) 390 return es; 391 392 es1 = rb_entry(node, struct extent_status, rb_node); 393 if (ext4_es_can_be_merged(es, es1)) { 394 es->es_len += es1->es_len; 395 rb_erase(node, &tree->root); 396 ext4_es_free_extent(inode, es1); 397 } 398 399 return es; 400 } 401 402 #ifdef ES_AGGRESSIVE_TEST 403 static void ext4_es_insert_extent_ext_check(struct inode *inode, 404 struct extent_status *es) 405 { 406 struct ext4_ext_path *path = NULL; 407 struct ext4_extent *ex; 408 ext4_lblk_t ee_block; 409 ext4_fsblk_t ee_start; 410 unsigned short ee_len; 411 int depth, ee_status, es_status; 412 413 path = ext4_ext_find_extent(inode, es->es_lblk, NULL); 414 if (IS_ERR(path)) 415 return; 416 417 depth = ext_depth(inode); 418 ex = path[depth].p_ext; 419 420 if (ex) { 421 422 ee_block = le32_to_cpu(ex->ee_block); 423 ee_start = ext4_ext_pblock(ex); 424 ee_len = ext4_ext_get_actual_len(ex); 425 426 ee_status = ext4_ext_is_uninitialized(ex) ? 1 : 0; 427 es_status = ext4_es_is_unwritten(es) ? 1 : 0; 428 429 /* 430 * Make sure ex and es are not overlap when we try to insert 431 * a delayed/hole extent. 432 */ 433 if (!ext4_es_is_written(es) && !ext4_es_is_unwritten(es)) { 434 if (in_range(es->es_lblk, ee_block, ee_len)) { 435 pr_warn("ES insert assertation failed for " 436 "inode: %lu we can find an extent " 437 "at block [%d/%d/%llu/%c], but we " 438 "want to add an delayed/hole extent " 439 "[%d/%d/%llu/%llx]\n", 440 inode->i_ino, ee_block, ee_len, 441 ee_start, ee_status ? 'u' : 'w', 442 es->es_lblk, es->es_len, 443 ext4_es_pblock(es), ext4_es_status(es)); 444 } 445 goto out; 446 } 447 448 /* 449 * We don't check ee_block == es->es_lblk, etc. because es 450 * might be a part of whole extent, vice versa. 451 */ 452 if (es->es_lblk < ee_block || 453 ext4_es_pblock(es) != ee_start + es->es_lblk - ee_block) { 454 pr_warn("ES insert assertation failed for inode: %lu " 455 "ex_status [%d/%d/%llu/%c] != " 456 "es_status [%d/%d/%llu/%c]\n", inode->i_ino, 457 ee_block, ee_len, ee_start, 458 ee_status ? 'u' : 'w', es->es_lblk, es->es_len, 459 ext4_es_pblock(es), es_status ? 'u' : 'w'); 460 goto out; 461 } 462 463 if (ee_status ^ es_status) { 464 pr_warn("ES insert assertation failed for inode: %lu " 465 "ex_status [%d/%d/%llu/%c] != " 466 "es_status [%d/%d/%llu/%c]\n", inode->i_ino, 467 ee_block, ee_len, ee_start, 468 ee_status ? 'u' : 'w', es->es_lblk, es->es_len, 469 ext4_es_pblock(es), es_status ? 'u' : 'w'); 470 } 471 } else { 472 /* 473 * We can't find an extent on disk. So we need to make sure 474 * that we don't want to add an written/unwritten extent. 475 */ 476 if (!ext4_es_is_delayed(es) && !ext4_es_is_hole(es)) { 477 pr_warn("ES insert assertation failed for inode: %lu " 478 "can't find an extent at block %d but we want " 479 "to add an written/unwritten extent " 480 "[%d/%d/%llu/%llx]\n", inode->i_ino, 481 es->es_lblk, es->es_lblk, es->es_len, 482 ext4_es_pblock(es), ext4_es_status(es)); 483 } 484 } 485 out: 486 if (path) { 487 ext4_ext_drop_refs(path); 488 kfree(path); 489 } 490 } 491 492 static void ext4_es_insert_extent_ind_check(struct inode *inode, 493 struct extent_status *es) 494 { 495 struct ext4_map_blocks map; 496 int retval; 497 498 /* 499 * Here we call ext4_ind_map_blocks to lookup a block mapping because 500 * 'Indirect' structure is defined in indirect.c. So we couldn't 501 * access direct/indirect tree from outside. It is too dirty to define 502 * this function in indirect.c file. 503 */ 504 505 map.m_lblk = es->es_lblk; 506 map.m_len = es->es_len; 507 508 retval = ext4_ind_map_blocks(NULL, inode, &map, 0); 509 if (retval > 0) { 510 if (ext4_es_is_delayed(es) || ext4_es_is_hole(es)) { 511 /* 512 * We want to add a delayed/hole extent but this 513 * block has been allocated. 514 */ 515 pr_warn("ES insert assertation failed for inode: %lu " 516 "We can find blocks but we want to add a " 517 "delayed/hole extent [%d/%d/%llu/%llx]\n", 518 inode->i_ino, es->es_lblk, es->es_len, 519 ext4_es_pblock(es), ext4_es_status(es)); 520 return; 521 } else if (ext4_es_is_written(es)) { 522 if (retval != es->es_len) { 523 pr_warn("ES insert assertation failed for " 524 "inode: %lu retval %d != es_len %d\n", 525 inode->i_ino, retval, es->es_len); 526 return; 527 } 528 if (map.m_pblk != ext4_es_pblock(es)) { 529 pr_warn("ES insert assertation failed for " 530 "inode: %lu m_pblk %llu != " 531 "es_pblk %llu\n", 532 inode->i_ino, map.m_pblk, 533 ext4_es_pblock(es)); 534 return; 535 } 536 } else { 537 /* 538 * We don't need to check unwritten extent because 539 * indirect-based file doesn't have it. 540 */ 541 BUG_ON(1); 542 } 543 } else if (retval == 0) { 544 if (ext4_es_is_written(es)) { 545 pr_warn("ES insert assertation failed for inode: %lu " 546 "We can't find the block but we want to add " 547 "an written extent [%d/%d/%llu/%llx]\n", 548 inode->i_ino, es->es_lblk, es->es_len, 549 ext4_es_pblock(es), ext4_es_status(es)); 550 return; 551 } 552 } 553 } 554 555 static inline void ext4_es_insert_extent_check(struct inode *inode, 556 struct extent_status *es) 557 { 558 /* 559 * We don't need to worry about the race condition because 560 * caller takes i_data_sem locking. 561 */ 562 BUG_ON(!rwsem_is_locked(&EXT4_I(inode)->i_data_sem)); 563 if (ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS)) 564 ext4_es_insert_extent_ext_check(inode, es); 565 else 566 ext4_es_insert_extent_ind_check(inode, es); 567 } 568 #else 569 static inline void ext4_es_insert_extent_check(struct inode *inode, 570 struct extent_status *es) 571 { 572 } 573 #endif 574 575 static int __es_insert_extent(struct inode *inode, struct extent_status *newes) 576 { 577 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree; 578 struct rb_node **p = &tree->root.rb_node; 579 struct rb_node *parent = NULL; 580 struct extent_status *es; 581 582 while (*p) { 583 parent = *p; 584 es = rb_entry(parent, struct extent_status, rb_node); 585 586 if (newes->es_lblk < es->es_lblk) { 587 if (ext4_es_can_be_merged(newes, es)) { 588 /* 589 * Here we can modify es_lblk directly 590 * because it isn't overlapped. 591 */ 592 es->es_lblk = newes->es_lblk; 593 es->es_len += newes->es_len; 594 if (ext4_es_is_written(es) || 595 ext4_es_is_unwritten(es)) 596 ext4_es_store_pblock(es, 597 newes->es_pblk); 598 es = ext4_es_try_to_merge_left(inode, es); 599 goto out; 600 } 601 p = &(*p)->rb_left; 602 } else if (newes->es_lblk > ext4_es_end(es)) { 603 if (ext4_es_can_be_merged(es, newes)) { 604 es->es_len += newes->es_len; 605 es = ext4_es_try_to_merge_right(inode, es); 606 goto out; 607 } 608 p = &(*p)->rb_right; 609 } else { 610 BUG_ON(1); 611 return -EINVAL; 612 } 613 } 614 615 es = ext4_es_alloc_extent(inode, newes->es_lblk, newes->es_len, 616 newes->es_pblk); 617 if (!es) 618 return -ENOMEM; 619 rb_link_node(&es->rb_node, parent, p); 620 rb_insert_color(&es->rb_node, &tree->root); 621 622 out: 623 tree->cache_es = es; 624 return 0; 625 } 626 627 /* 628 * ext4_es_insert_extent() adds a space to a extent status tree. 629 * 630 * ext4_es_insert_extent is called by ext4_da_write_begin and 631 * ext4_es_remove_extent. 632 * 633 * Return 0 on success, error code on failure. 634 */ 635 int ext4_es_insert_extent(struct inode *inode, ext4_lblk_t lblk, 636 ext4_lblk_t len, ext4_fsblk_t pblk, 637 unsigned long long status) 638 { 639 struct extent_status newes; 640 ext4_lblk_t end = lblk + len - 1; 641 int err = 0; 642 643 es_debug("add [%u/%u) %llu %llx to extent status tree of inode %lu\n", 644 lblk, len, pblk, status, inode->i_ino); 645 646 if (!len) 647 return 0; 648 649 BUG_ON(end < lblk); 650 651 newes.es_lblk = lblk; 652 newes.es_len = len; 653 ext4_es_store_pblock(&newes, pblk); 654 ext4_es_store_status(&newes, status); 655 trace_ext4_es_insert_extent(inode, &newes); 656 657 ext4_es_insert_extent_check(inode, &newes); 658 659 write_lock(&EXT4_I(inode)->i_es_lock); 660 err = __es_remove_extent(inode, lblk, end); 661 if (err != 0) 662 goto error; 663 err = __es_insert_extent(inode, &newes); 664 665 error: 666 write_unlock(&EXT4_I(inode)->i_es_lock); 667 668 ext4_es_lru_add(inode); 669 ext4_es_print_tree(inode); 670 671 return err; 672 } 673 674 /* 675 * ext4_es_lookup_extent() looks up an extent in extent status tree. 676 * 677 * ext4_es_lookup_extent is called by ext4_map_blocks/ext4_da_map_blocks. 678 * 679 * Return: 1 on found, 0 on not 680 */ 681 int ext4_es_lookup_extent(struct inode *inode, ext4_lblk_t lblk, 682 struct extent_status *es) 683 { 684 struct ext4_es_tree *tree; 685 struct extent_status *es1 = NULL; 686 struct rb_node *node; 687 int found = 0; 688 689 trace_ext4_es_lookup_extent_enter(inode, lblk); 690 es_debug("lookup extent in block %u\n", lblk); 691 692 tree = &EXT4_I(inode)->i_es_tree; 693 read_lock(&EXT4_I(inode)->i_es_lock); 694 695 /* find extent in cache firstly */ 696 es->es_lblk = es->es_len = es->es_pblk = 0; 697 if (tree->cache_es) { 698 es1 = tree->cache_es; 699 if (in_range(lblk, es1->es_lblk, es1->es_len)) { 700 es_debug("%u cached by [%u/%u)\n", 701 lblk, es1->es_lblk, es1->es_len); 702 found = 1; 703 goto out; 704 } 705 } 706 707 node = tree->root.rb_node; 708 while (node) { 709 es1 = rb_entry(node, struct extent_status, rb_node); 710 if (lblk < es1->es_lblk) 711 node = node->rb_left; 712 else if (lblk > ext4_es_end(es1)) 713 node = node->rb_right; 714 else { 715 found = 1; 716 break; 717 } 718 } 719 720 out: 721 if (found) { 722 BUG_ON(!es1); 723 es->es_lblk = es1->es_lblk; 724 es->es_len = es1->es_len; 725 es->es_pblk = es1->es_pblk; 726 } 727 728 read_unlock(&EXT4_I(inode)->i_es_lock); 729 730 ext4_es_lru_add(inode); 731 trace_ext4_es_lookup_extent_exit(inode, es, found); 732 return found; 733 } 734 735 static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk, 736 ext4_lblk_t end) 737 { 738 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree; 739 struct rb_node *node; 740 struct extent_status *es; 741 struct extent_status orig_es; 742 ext4_lblk_t len1, len2; 743 ext4_fsblk_t block; 744 int err = 0; 745 746 es = __es_tree_search(&tree->root, lblk); 747 if (!es) 748 goto out; 749 if (es->es_lblk > end) 750 goto out; 751 752 /* Simply invalidate cache_es. */ 753 tree->cache_es = NULL; 754 755 orig_es.es_lblk = es->es_lblk; 756 orig_es.es_len = es->es_len; 757 orig_es.es_pblk = es->es_pblk; 758 759 len1 = lblk > es->es_lblk ? lblk - es->es_lblk : 0; 760 len2 = ext4_es_end(es) > end ? ext4_es_end(es) - end : 0; 761 if (len1 > 0) 762 es->es_len = len1; 763 if (len2 > 0) { 764 if (len1 > 0) { 765 struct extent_status newes; 766 767 newes.es_lblk = end + 1; 768 newes.es_len = len2; 769 if (ext4_es_is_written(&orig_es) || 770 ext4_es_is_unwritten(&orig_es)) { 771 block = ext4_es_pblock(&orig_es) + 772 orig_es.es_len - len2; 773 ext4_es_store_pblock(&newes, block); 774 } 775 ext4_es_store_status(&newes, ext4_es_status(&orig_es)); 776 err = __es_insert_extent(inode, &newes); 777 if (err) { 778 es->es_lblk = orig_es.es_lblk; 779 es->es_len = orig_es.es_len; 780 goto out; 781 } 782 } else { 783 es->es_lblk = end + 1; 784 es->es_len = len2; 785 if (ext4_es_is_written(es) || 786 ext4_es_is_unwritten(es)) { 787 block = orig_es.es_pblk + orig_es.es_len - len2; 788 ext4_es_store_pblock(es, block); 789 } 790 } 791 goto out; 792 } 793 794 if (len1 > 0) { 795 node = rb_next(&es->rb_node); 796 if (node) 797 es = rb_entry(node, struct extent_status, rb_node); 798 else 799 es = NULL; 800 } 801 802 while (es && ext4_es_end(es) <= end) { 803 node = rb_next(&es->rb_node); 804 rb_erase(&es->rb_node, &tree->root); 805 ext4_es_free_extent(inode, es); 806 if (!node) { 807 es = NULL; 808 break; 809 } 810 es = rb_entry(node, struct extent_status, rb_node); 811 } 812 813 if (es && es->es_lblk < end + 1) { 814 ext4_lblk_t orig_len = es->es_len; 815 816 len1 = ext4_es_end(es) - end; 817 es->es_lblk = end + 1; 818 es->es_len = len1; 819 if (ext4_es_is_written(es) || ext4_es_is_unwritten(es)) { 820 block = es->es_pblk + orig_len - len1; 821 ext4_es_store_pblock(es, block); 822 } 823 } 824 825 out: 826 return err; 827 } 828 829 /* 830 * ext4_es_remove_extent() removes a space from a extent status tree. 831 * 832 * Return 0 on success, error code on failure. 833 */ 834 int ext4_es_remove_extent(struct inode *inode, ext4_lblk_t lblk, 835 ext4_lblk_t len) 836 { 837 ext4_lblk_t end; 838 int err = 0; 839 840 trace_ext4_es_remove_extent(inode, lblk, len); 841 es_debug("remove [%u/%u) from extent status tree of inode %lu\n", 842 lblk, len, inode->i_ino); 843 844 if (!len) 845 return err; 846 847 end = lblk + len - 1; 848 BUG_ON(end < lblk); 849 850 write_lock(&EXT4_I(inode)->i_es_lock); 851 err = __es_remove_extent(inode, lblk, end); 852 write_unlock(&EXT4_I(inode)->i_es_lock); 853 ext4_es_print_tree(inode); 854 return err; 855 } 856 857 int ext4_es_zeroout(struct inode *inode, struct ext4_extent *ex) 858 { 859 ext4_lblk_t ee_block; 860 ext4_fsblk_t ee_pblock; 861 unsigned int ee_len; 862 863 ee_block = le32_to_cpu(ex->ee_block); 864 ee_len = ext4_ext_get_actual_len(ex); 865 ee_pblock = ext4_ext_pblock(ex); 866 867 if (ee_len == 0) 868 return 0; 869 870 return ext4_es_insert_extent(inode, ee_block, ee_len, ee_pblock, 871 EXTENT_STATUS_WRITTEN); 872 } 873 874 static int ext4_es_shrink(struct shrinker *shrink, struct shrink_control *sc) 875 { 876 struct ext4_sb_info *sbi = container_of(shrink, 877 struct ext4_sb_info, s_es_shrinker); 878 struct ext4_inode_info *ei; 879 struct list_head *cur, *tmp, scanned; 880 int nr_to_scan = sc->nr_to_scan; 881 int ret, nr_shrunk = 0; 882 883 ret = percpu_counter_read_positive(&sbi->s_extent_cache_cnt); 884 trace_ext4_es_shrink_enter(sbi->s_sb, nr_to_scan, ret); 885 886 if (!nr_to_scan) 887 return ret; 888 889 INIT_LIST_HEAD(&scanned); 890 891 spin_lock(&sbi->s_es_lru_lock); 892 list_for_each_safe(cur, tmp, &sbi->s_es_lru) { 893 list_move_tail(cur, &scanned); 894 895 ei = list_entry(cur, struct ext4_inode_info, i_es_lru); 896 897 read_lock(&ei->i_es_lock); 898 if (ei->i_es_lru_nr == 0) { 899 read_unlock(&ei->i_es_lock); 900 continue; 901 } 902 read_unlock(&ei->i_es_lock); 903 904 write_lock(&ei->i_es_lock); 905 ret = __es_try_to_reclaim_extents(ei, nr_to_scan); 906 write_unlock(&ei->i_es_lock); 907 908 nr_shrunk += ret; 909 nr_to_scan -= ret; 910 if (nr_to_scan == 0) 911 break; 912 } 913 list_splice_tail(&scanned, &sbi->s_es_lru); 914 spin_unlock(&sbi->s_es_lru_lock); 915 916 ret = percpu_counter_read_positive(&sbi->s_extent_cache_cnt); 917 trace_ext4_es_shrink_exit(sbi->s_sb, nr_shrunk, ret); 918 return ret; 919 } 920 921 void ext4_es_register_shrinker(struct super_block *sb) 922 { 923 struct ext4_sb_info *sbi; 924 925 sbi = EXT4_SB(sb); 926 INIT_LIST_HEAD(&sbi->s_es_lru); 927 spin_lock_init(&sbi->s_es_lru_lock); 928 sbi->s_es_shrinker.shrink = ext4_es_shrink; 929 sbi->s_es_shrinker.seeks = DEFAULT_SEEKS; 930 register_shrinker(&sbi->s_es_shrinker); 931 } 932 933 void ext4_es_unregister_shrinker(struct super_block *sb) 934 { 935 unregister_shrinker(&EXT4_SB(sb)->s_es_shrinker); 936 } 937 938 void ext4_es_lru_add(struct inode *inode) 939 { 940 struct ext4_inode_info *ei = EXT4_I(inode); 941 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb); 942 943 spin_lock(&sbi->s_es_lru_lock); 944 if (list_empty(&ei->i_es_lru)) 945 list_add_tail(&ei->i_es_lru, &sbi->s_es_lru); 946 else 947 list_move_tail(&ei->i_es_lru, &sbi->s_es_lru); 948 spin_unlock(&sbi->s_es_lru_lock); 949 } 950 951 void ext4_es_lru_del(struct inode *inode) 952 { 953 struct ext4_inode_info *ei = EXT4_I(inode); 954 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb); 955 956 spin_lock(&sbi->s_es_lru_lock); 957 if (!list_empty(&ei->i_es_lru)) 958 list_del_init(&ei->i_es_lru); 959 spin_unlock(&sbi->s_es_lru_lock); 960 } 961 962 static int __es_try_to_reclaim_extents(struct ext4_inode_info *ei, 963 int nr_to_scan) 964 { 965 struct inode *inode = &ei->vfs_inode; 966 struct ext4_es_tree *tree = &ei->i_es_tree; 967 struct rb_node *node; 968 struct extent_status *es; 969 int nr_shrunk = 0; 970 971 if (ei->i_es_lru_nr == 0) 972 return 0; 973 974 node = rb_first(&tree->root); 975 while (node != NULL) { 976 es = rb_entry(node, struct extent_status, rb_node); 977 node = rb_next(&es->rb_node); 978 /* 979 * We can't reclaim delayed extent from status tree because 980 * fiemap, bigallic, and seek_data/hole need to use it. 981 */ 982 if (!ext4_es_is_delayed(es)) { 983 rb_erase(&es->rb_node, &tree->root); 984 ext4_es_free_extent(inode, es); 985 nr_shrunk++; 986 if (--nr_to_scan == 0) 987 break; 988 } 989 } 990 tree->cache_es = NULL; 991 return nr_shrunk; 992 } 993