2277 lines · c
1// SPDX-License-Identifier: GPL-2.02/*3 * fs/ext4/extents_status.c4 *5 * Written by Yongqiang Yang <xiaoqiangnk@gmail.com>6 * Modified by7 * 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, we22 * will introduce a new structure called io tree to track all extent23 * status in order to solve some problems that we have met24 * (e.g. Reservation space warning), and provide extent-level locking.25 * Delay extent tree is the first step to achieve this goal. It is26 * original built by Yongqiang Yang. At that time it is called delay27 * extent tree, whose goal is only track delayed extents in memory to28 * simplify the implementation of fiemap and bigalloc, and introduce29 * lseek SEEK_DATA/SEEK_HOLE support. That is why it is still called30 * delay extent tree at the first commit. But for better understand31 * 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 are35 * tracked in the tree. It maintains the delayed extent when a delayed36 * allocation is issued, and the delayed extent is written out or37 * invalidated. Therefore the implementation of fiemap and bigalloc38 * are simplified, and SEEK_DATA/SEEK_HOLE are introduced.39 *40 * The following comment describes the implemenmtation of extent41 * 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 before46 * finding it in extent tree. Hence, single extent cache can be removed47 * because extent status tree can do a better job. Extents in status48 * tree are loaded on-demand. Therefore, the extent status tree may not49 * contain all of the extents in a file. Meanwhile we define a shrinker50 * to reclaim memory from extent status tree because fragmented extent51 * tree will make status tree cost too much memory. written/unwritten/-52 * hole extents in the tree will be reclaimed by this shrinker when we53 * are under high memory pressure. Delayed extents will not be54 * 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 looking67 * 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 a71 * 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 * -- FIEMAP75 * FIEMAP looks up page cache to identify delayed allocations from holes.76 *77 * -- SEEK_HOLE/DATA78 * SEEK_HOLE/DATA has the same problem as FIEMAP.79 *80 * -- bigalloc81 * bigalloc looks up page cache to figure out if a block is82 * already under delayed allocation or not to determine whether83 * quota reserving is needed for the cluster.84 *85 * -- writeout86 * Writeout looks up whole page cache to see if a buffer is87 * mapped, If there are not very many delayed buffers, then it is88 * 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 of92 * blocks is under delayed allocation(belonged to a delayed extent) or93 * not by searching the extent tree.94 *95 *96 * ==========================================================================97 * 2. Ext4 extent status tree impelmentation98 *99 * -- extent100 * A extent is a range of blocks which are contiguous logically and101 * physically. Unlike extent in extent tree, this extent in ext4 is102 * a in-memory struct, there is no corresponding on-disk data. There103 * is no limit on length of extent, so an extent can contain as many104 * blocks as they are contiguous logically and physically.105 *106 * -- extent status tree107 * Every inode has an extent status tree and all allocation blocks108 * are added to the tree with different status. The extent in the109 * tree are ordered by logical block no.110 *111 * -- operations on a extent status tree112 * There are three important operations on a delayed extent tree: find113 * next extent, adding a extent(a range of blocks) and removing a extent.114 *115 * -- race on a extent status tree116 * Extent status tree is protected by inode->i_es_lock.117 *118 * -- memory consumption119 * Fragmented extent tree will make extent status tree cost too much120 * memory. Hence, we will reclaim written/unwritten/hole extents from121 * the tree under a heavy memory pressure.122 *123 *124 * ==========================================================================125 * 3. Performance analysis126 *127 * -- overhead128 * 1. There is a cache extent for write access, so if writes are129 * not very random, adding space operaions are in O(1) time.130 *131 * -- gain132 * 2. Code is much simpler, more readable, more maintainable and133 * more efficient.134 *135 *136 * ==========================================================================137 * 4. TODO list138 *139 * -- Refactor delayed space reservation140 *141 * -- Extent-level locking142 */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#else198#define ext4_es_print_tree(inode)199#endif200 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. If209 * 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 else224 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 block241 * range or next extent following block range in242 * extents status tree243 *244 * @inode - file containing the range245 * @matching_fn - pointer to function that matches extents with desired status246 * @lblk - logical block defining start of range247 * @end - logical block defining end of range248 * @es - extent found, if any249 *250 * Find the first extent within the block range specified by @lblk and @end251 * in the extents status tree that satisfies @matching_fn. If a match252 * is found, it's returned in @es. If not, and a matching extent is found253 * beyond the block range, it's returned in @es. If no match is found, an254 * extent is returned in @es whose es_lblk, es_len, and es_pblk components255 * 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 use307 */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 es->es_lblk = es->es_len = es->es_pblk = 0;314 315 if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY)316 return;317 318 trace_ext4_es_find_extent_range_enter(inode, lblk);319 320 read_lock(&EXT4_I(inode)->i_es_lock);321 __es_find_extent_range(inode, matching_fn, lblk, end, es);322 read_unlock(&EXT4_I(inode)->i_es_lock);323 324 trace_ext4_es_find_extent_range_exit(inode, es);325}326 327/*328 * __es_scan_range - search block range for block with specified status329 * in extents status tree330 *331 * @inode - file containing the range332 * @matching_fn - pointer to function that matches extents with desired status333 * @lblk - logical block defining start of range334 * @end - logical block defining end of range335 *336 * Returns true if at least one block in the specified block range satisfies337 * the criterion specified by @matching_fn, and false if not. If at least338 * one extent has the specified status, then there is at least one block339 * in the cluster with that status. Should only be called by code that has340 * taken i_es_lock.341 */342static bool __es_scan_range(struct inode *inode,343 int (*matching_fn)(struct extent_status *es),344 ext4_lblk_t start, ext4_lblk_t end)345{346 struct extent_status es;347 348 __es_find_extent_range(inode, matching_fn, start, end, &es);349 if (es.es_len == 0)350 return false; /* no matching extent in the tree */351 else if (es.es_lblk <= start &&352 start < es.es_lblk + es.es_len)353 return true;354 else if (start <= es.es_lblk && es.es_lblk <= end)355 return true;356 else357 return false;358}359/*360 * Locking for __es_scan_range() for external use361 */362bool ext4_es_scan_range(struct inode *inode,363 int (*matching_fn)(struct extent_status *es),364 ext4_lblk_t lblk, ext4_lblk_t end)365{366 bool ret;367 368 if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY)369 return false;370 371 read_lock(&EXT4_I(inode)->i_es_lock);372 ret = __es_scan_range(inode, matching_fn, lblk, end);373 read_unlock(&EXT4_I(inode)->i_es_lock);374 375 return ret;376}377 378/*379 * __es_scan_clu - search cluster for block with specified status in380 * extents status tree381 *382 * @inode - file containing the cluster383 * @matching_fn - pointer to function that matches extents with desired status384 * @lblk - logical block in cluster to be searched385 *386 * Returns true if at least one extent in the cluster containing @lblk387 * satisfies the criterion specified by @matching_fn, and false if not. If at388 * least one extent has the specified status, then there is at least one block389 * in the cluster with that status. Should only be called by code that has390 * taken i_es_lock.391 */392static bool __es_scan_clu(struct inode *inode,393 int (*matching_fn)(struct extent_status *es),394 ext4_lblk_t lblk)395{396 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);397 ext4_lblk_t lblk_start, lblk_end;398 399 lblk_start = EXT4_LBLK_CMASK(sbi, lblk);400 lblk_end = lblk_start + sbi->s_cluster_ratio - 1;401 402 return __es_scan_range(inode, matching_fn, lblk_start, lblk_end);403}404 405/*406 * Locking for __es_scan_clu() for external use407 */408bool ext4_es_scan_clu(struct inode *inode,409 int (*matching_fn)(struct extent_status *es),410 ext4_lblk_t lblk)411{412 bool ret;413 414 if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY)415 return false;416 417 read_lock(&EXT4_I(inode)->i_es_lock);418 ret = __es_scan_clu(inode, matching_fn, lblk);419 read_unlock(&EXT4_I(inode)->i_es_lock);420 421 return ret;422}423 424static void ext4_es_list_add(struct inode *inode)425{426 struct ext4_inode_info *ei = EXT4_I(inode);427 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);428 429 if (!list_empty(&ei->i_es_list))430 return;431 432 spin_lock(&sbi->s_es_lock);433 if (list_empty(&ei->i_es_list)) {434 list_add_tail(&ei->i_es_list, &sbi->s_es_list);435 sbi->s_es_nr_inode++;436 }437 spin_unlock(&sbi->s_es_lock);438}439 440static void ext4_es_list_del(struct inode *inode)441{442 struct ext4_inode_info *ei = EXT4_I(inode);443 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);444 445 spin_lock(&sbi->s_es_lock);446 if (!list_empty(&ei->i_es_list)) {447 list_del_init(&ei->i_es_list);448 sbi->s_es_nr_inode--;449 WARN_ON_ONCE(sbi->s_es_nr_inode < 0);450 }451 spin_unlock(&sbi->s_es_lock);452}453 454static inline struct pending_reservation *__alloc_pending(bool nofail)455{456 if (!nofail)457 return kmem_cache_alloc(ext4_pending_cachep, GFP_ATOMIC);458 459 return kmem_cache_zalloc(ext4_pending_cachep, GFP_KERNEL | __GFP_NOFAIL);460}461 462static inline void __free_pending(struct pending_reservation *pr)463{464 kmem_cache_free(ext4_pending_cachep, pr);465}466 467/*468 * Returns true if we cannot fail to allocate memory for this extent_status469 * entry and cannot reclaim it until its status changes.470 */471static inline bool ext4_es_must_keep(struct extent_status *es)472{473 /* fiemap, bigalloc, and seek_data/hole need to use it. */474 if (ext4_es_is_delayed(es))475 return true;476 477 return false;478}479 480static inline struct extent_status *__es_alloc_extent(bool nofail)481{482 if (!nofail)483 return kmem_cache_alloc(ext4_es_cachep, GFP_ATOMIC);484 485 return kmem_cache_zalloc(ext4_es_cachep, GFP_KERNEL | __GFP_NOFAIL);486}487 488static void ext4_es_init_extent(struct inode *inode, struct extent_status *es,489 ext4_lblk_t lblk, ext4_lblk_t len, ext4_fsblk_t pblk)490{491 es->es_lblk = lblk;492 es->es_len = len;493 es->es_pblk = pblk;494 495 /* We never try to reclaim a must kept extent, so we don't count it. */496 if (!ext4_es_must_keep(es)) {497 if (!EXT4_I(inode)->i_es_shk_nr++)498 ext4_es_list_add(inode);499 percpu_counter_inc(&EXT4_SB(inode->i_sb)->500 s_es_stats.es_stats_shk_cnt);501 }502 503 EXT4_I(inode)->i_es_all_nr++;504 percpu_counter_inc(&EXT4_SB(inode->i_sb)->s_es_stats.es_stats_all_cnt);505}506 507static inline void __es_free_extent(struct extent_status *es)508{509 kmem_cache_free(ext4_es_cachep, es);510}511 512static void ext4_es_free_extent(struct inode *inode, struct extent_status *es)513{514 EXT4_I(inode)->i_es_all_nr--;515 percpu_counter_dec(&EXT4_SB(inode->i_sb)->s_es_stats.es_stats_all_cnt);516 517 /* Decrease the shrink counter when we can reclaim the extent. */518 if (!ext4_es_must_keep(es)) {519 BUG_ON(EXT4_I(inode)->i_es_shk_nr == 0);520 if (!--EXT4_I(inode)->i_es_shk_nr)521 ext4_es_list_del(inode);522 percpu_counter_dec(&EXT4_SB(inode->i_sb)->523 s_es_stats.es_stats_shk_cnt);524 }525 526 __es_free_extent(es);527}528 529/*530 * Check whether or not two extents can be merged531 * Condition:532 * - logical block number is contiguous533 * - physical block number is contiguous534 * - status is equal535 */536static int ext4_es_can_be_merged(struct extent_status *es1,537 struct extent_status *es2)538{539 if (ext4_es_type(es1) != ext4_es_type(es2))540 return 0;541 542 if (((__u64) es1->es_len) + es2->es_len > EXT_MAX_BLOCKS) {543 pr_warn("ES assertion failed when merging extents. "544 "The sum of lengths of es1 (%d) and es2 (%d) "545 "is bigger than allowed file size (%d)\n",546 es1->es_len, es2->es_len, EXT_MAX_BLOCKS);547 WARN_ON(1);548 return 0;549 }550 551 if (((__u64) es1->es_lblk) + es1->es_len != es2->es_lblk)552 return 0;553 554 if ((ext4_es_is_written(es1) || ext4_es_is_unwritten(es1)) &&555 (ext4_es_pblock(es1) + es1->es_len == ext4_es_pblock(es2)))556 return 1;557 558 if (ext4_es_is_hole(es1))559 return 1;560 561 /* we need to check delayed extent */562 if (ext4_es_is_delayed(es1))563 return 1;564 565 return 0;566}567 568static struct extent_status *569ext4_es_try_to_merge_left(struct inode *inode, struct extent_status *es)570{571 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;572 struct extent_status *es1;573 struct rb_node *node;574 575 node = rb_prev(&es->rb_node);576 if (!node)577 return es;578 579 es1 = rb_entry(node, struct extent_status, rb_node);580 if (ext4_es_can_be_merged(es1, es)) {581 es1->es_len += es->es_len;582 if (ext4_es_is_referenced(es))583 ext4_es_set_referenced(es1);584 rb_erase(&es->rb_node, &tree->root);585 ext4_es_free_extent(inode, es);586 es = es1;587 }588 589 return es;590}591 592static struct extent_status *593ext4_es_try_to_merge_right(struct inode *inode, struct extent_status *es)594{595 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;596 struct extent_status *es1;597 struct rb_node *node;598 599 node = rb_next(&es->rb_node);600 if (!node)601 return es;602 603 es1 = rb_entry(node, struct extent_status, rb_node);604 if (ext4_es_can_be_merged(es, es1)) {605 es->es_len += es1->es_len;606 if (ext4_es_is_referenced(es1))607 ext4_es_set_referenced(es);608 rb_erase(node, &tree->root);609 ext4_es_free_extent(inode, es1);610 }611 612 return es;613}614 615#ifdef ES_AGGRESSIVE_TEST616#include "ext4_extents.h" /* Needed when ES_AGGRESSIVE_TEST is defined */617 618static void ext4_es_insert_extent_ext_check(struct inode *inode,619 struct extent_status *es)620{621 struct ext4_ext_path *path = NULL;622 struct ext4_extent *ex;623 ext4_lblk_t ee_block;624 ext4_fsblk_t ee_start;625 unsigned short ee_len;626 int depth, ee_status, es_status;627 628 path = ext4_find_extent(inode, es->es_lblk, NULL, EXT4_EX_NOCACHE);629 if (IS_ERR(path))630 return;631 632 depth = ext_depth(inode);633 ex = path[depth].p_ext;634 635 if (ex) {636 637 ee_block = le32_to_cpu(ex->ee_block);638 ee_start = ext4_ext_pblock(ex);639 ee_len = ext4_ext_get_actual_len(ex);640 641 ee_status = ext4_ext_is_unwritten(ex) ? 1 : 0;642 es_status = ext4_es_is_unwritten(es) ? 1 : 0;643 644 /*645 * Make sure ex and es are not overlap when we try to insert646 * a delayed/hole extent.647 */648 if (!ext4_es_is_written(es) && !ext4_es_is_unwritten(es)) {649 if (in_range(es->es_lblk, ee_block, ee_len)) {650 pr_warn("ES insert assertion failed for "651 "inode: %lu we can find an extent "652 "at block [%d/%d/%llu/%c], but we "653 "want to add a delayed/hole extent "654 "[%d/%d/%llu/%x]\n",655 inode->i_ino, ee_block, ee_len,656 ee_start, ee_status ? 'u' : 'w',657 es->es_lblk, es->es_len,658 ext4_es_pblock(es), ext4_es_status(es));659 }660 goto out;661 }662 663 /*664 * We don't check ee_block == es->es_lblk, etc. because es665 * might be a part of whole extent, vice versa.666 */667 if (es->es_lblk < ee_block ||668 ext4_es_pblock(es) != ee_start + es->es_lblk - ee_block) {669 pr_warn("ES insert assertion failed for inode: %lu "670 "ex_status [%d/%d/%llu/%c] != "671 "es_status [%d/%d/%llu/%c]\n", inode->i_ino,672 ee_block, ee_len, ee_start,673 ee_status ? 'u' : 'w', es->es_lblk, es->es_len,674 ext4_es_pblock(es), es_status ? 'u' : 'w');675 goto out;676 }677 678 if (ee_status ^ es_status) {679 pr_warn("ES insert assertion failed for inode: %lu "680 "ex_status [%d/%d/%llu/%c] != "681 "es_status [%d/%d/%llu/%c]\n", inode->i_ino,682 ee_block, ee_len, ee_start,683 ee_status ? 'u' : 'w', es->es_lblk, es->es_len,684 ext4_es_pblock(es), es_status ? 'u' : 'w');685 }686 } else {687 /*688 * We can't find an extent on disk. So we need to make sure689 * that we don't want to add an written/unwritten extent.690 */691 if (!ext4_es_is_delayed(es) && !ext4_es_is_hole(es)) {692 pr_warn("ES insert assertion failed for inode: %lu "693 "can't find an extent at block %d but we want "694 "to add a written/unwritten extent "695 "[%d/%d/%llu/%x]\n", inode->i_ino,696 es->es_lblk, es->es_lblk, es->es_len,697 ext4_es_pblock(es), ext4_es_status(es));698 }699 }700out:701 ext4_free_ext_path(path);702}703 704static void ext4_es_insert_extent_ind_check(struct inode *inode,705 struct extent_status *es)706{707 struct ext4_map_blocks map;708 int retval;709 710 /*711 * Here we call ext4_ind_map_blocks to lookup a block mapping because712 * 'Indirect' structure is defined in indirect.c. So we couldn't713 * access direct/indirect tree from outside. It is too dirty to define714 * this function in indirect.c file.715 */716 717 map.m_lblk = es->es_lblk;718 map.m_len = es->es_len;719 720 retval = ext4_ind_map_blocks(NULL, inode, &map, 0);721 if (retval > 0) {722 if (ext4_es_is_delayed(es) || ext4_es_is_hole(es)) {723 /*724 * We want to add a delayed/hole extent but this725 * block has been allocated.726 */727 pr_warn("ES insert assertion failed for inode: %lu "728 "We can find blocks but we want to add a "729 "delayed/hole extent [%d/%d/%llu/%x]\n",730 inode->i_ino, es->es_lblk, es->es_len,731 ext4_es_pblock(es), ext4_es_status(es));732 return;733 } else if (ext4_es_is_written(es)) {734 if (retval != es->es_len) {735 pr_warn("ES insert assertion failed for "736 "inode: %lu retval %d != es_len %d\n",737 inode->i_ino, retval, es->es_len);738 return;739 }740 if (map.m_pblk != ext4_es_pblock(es)) {741 pr_warn("ES insert assertion failed for "742 "inode: %lu m_pblk %llu != "743 "es_pblk %llu\n",744 inode->i_ino, map.m_pblk,745 ext4_es_pblock(es));746 return;747 }748 } else {749 /*750 * We don't need to check unwritten extent because751 * indirect-based file doesn't have it.752 */753 BUG();754 }755 } else if (retval == 0) {756 if (ext4_es_is_written(es)) {757 pr_warn("ES insert assertion failed for inode: %lu "758 "We can't find the block but we want to add "759 "a written extent [%d/%d/%llu/%x]\n",760 inode->i_ino, es->es_lblk, es->es_len,761 ext4_es_pblock(es), ext4_es_status(es));762 return;763 }764 }765}766 767static inline void ext4_es_insert_extent_check(struct inode *inode,768 struct extent_status *es)769{770 /*771 * We don't need to worry about the race condition because772 * caller takes i_data_sem locking.773 */774 BUG_ON(!rwsem_is_locked(&EXT4_I(inode)->i_data_sem));775 if (ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))776 ext4_es_insert_extent_ext_check(inode, es);777 else778 ext4_es_insert_extent_ind_check(inode, es);779}780#else781static inline void ext4_es_insert_extent_check(struct inode *inode,782 struct extent_status *es)783{784}785#endif786 787static int __es_insert_extent(struct inode *inode, struct extent_status *newes,788 struct extent_status *prealloc)789{790 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;791 struct rb_node **p = &tree->root.rb_node;792 struct rb_node *parent = NULL;793 struct extent_status *es;794 795 while (*p) {796 parent = *p;797 es = rb_entry(parent, struct extent_status, rb_node);798 799 if (newes->es_lblk < es->es_lblk) {800 if (ext4_es_can_be_merged(newes, es)) {801 /*802 * Here we can modify es_lblk directly803 * because it isn't overlapped.804 */805 es->es_lblk = newes->es_lblk;806 es->es_len += newes->es_len;807 if (ext4_es_is_written(es) ||808 ext4_es_is_unwritten(es))809 ext4_es_store_pblock(es,810 newes->es_pblk);811 es = ext4_es_try_to_merge_left(inode, es);812 goto out;813 }814 p = &(*p)->rb_left;815 } else if (newes->es_lblk > ext4_es_end(es)) {816 if (ext4_es_can_be_merged(es, newes)) {817 es->es_len += newes->es_len;818 es = ext4_es_try_to_merge_right(inode, es);819 goto out;820 }821 p = &(*p)->rb_right;822 } else {823 BUG();824 return -EINVAL;825 }826 }827 828 if (prealloc)829 es = prealloc;830 else831 es = __es_alloc_extent(false);832 if (!es)833 return -ENOMEM;834 ext4_es_init_extent(inode, es, newes->es_lblk, newes->es_len,835 newes->es_pblk);836 837 rb_link_node(&es->rb_node, parent, p);838 rb_insert_color(&es->rb_node, &tree->root);839 840out:841 tree->cache_es = es;842 return 0;843}844 845/*846 * ext4_es_insert_extent() adds information to an inode's extent847 * status tree.848 */849void ext4_es_insert_extent(struct inode *inode, ext4_lblk_t lblk,850 ext4_lblk_t len, ext4_fsblk_t pblk,851 unsigned int status, int flags)852{853 struct extent_status newes;854 ext4_lblk_t end = lblk + len - 1;855 int err1 = 0, err2 = 0, err3 = 0;856 int resv_used = 0, pending = 0;857 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);858 struct extent_status *es1 = NULL;859 struct extent_status *es2 = NULL;860 struct pending_reservation *pr = NULL;861 bool revise_pending = false;862 863 if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY)864 return;865 866 es_debug("add [%u/%u) %llu %x %x to extent status tree of inode %lu\n",867 lblk, len, pblk, status, flags, inode->i_ino);868 869 if (!len)870 return;871 872 BUG_ON(end < lblk);873 WARN_ON_ONCE(status & EXTENT_STATUS_DELAYED);874 875 newes.es_lblk = lblk;876 newes.es_len = len;877 ext4_es_store_pblock_status(&newes, pblk, status);878 trace_ext4_es_insert_extent(inode, &newes);879 880 ext4_es_insert_extent_check(inode, &newes);881 882 revise_pending = sbi->s_cluster_ratio > 1 &&883 test_opt(inode->i_sb, DELALLOC) &&884 (status & (EXTENT_STATUS_WRITTEN |885 EXTENT_STATUS_UNWRITTEN));886retry:887 if (err1 && !es1)888 es1 = __es_alloc_extent(true);889 if ((err1 || err2) && !es2)890 es2 = __es_alloc_extent(true);891 if ((err1 || err2 || err3 < 0) && revise_pending && !pr)892 pr = __alloc_pending(true);893 write_lock(&EXT4_I(inode)->i_es_lock);894 895 err1 = __es_remove_extent(inode, lblk, end, &resv_used, es1);896 if (err1 != 0)897 goto error;898 /* Free preallocated extent if it didn't get used. */899 if (es1) {900 if (!es1->es_len)901 __es_free_extent(es1);902 es1 = NULL;903 }904 905 err2 = __es_insert_extent(inode, &newes, es2);906 if (err2 == -ENOMEM && !ext4_es_must_keep(&newes))907 err2 = 0;908 if (err2 != 0)909 goto error;910 /* Free preallocated extent if it didn't get used. */911 if (es2) {912 if (!es2->es_len)913 __es_free_extent(es2);914 es2 = NULL;915 }916 917 if (revise_pending) {918 err3 = __revise_pending(inode, lblk, len, &pr);919 if (err3 < 0)920 goto error;921 if (pr) {922 __free_pending(pr);923 pr = NULL;924 }925 pending = err3;926 }927error:928 write_unlock(&EXT4_I(inode)->i_es_lock);929 /*930 * Reduce the reserved cluster count to reflect successful deferred931 * allocation of delayed allocated clusters or direct allocation of932 * clusters discovered to be delayed allocated. Once allocated, a933 * cluster is not included in the reserved count.934 *935 * When direct allocating (from fallocate, filemap, DIO, or clusters936 * allocated when delalloc has been disabled by ext4_nonda_switch())937 * an extent either 1) contains delayed blocks but start with938 * non-delayed allocated blocks (e.g. hole) or 2) contains non-delayed939 * allocated blocks which belong to delayed allocated clusters when940 * bigalloc feature is enabled, quota has already been claimed by941 * ext4_mb_new_blocks(), so release the quota reservations made for942 * any previously delayed allocated clusters instead of claim them943 * again.944 */945 resv_used += pending;946 if (resv_used)947 ext4_da_update_reserve_space(inode, resv_used,948 flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE);949 950 if (err1 || err2 || err3 < 0)951 goto retry;952 953 ext4_es_print_tree(inode);954 return;955}956 957/*958 * ext4_es_cache_extent() inserts information into the extent status959 * tree if and only if there isn't information about the range in960 * question already.961 */962void ext4_es_cache_extent(struct inode *inode, ext4_lblk_t lblk,963 ext4_lblk_t len, ext4_fsblk_t pblk,964 unsigned int status)965{966 struct extent_status *es;967 struct extent_status newes;968 ext4_lblk_t end = lblk + len - 1;969 970 if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY)971 return;972 973 newes.es_lblk = lblk;974 newes.es_len = len;975 ext4_es_store_pblock_status(&newes, pblk, status);976 trace_ext4_es_cache_extent(inode, &newes);977 978 if (!len)979 return;980 981 BUG_ON(end < lblk);982 983 write_lock(&EXT4_I(inode)->i_es_lock);984 985 es = __es_tree_search(&EXT4_I(inode)->i_es_tree.root, lblk);986 if (!es || es->es_lblk > end)987 __es_insert_extent(inode, &newes, NULL);988 write_unlock(&EXT4_I(inode)->i_es_lock);989}990 991/*992 * ext4_es_lookup_extent() looks up an extent in extent status tree.993 *994 * ext4_es_lookup_extent is called by ext4_map_blocks/ext4_da_map_blocks.995 *996 * Return: 1 on found, 0 on not997 */998int ext4_es_lookup_extent(struct inode *inode, ext4_lblk_t lblk,999 ext4_lblk_t *next_lblk,1000 struct extent_status *es)1001{1002 struct ext4_es_tree *tree;1003 struct ext4_es_stats *stats;1004 struct extent_status *es1 = NULL;1005 struct rb_node *node;1006 int found = 0;1007 1008 if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY)1009 return 0;1010 1011 trace_ext4_es_lookup_extent_enter(inode, lblk);1012 es_debug("lookup extent in block %u\n", lblk);1013 1014 tree = &EXT4_I(inode)->i_es_tree;1015 read_lock(&EXT4_I(inode)->i_es_lock);1016 1017 /* find extent in cache firstly */1018 es->es_lblk = es->es_len = es->es_pblk = 0;1019 es1 = READ_ONCE(tree->cache_es);1020 if (es1 && in_range(lblk, es1->es_lblk, es1->es_len)) {1021 es_debug("%u cached by [%u/%u)\n",1022 lblk, es1->es_lblk, es1->es_len);1023 found = 1;1024 goto out;1025 }1026 1027 node = tree->root.rb_node;1028 while (node) {1029 es1 = rb_entry(node, struct extent_status, rb_node);1030 if (lblk < es1->es_lblk)1031 node = node->rb_left;1032 else if (lblk > ext4_es_end(es1))1033 node = node->rb_right;1034 else {1035 found = 1;1036 break;1037 }1038 }1039 1040out:1041 stats = &EXT4_SB(inode->i_sb)->s_es_stats;1042 if (found) {1043 BUG_ON(!es1);1044 es->es_lblk = es1->es_lblk;1045 es->es_len = es1->es_len;1046 es->es_pblk = es1->es_pblk;1047 if (!ext4_es_is_referenced(es1))1048 ext4_es_set_referenced(es1);1049 percpu_counter_inc(&stats->es_stats_cache_hits);1050 if (next_lblk) {1051 node = rb_next(&es1->rb_node);1052 if (node) {1053 es1 = rb_entry(node, struct extent_status,1054 rb_node);1055 *next_lblk = es1->es_lblk;1056 } else1057 *next_lblk = 0;1058 }1059 } else {1060 percpu_counter_inc(&stats->es_stats_cache_misses);1061 }1062 1063 read_unlock(&EXT4_I(inode)->i_es_lock);1064 1065 trace_ext4_es_lookup_extent_exit(inode, es, found);1066 return found;1067}1068 1069struct rsvd_count {1070 int ndelayed;1071 bool first_do_lblk_found;1072 ext4_lblk_t first_do_lblk;1073 ext4_lblk_t last_do_lblk;1074 struct extent_status *left_es;1075 bool partial;1076 ext4_lblk_t lclu;1077};1078 1079/*1080 * init_rsvd - initialize reserved count data before removing block range1081 * in file from extent status tree1082 *1083 * @inode - file containing range1084 * @lblk - first block in range1085 * @es - pointer to first extent in range1086 * @rc - pointer to reserved count data1087 *1088 * Assumes es is not NULL1089 */1090static void init_rsvd(struct inode *inode, ext4_lblk_t lblk,1091 struct extent_status *es, struct rsvd_count *rc)1092{1093 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);1094 struct rb_node *node;1095 1096 rc->ndelayed = 0;1097 1098 /*1099 * for bigalloc, note the first delayed block in the range has not1100 * been found, record the extent containing the block to the left of1101 * the region to be removed, if any, and note that there's no partial1102 * cluster to track1103 */1104 if (sbi->s_cluster_ratio > 1) {1105 rc->first_do_lblk_found = false;1106 if (lblk > es->es_lblk) {1107 rc->left_es = es;1108 } else {1109 node = rb_prev(&es->rb_node);1110 rc->left_es = node ? rb_entry(node,1111 struct extent_status,1112 rb_node) : NULL;1113 }1114 rc->partial = false;1115 }1116}1117 1118/*1119 * count_rsvd - count the clusters containing delayed blocks in a range1120 * within an extent and add to the running tally in rsvd_count1121 *1122 * @inode - file containing extent1123 * @lblk - first block in range1124 * @len - length of range in blocks1125 * @es - pointer to extent containing clusters to be counted1126 * @rc - pointer to reserved count data1127 *1128 * Tracks partial clusters found at the beginning and end of extents so1129 * they aren't overcounted when they span adjacent extents1130 */1131static void count_rsvd(struct inode *inode, ext4_lblk_t lblk, long len,1132 struct extent_status *es, struct rsvd_count *rc)1133{1134 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);1135 ext4_lblk_t i, end, nclu;1136 1137 if (!ext4_es_is_delayed(es))1138 return;1139 1140 WARN_ON(len <= 0);1141 1142 if (sbi->s_cluster_ratio == 1) {1143 rc->ndelayed += (int) len;1144 return;1145 }1146 1147 /* bigalloc */1148 1149 i = (lblk < es->es_lblk) ? es->es_lblk : lblk;1150 end = lblk + (ext4_lblk_t) len - 1;1151 end = (end > ext4_es_end(es)) ? ext4_es_end(es) : end;1152 1153 /* record the first block of the first delayed extent seen */1154 if (!rc->first_do_lblk_found) {1155 rc->first_do_lblk = i;1156 rc->first_do_lblk_found = true;1157 }1158 1159 /* update the last lblk in the region seen so far */1160 rc->last_do_lblk = end;1161 1162 /*1163 * if we're tracking a partial cluster and the current extent1164 * doesn't start with it, count it and stop tracking1165 */1166 if (rc->partial && (rc->lclu != EXT4_B2C(sbi, i))) {1167 rc->ndelayed++;1168 rc->partial = false;1169 }1170 1171 /*1172 * if the first cluster doesn't start on a cluster boundary but1173 * ends on one, count it1174 */1175 if (EXT4_LBLK_COFF(sbi, i) != 0) {1176 if (end >= EXT4_LBLK_CFILL(sbi, i)) {1177 rc->ndelayed++;1178 rc->partial = false;1179 i = EXT4_LBLK_CFILL(sbi, i) + 1;1180 }1181 }1182 1183 /*1184 * if the current cluster starts on a cluster boundary, count the1185 * number of whole delayed clusters in the extent1186 */1187 if ((i + sbi->s_cluster_ratio - 1) <= end) {1188 nclu = (end - i + 1) >> sbi->s_cluster_bits;1189 rc->ndelayed += nclu;1190 i += nclu << sbi->s_cluster_bits;1191 }1192 1193 /*1194 * start tracking a partial cluster if there's a partial at the end1195 * of the current extent and we're not already tracking one1196 */1197 if (!rc->partial && i <= end) {1198 rc->partial = true;1199 rc->lclu = EXT4_B2C(sbi, i);1200 }1201}1202 1203/*1204 * __pr_tree_search - search for a pending cluster reservation1205 *1206 * @root - root of pending reservation tree1207 * @lclu - logical cluster to search for1208 *1209 * Returns the pending reservation for the cluster identified by @lclu1210 * if found. If not, returns a reservation for the next cluster if any,1211 * and if not, returns NULL.1212 */1213static struct pending_reservation *__pr_tree_search(struct rb_root *root,1214 ext4_lblk_t lclu)1215{1216 struct rb_node *node = root->rb_node;1217 struct pending_reservation *pr = NULL;1218 1219 while (node) {1220 pr = rb_entry(node, struct pending_reservation, rb_node);1221 if (lclu < pr->lclu)1222 node = node->rb_left;1223 else if (lclu > pr->lclu)1224 node = node->rb_right;1225 else1226 return pr;1227 }1228 if (pr && lclu < pr->lclu)1229 return pr;1230 if (pr && lclu > pr->lclu) {1231 node = rb_next(&pr->rb_node);1232 return node ? rb_entry(node, struct pending_reservation,1233 rb_node) : NULL;1234 }1235 return NULL;1236}1237 1238/*1239 * get_rsvd - calculates and returns the number of cluster reservations to be1240 * released when removing a block range from the extent status tree1241 * and releases any pending reservations within the range1242 *1243 * @inode - file containing block range1244 * @end - last block in range1245 * @right_es - pointer to extent containing next block beyond end or NULL1246 * @rc - pointer to reserved count data1247 *1248 * The number of reservations to be released is equal to the number of1249 * clusters containing delayed blocks within the range, minus the number of1250 * clusters still containing delayed blocks at the ends of the range, and1251 * minus the number of pending reservations within the range.1252 */1253static unsigned int get_rsvd(struct inode *inode, ext4_lblk_t end,1254 struct extent_status *right_es,1255 struct rsvd_count *rc)1256{1257 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);1258 struct pending_reservation *pr;1259 struct ext4_pending_tree *tree = &EXT4_I(inode)->i_pending_tree;1260 struct rb_node *node;1261 ext4_lblk_t first_lclu, last_lclu;1262 bool left_delayed, right_delayed, count_pending;1263 struct extent_status *es;1264 1265 if (sbi->s_cluster_ratio > 1) {1266 /* count any remaining partial cluster */1267 if (rc->partial)1268 rc->ndelayed++;1269 1270 if (rc->ndelayed == 0)1271 return 0;1272 1273 first_lclu = EXT4_B2C(sbi, rc->first_do_lblk);1274 last_lclu = EXT4_B2C(sbi, rc->last_do_lblk);1275 1276 /*1277 * decrease the delayed count by the number of clusters at the1278 * ends of the range that still contain delayed blocks -1279 * these clusters still need to be reserved1280 */1281 left_delayed = right_delayed = false;1282 1283 es = rc->left_es;1284 while (es && ext4_es_end(es) >=1285 EXT4_LBLK_CMASK(sbi, rc->first_do_lblk)) {1286 if (ext4_es_is_delayed(es)) {1287 rc->ndelayed--;1288 left_delayed = true;1289 break;1290 }1291 node = rb_prev(&es->rb_node);1292 if (!node)1293 break;1294 es = rb_entry(node, struct extent_status, rb_node);1295 }1296 if (right_es && (!left_delayed || first_lclu != last_lclu)) {1297 if (end < ext4_es_end(right_es)) {1298 es = right_es;1299 } else {1300 node = rb_next(&right_es->rb_node);1301 es = node ? rb_entry(node, struct extent_status,1302 rb_node) : NULL;1303 }1304 while (es && es->es_lblk <=1305 EXT4_LBLK_CFILL(sbi, rc->last_do_lblk)) {1306 if (ext4_es_is_delayed(es)) {1307 rc->ndelayed--;1308 right_delayed = true;1309 break;1310 }1311 node = rb_next(&es->rb_node);1312 if (!node)1313 break;1314 es = rb_entry(node, struct extent_status,1315 rb_node);1316 }1317 }1318 1319 /*1320 * Determine the block range that should be searched for1321 * pending reservations, if any. Clusters on the ends of the1322 * original removed range containing delayed blocks are1323 * excluded. They've already been accounted for and it's not1324 * possible to determine if an associated pending reservation1325 * should be released with the information available in the1326 * extents status tree.1327 */1328 if (first_lclu == last_lclu) {1329 if (left_delayed | right_delayed)1330 count_pending = false;1331 else1332 count_pending = true;1333 } else {1334 if (left_delayed)1335 first_lclu++;1336 if (right_delayed)1337 last_lclu--;1338 if (first_lclu <= last_lclu)1339 count_pending = true;1340 else1341 count_pending = false;1342 }1343 1344 /*1345 * a pending reservation found between first_lclu and last_lclu1346 * represents an allocated cluster that contained at least one1347 * delayed block, so the delayed total must be reduced by one1348 * for each pending reservation found and released1349 */1350 if (count_pending) {1351 pr = __pr_tree_search(&tree->root, first_lclu);1352 while (pr && pr->lclu <= last_lclu) {1353 rc->ndelayed--;1354 node = rb_next(&pr->rb_node);1355 rb_erase(&pr->rb_node, &tree->root);1356 __free_pending(pr);1357 if (!node)1358 break;1359 pr = rb_entry(node, struct pending_reservation,1360 rb_node);1361 }1362 }1363 }1364 return rc->ndelayed;1365}1366 1367 1368/*1369 * __es_remove_extent - removes block range from extent status tree1370 *1371 * @inode - file containing range1372 * @lblk - first block in range1373 * @end - last block in range1374 * @reserved - number of cluster reservations released1375 * @prealloc - pre-allocated es to avoid memory allocation failures1376 *1377 * If @reserved is not NULL and delayed allocation is enabled, counts1378 * block/cluster reservations freed by removing range and if bigalloc1379 * enabled cancels pending reservations as needed. Returns 0 on success,1380 * error code on failure.1381 */1382static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk,1383 ext4_lblk_t end, int *reserved,1384 struct extent_status *prealloc)1385{1386 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;1387 struct rb_node *node;1388 struct extent_status *es;1389 struct extent_status orig_es;1390 ext4_lblk_t len1, len2;1391 ext4_fsblk_t block;1392 int err = 0;1393 bool count_reserved = true;1394 struct rsvd_count rc;1395 1396 if (reserved == NULL || !test_opt(inode->i_sb, DELALLOC))1397 count_reserved = false;1398 1399 es = __es_tree_search(&tree->root, lblk);1400 if (!es)1401 goto out;1402 if (es->es_lblk > end)1403 goto out;1404 1405 /* Simply invalidate cache_es. */1406 tree->cache_es = NULL;1407 if (count_reserved)1408 init_rsvd(inode, lblk, es, &rc);1409 1410 orig_es.es_lblk = es->es_lblk;1411 orig_es.es_len = es->es_len;1412 orig_es.es_pblk = es->es_pblk;1413 1414 len1 = lblk > es->es_lblk ? lblk - es->es_lblk : 0;1415 len2 = ext4_es_end(es) > end ? ext4_es_end(es) - end : 0;1416 if (len1 > 0)1417 es->es_len = len1;1418 if (len2 > 0) {1419 if (len1 > 0) {1420 struct extent_status newes;1421 1422 newes.es_lblk = end + 1;1423 newes.es_len = len2;1424 block = 0x7FDEADBEEFULL;1425 if (ext4_es_is_written(&orig_es) ||1426 ext4_es_is_unwritten(&orig_es))1427 block = ext4_es_pblock(&orig_es) +1428 orig_es.es_len - len2;1429 ext4_es_store_pblock_status(&newes, block,1430 ext4_es_status(&orig_es));1431 err = __es_insert_extent(inode, &newes, prealloc);1432 if (err) {1433 if (!ext4_es_must_keep(&newes))1434 return 0;1435 1436 es->es_lblk = orig_es.es_lblk;1437 es->es_len = orig_es.es_len;1438 goto out;1439 }1440 } else {1441 es->es_lblk = end + 1;1442 es->es_len = len2;1443 if (ext4_es_is_written(es) ||1444 ext4_es_is_unwritten(es)) {1445 block = orig_es.es_pblk + orig_es.es_len - len2;1446 ext4_es_store_pblock(es, block);1447 }1448 }1449 if (count_reserved)1450 count_rsvd(inode, orig_es.es_lblk + len1,1451 orig_es.es_len - len1 - len2, &orig_es, &rc);1452 goto out_get_reserved;1453 }1454 1455 if (len1 > 0) {1456 if (count_reserved)1457 count_rsvd(inode, lblk, orig_es.es_len - len1,1458 &orig_es, &rc);1459 node = rb_next(&es->rb_node);1460 if (node)1461 es = rb_entry(node, struct extent_status, rb_node);1462 else1463 es = NULL;1464 }1465 1466 while (es && ext4_es_end(es) <= end) {1467 if (count_reserved)1468 count_rsvd(inode, es->es_lblk, es->es_len, es, &rc);1469 node = rb_next(&es->rb_node);1470 rb_erase(&es->rb_node, &tree->root);1471 ext4_es_free_extent(inode, es);1472 if (!node) {1473 es = NULL;1474 break;1475 }1476 es = rb_entry(node, struct extent_status, rb_node);1477 }1478 1479 if (es && es->es_lblk < end + 1) {1480 ext4_lblk_t orig_len = es->es_len;1481 1482 len1 = ext4_es_end(es) - end;1483 if (count_reserved)1484 count_rsvd(inode, es->es_lblk, orig_len - len1,1485 es, &rc);1486 es->es_lblk = end + 1;1487 es->es_len = len1;1488 if (ext4_es_is_written(es) || ext4_es_is_unwritten(es)) {1489 block = es->es_pblk + orig_len - len1;1490 ext4_es_store_pblock(es, block);1491 }1492 }1493 1494out_get_reserved:1495 if (count_reserved)1496 *reserved = get_rsvd(inode, end, es, &rc);1497out:1498 return err;1499}1500 1501/*1502 * ext4_es_remove_extent - removes block range from extent status tree1503 *1504 * @inode - file containing range1505 * @lblk - first block in range1506 * @len - number of blocks to remove1507 *1508 * Reduces block/cluster reservation count and for bigalloc cancels pending1509 * reservations as needed.1510 */1511void ext4_es_remove_extent(struct inode *inode, ext4_lblk_t lblk,1512 ext4_lblk_t len)1513{1514 ext4_lblk_t end;1515 int err = 0;1516 int reserved = 0;1517 struct extent_status *es = NULL;1518 1519 if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY)1520 return;1521 1522 trace_ext4_es_remove_extent(inode, lblk, len);1523 es_debug("remove [%u/%u) from extent status tree of inode %lu\n",1524 lblk, len, inode->i_ino);1525 1526 if (!len)1527 return;1528 1529 end = lblk + len - 1;1530 BUG_ON(end < lblk);1531 1532retry:1533 if (err && !es)1534 es = __es_alloc_extent(true);1535 /*1536 * ext4_clear_inode() depends on us taking i_es_lock unconditionally1537 * so that we are sure __es_shrink() is done with the inode before it1538 * is reclaimed.1539 */1540 write_lock(&EXT4_I(inode)->i_es_lock);1541 err = __es_remove_extent(inode, lblk, end, &reserved, es);1542 /* Free preallocated extent if it didn't get used. */1543 if (es) {1544 if (!es->es_len)1545 __es_free_extent(es);1546 es = NULL;1547 }1548 write_unlock(&EXT4_I(inode)->i_es_lock);1549 if (err)1550 goto retry;1551 1552 ext4_es_print_tree(inode);1553 ext4_da_release_space(inode, reserved);1554 return;1555}1556 1557static int __es_shrink(struct ext4_sb_info *sbi, int nr_to_scan,1558 struct ext4_inode_info *locked_ei)1559{1560 struct ext4_inode_info *ei;1561 struct ext4_es_stats *es_stats;1562 ktime_t start_time;1563 u64 scan_time;1564 int nr_to_walk;1565 int nr_shrunk = 0;1566 int retried = 0, nr_skipped = 0;1567 1568 es_stats = &sbi->s_es_stats;1569 start_time = ktime_get();1570 1571retry:1572 spin_lock(&sbi->s_es_lock);1573 nr_to_walk = sbi->s_es_nr_inode;1574 while (nr_to_walk-- > 0) {1575 if (list_empty(&sbi->s_es_list)) {1576 spin_unlock(&sbi->s_es_lock);1577 goto out;1578 }1579 ei = list_first_entry(&sbi->s_es_list, struct ext4_inode_info,1580 i_es_list);1581 /* Move the inode to the tail */1582 list_move_tail(&ei->i_es_list, &sbi->s_es_list);1583 1584 /*1585 * Normally we try hard to avoid shrinking precached inodes,1586 * but we will as a last resort.1587 */1588 if (!retried && ext4_test_inode_state(&ei->vfs_inode,1589 EXT4_STATE_EXT_PRECACHED)) {1590 nr_skipped++;1591 continue;1592 }1593 1594 if (ei == locked_ei || !write_trylock(&ei->i_es_lock)) {1595 nr_skipped++;1596 continue;1597 }1598 /*1599 * Now we hold i_es_lock which protects us from inode reclaim1600 * freeing inode under us1601 */1602 spin_unlock(&sbi->s_es_lock);1603 1604 nr_shrunk += es_reclaim_extents(ei, &nr_to_scan);1605 write_unlock(&ei->i_es_lock);1606 1607 if (nr_to_scan <= 0)1608 goto out;1609 spin_lock(&sbi->s_es_lock);1610 }1611 spin_unlock(&sbi->s_es_lock);1612 1613 /*1614 * If we skipped any inodes, and we weren't able to make any1615 * forward progress, try again to scan precached inodes.1616 */1617 if ((nr_shrunk == 0) && nr_skipped && !retried) {1618 retried++;1619 goto retry;1620 }1621 1622 if (locked_ei && nr_shrunk == 0)1623 nr_shrunk = es_reclaim_extents(locked_ei, &nr_to_scan);1624 1625out:1626 scan_time = ktime_to_ns(ktime_sub(ktime_get(), start_time));1627 if (likely(es_stats->es_stats_scan_time))1628 es_stats->es_stats_scan_time = (scan_time +1629 es_stats->es_stats_scan_time*3) / 4;1630 else1631 es_stats->es_stats_scan_time = scan_time;1632 if (scan_time > es_stats->es_stats_max_scan_time)1633 es_stats->es_stats_max_scan_time = scan_time;1634 if (likely(es_stats->es_stats_shrunk))1635 es_stats->es_stats_shrunk = (nr_shrunk +1636 es_stats->es_stats_shrunk*3) / 4;1637 else1638 es_stats->es_stats_shrunk = nr_shrunk;1639 1640 trace_ext4_es_shrink(sbi->s_sb, nr_shrunk, scan_time,1641 nr_skipped, retried);1642 return nr_shrunk;1643}1644 1645static unsigned long ext4_es_count(struct shrinker *shrink,1646 struct shrink_control *sc)1647{1648 unsigned long nr;1649 struct ext4_sb_info *sbi;1650 1651 sbi = shrink->private_data;1652 nr = percpu_counter_read_positive(&sbi->s_es_stats.es_stats_shk_cnt);1653 trace_ext4_es_shrink_count(sbi->s_sb, sc->nr_to_scan, nr);1654 return nr;1655}1656 1657static unsigned long ext4_es_scan(struct shrinker *shrink,1658 struct shrink_control *sc)1659{1660 struct ext4_sb_info *sbi = shrink->private_data;1661 int nr_to_scan = sc->nr_to_scan;1662 int ret, nr_shrunk;1663 1664 ret = percpu_counter_read_positive(&sbi->s_es_stats.es_stats_shk_cnt);1665 trace_ext4_es_shrink_scan_enter(sbi->s_sb, nr_to_scan, ret);1666 1667 nr_shrunk = __es_shrink(sbi, nr_to_scan, NULL);1668 1669 ret = percpu_counter_read_positive(&sbi->s_es_stats.es_stats_shk_cnt);1670 trace_ext4_es_shrink_scan_exit(sbi->s_sb, nr_shrunk, ret);1671 return nr_shrunk;1672}1673 1674int ext4_seq_es_shrinker_info_show(struct seq_file *seq, void *v)1675{1676 struct ext4_sb_info *sbi = EXT4_SB((struct super_block *) seq->private);1677 struct ext4_es_stats *es_stats = &sbi->s_es_stats;1678 struct ext4_inode_info *ei, *max = NULL;1679 unsigned int inode_cnt = 0;1680 1681 if (v != SEQ_START_TOKEN)1682 return 0;1683 1684 /* here we just find an inode that has the max nr. of objects */1685 spin_lock(&sbi->s_es_lock);1686 list_for_each_entry(ei, &sbi->s_es_list, i_es_list) {1687 inode_cnt++;1688 if (max && max->i_es_all_nr < ei->i_es_all_nr)1689 max = ei;1690 else if (!max)1691 max = ei;1692 }1693 spin_unlock(&sbi->s_es_lock);1694 1695 seq_printf(seq, "stats:\n %lld objects\n %lld reclaimable objects\n",1696 percpu_counter_sum_positive(&es_stats->es_stats_all_cnt),1697 percpu_counter_sum_positive(&es_stats->es_stats_shk_cnt));1698 seq_printf(seq, " %lld/%lld cache hits/misses\n",1699 percpu_counter_sum_positive(&es_stats->es_stats_cache_hits),1700 percpu_counter_sum_positive(&es_stats->es_stats_cache_misses));1701 if (inode_cnt)1702 seq_printf(seq, " %d inodes on list\n", inode_cnt);1703 1704 seq_printf(seq, "average:\n %llu us scan time\n",1705 div_u64(es_stats->es_stats_scan_time, 1000));1706 seq_printf(seq, " %lu shrunk objects\n", es_stats->es_stats_shrunk);1707 if (inode_cnt)1708 seq_printf(seq,1709 "maximum:\n %lu inode (%u objects, %u reclaimable)\n"1710 " %llu us max scan time\n",1711 max->vfs_inode.i_ino, max->i_es_all_nr, max->i_es_shk_nr,1712 div_u64(es_stats->es_stats_max_scan_time, 1000));1713 1714 return 0;1715}1716 1717int ext4_es_register_shrinker(struct ext4_sb_info *sbi)1718{1719 int err;1720 1721 /* Make sure we have enough bits for physical block number */1722 BUILD_BUG_ON(ES_SHIFT < 48);1723 INIT_LIST_HEAD(&sbi->s_es_list);1724 sbi->s_es_nr_inode = 0;1725 spin_lock_init(&sbi->s_es_lock);1726 sbi->s_es_stats.es_stats_shrunk = 0;1727 err = percpu_counter_init(&sbi->s_es_stats.es_stats_cache_hits, 0,1728 GFP_KERNEL);1729 if (err)1730 return err;1731 err = percpu_counter_init(&sbi->s_es_stats.es_stats_cache_misses, 0,1732 GFP_KERNEL);1733 if (err)1734 goto err1;1735 sbi->s_es_stats.es_stats_scan_time = 0;1736 sbi->s_es_stats.es_stats_max_scan_time = 0;1737 err = percpu_counter_init(&sbi->s_es_stats.es_stats_all_cnt, 0, GFP_KERNEL);1738 if (err)1739 goto err2;1740 err = percpu_counter_init(&sbi->s_es_stats.es_stats_shk_cnt, 0, GFP_KERNEL);1741 if (err)1742 goto err3;1743 1744 sbi->s_es_shrinker = shrinker_alloc(0, "ext4-es:%s", sbi->s_sb->s_id);1745 if (!sbi->s_es_shrinker) {1746 err = -ENOMEM;1747 goto err4;1748 }1749 1750 sbi->s_es_shrinker->scan_objects = ext4_es_scan;1751 sbi->s_es_shrinker->count_objects = ext4_es_count;1752 sbi->s_es_shrinker->private_data = sbi;1753 1754 shrinker_register(sbi->s_es_shrinker);1755 1756 return 0;1757err4:1758 percpu_counter_destroy(&sbi->s_es_stats.es_stats_shk_cnt);1759err3:1760 percpu_counter_destroy(&sbi->s_es_stats.es_stats_all_cnt);1761err2:1762 percpu_counter_destroy(&sbi->s_es_stats.es_stats_cache_misses);1763err1:1764 percpu_counter_destroy(&sbi->s_es_stats.es_stats_cache_hits);1765 return err;1766}1767 1768void ext4_es_unregister_shrinker(struct ext4_sb_info *sbi)1769{1770 percpu_counter_destroy(&sbi->s_es_stats.es_stats_cache_hits);1771 percpu_counter_destroy(&sbi->s_es_stats.es_stats_cache_misses);1772 percpu_counter_destroy(&sbi->s_es_stats.es_stats_all_cnt);1773 percpu_counter_destroy(&sbi->s_es_stats.es_stats_shk_cnt);1774 shrinker_free(sbi->s_es_shrinker);1775}1776 1777/*1778 * Shrink extents in given inode from ei->i_es_shrink_lblk till end. Scan at1779 * most *nr_to_scan extents, update *nr_to_scan accordingly.1780 *1781 * Return 0 if we hit end of tree / interval, 1 if we exhausted nr_to_scan.1782 * Increment *nr_shrunk by the number of reclaimed extents. Also update1783 * ei->i_es_shrink_lblk to where we should continue scanning.1784 */1785static int es_do_reclaim_extents(struct ext4_inode_info *ei, ext4_lblk_t end,1786 int *nr_to_scan, int *nr_shrunk)1787{1788 struct inode *inode = &ei->vfs_inode;1789 struct ext4_es_tree *tree = &ei->i_es_tree;1790 struct extent_status *es;1791 struct rb_node *node;1792 1793 es = __es_tree_search(&tree->root, ei->i_es_shrink_lblk);1794 if (!es)1795 goto out_wrap;1796 1797 while (*nr_to_scan > 0) {1798 if (es->es_lblk > end) {1799 ei->i_es_shrink_lblk = end + 1;1800 return 0;1801 }1802 1803 (*nr_to_scan)--;1804 node = rb_next(&es->rb_node);1805 1806 if (ext4_es_must_keep(es))1807 goto next;1808 if (ext4_es_is_referenced(es)) {1809 ext4_es_clear_referenced(es);1810 goto next;1811 }1812 1813 rb_erase(&es->rb_node, &tree->root);1814 ext4_es_free_extent(inode, es);1815 (*nr_shrunk)++;1816next:1817 if (!node)1818 goto out_wrap;1819 es = rb_entry(node, struct extent_status, rb_node);1820 }1821 ei->i_es_shrink_lblk = es->es_lblk;1822 return 1;1823out_wrap:1824 ei->i_es_shrink_lblk = 0;1825 return 0;1826}1827 1828static int es_reclaim_extents(struct ext4_inode_info *ei, int *nr_to_scan)1829{1830 struct inode *inode = &ei->vfs_inode;1831 int nr_shrunk = 0;1832 ext4_lblk_t start = ei->i_es_shrink_lblk;1833 static DEFINE_RATELIMIT_STATE(_rs, DEFAULT_RATELIMIT_INTERVAL,1834 DEFAULT_RATELIMIT_BURST);1835 1836 if (ei->i_es_shk_nr == 0)1837 return 0;1838 1839 if (ext4_test_inode_state(inode, EXT4_STATE_EXT_PRECACHED) &&1840 __ratelimit(&_rs))1841 ext4_warning(inode->i_sb, "forced shrink of precached extents");1842 1843 if (!es_do_reclaim_extents(ei, EXT_MAX_BLOCKS, nr_to_scan, &nr_shrunk) &&1844 start != 0)1845 es_do_reclaim_extents(ei, start - 1, nr_to_scan, &nr_shrunk);1846 1847 ei->i_es_tree.cache_es = NULL;1848 return nr_shrunk;1849}1850 1851/*1852 * Called to support EXT4_IOC_CLEAR_ES_CACHE. We can only remove1853 * discretionary entries from the extent status cache. (Some entries1854 * must be present for proper operations.)1855 */1856void ext4_clear_inode_es(struct inode *inode)1857{1858 struct ext4_inode_info *ei = EXT4_I(inode);1859 struct extent_status *es;1860 struct ext4_es_tree *tree;1861 struct rb_node *node;1862 1863 write_lock(&ei->i_es_lock);1864 tree = &EXT4_I(inode)->i_es_tree;1865 tree->cache_es = NULL;1866 node = rb_first(&tree->root);1867 while (node) {1868 es = rb_entry(node, struct extent_status, rb_node);1869 node = rb_next(node);1870 if (!ext4_es_must_keep(es)) {1871 rb_erase(&es->rb_node, &tree->root);1872 ext4_es_free_extent(inode, es);1873 }1874 }1875 ext4_clear_inode_state(inode, EXT4_STATE_EXT_PRECACHED);1876 write_unlock(&ei->i_es_lock);1877}1878 1879#ifdef ES_DEBUG__1880static void ext4_print_pending_tree(struct inode *inode)1881{1882 struct ext4_pending_tree *tree;1883 struct rb_node *node;1884 struct pending_reservation *pr;1885 1886 printk(KERN_DEBUG "pending reservations for inode %lu:", inode->i_ino);1887 tree = &EXT4_I(inode)->i_pending_tree;1888 node = rb_first(&tree->root);1889 while (node) {1890 pr = rb_entry(node, struct pending_reservation, rb_node);1891 printk(KERN_DEBUG " %u", pr->lclu);1892 node = rb_next(node);1893 }1894 printk(KERN_DEBUG "\n");1895}1896#else1897#define ext4_print_pending_tree(inode)1898#endif1899 1900int __init ext4_init_pending(void)1901{1902 ext4_pending_cachep = KMEM_CACHE(pending_reservation, SLAB_RECLAIM_ACCOUNT);1903 if (ext4_pending_cachep == NULL)1904 return -ENOMEM;1905 return 0;1906}1907 1908void ext4_exit_pending(void)1909{1910 kmem_cache_destroy(ext4_pending_cachep);1911}1912 1913void ext4_init_pending_tree(struct ext4_pending_tree *tree)1914{1915 tree->root = RB_ROOT;1916}1917 1918/*1919 * __get_pending - retrieve a pointer to a pending reservation1920 *1921 * @inode - file containing the pending cluster reservation1922 * @lclu - logical cluster of interest1923 *1924 * Returns a pointer to a pending reservation if it's a member of1925 * the set, and NULL if not. Must be called holding i_es_lock.1926 */1927static struct pending_reservation *__get_pending(struct inode *inode,1928 ext4_lblk_t lclu)1929{1930 struct ext4_pending_tree *tree;1931 struct rb_node *node;1932 struct pending_reservation *pr = NULL;1933 1934 tree = &EXT4_I(inode)->i_pending_tree;1935 node = (&tree->root)->rb_node;1936 1937 while (node) {1938 pr = rb_entry(node, struct pending_reservation, rb_node);1939 if (lclu < pr->lclu)1940 node = node->rb_left;1941 else if (lclu > pr->lclu)1942 node = node->rb_right;1943 else if (lclu == pr->lclu)1944 return pr;1945 }1946 return NULL;1947}1948 1949/*1950 * __insert_pending - adds a pending cluster reservation to the set of1951 * pending reservations1952 *1953 * @inode - file containing the cluster1954 * @lblk - logical block in the cluster to be added1955 * @prealloc - preallocated pending entry1956 *1957 * Returns 1 on successful insertion and -ENOMEM on failure. If the1958 * pending reservation is already in the set, returns successfully.1959 */1960static int __insert_pending(struct inode *inode, ext4_lblk_t lblk,1961 struct pending_reservation **prealloc)1962{1963 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);1964 struct ext4_pending_tree *tree = &EXT4_I(inode)->i_pending_tree;1965 struct rb_node **p = &tree->root.rb_node;1966 struct rb_node *parent = NULL;1967 struct pending_reservation *pr;1968 ext4_lblk_t lclu;1969 int ret = 0;1970 1971 lclu = EXT4_B2C(sbi, lblk);1972 /* search to find parent for insertion */1973 while (*p) {1974 parent = *p;1975 pr = rb_entry(parent, struct pending_reservation, rb_node);1976 1977 if (lclu < pr->lclu) {1978 p = &(*p)->rb_left;1979 } else if (lclu > pr->lclu) {1980 p = &(*p)->rb_right;1981 } else {1982 /* pending reservation already inserted */1983 goto out;1984 }1985 }1986 1987 if (likely(*prealloc == NULL)) {1988 pr = __alloc_pending(false);1989 if (!pr) {1990 ret = -ENOMEM;1991 goto out;1992 }1993 } else {1994 pr = *prealloc;1995 *prealloc = NULL;1996 }1997 pr->lclu = lclu;1998 1999 rb_link_node(&pr->rb_node, parent, p);2000 rb_insert_color(&pr->rb_node, &tree->root);2001 ret = 1;2002 2003out:2004 return ret;2005}2006 2007/*2008 * __remove_pending - removes a pending cluster reservation from the set2009 * of pending reservations2010 *2011 * @inode - file containing the cluster2012 * @lblk - logical block in the pending cluster reservation to be removed2013 *2014 * Returns successfully if pending reservation is not a member of the set.2015 */2016static void __remove_pending(struct inode *inode, ext4_lblk_t lblk)2017{2018 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);2019 struct pending_reservation *pr;2020 struct ext4_pending_tree *tree;2021 2022 pr = __get_pending(inode, EXT4_B2C(sbi, lblk));2023 if (pr != NULL) {2024 tree = &EXT4_I(inode)->i_pending_tree;2025 rb_erase(&pr->rb_node, &tree->root);2026 __free_pending(pr);2027 }2028}2029 2030/*2031 * ext4_remove_pending - removes a pending cluster reservation from the set2032 * of pending reservations2033 *2034 * @inode - file containing the cluster2035 * @lblk - logical block in the pending cluster reservation to be removed2036 *2037 * Locking for external use of __remove_pending.2038 */2039void ext4_remove_pending(struct inode *inode, ext4_lblk_t lblk)2040{2041 struct ext4_inode_info *ei = EXT4_I(inode);2042 2043 write_lock(&ei->i_es_lock);2044 __remove_pending(inode, lblk);2045 write_unlock(&ei->i_es_lock);2046}2047 2048/*2049 * ext4_is_pending - determine whether a cluster has a pending reservation2050 * on it2051 *2052 * @inode - file containing the cluster2053 * @lblk - logical block in the cluster2054 *2055 * Returns true if there's a pending reservation for the cluster in the2056 * set of pending reservations, and false if not.2057 */2058bool ext4_is_pending(struct inode *inode, ext4_lblk_t lblk)2059{2060 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);2061 struct ext4_inode_info *ei = EXT4_I(inode);2062 bool ret;2063 2064 read_lock(&ei->i_es_lock);2065 ret = (bool)(__get_pending(inode, EXT4_B2C(sbi, lblk)) != NULL);2066 read_unlock(&ei->i_es_lock);2067 2068 return ret;2069}2070 2071/*2072 * ext4_es_insert_delayed_extent - adds some delayed blocks to the extents2073 * status tree, adding a pending reservation2074 * where needed2075 *2076 * @inode - file containing the newly added block2077 * @lblk - start logical block to be added2078 * @len - length of blocks to be added2079 * @lclu_allocated/end_allocated - indicates whether a physical cluster has2080 * been allocated for the logical cluster2081 * that contains the start/end block. Note that2082 * end_allocated should always be set to false2083 * if the start and the end block are in the2084 * same cluster2085 */2086void ext4_es_insert_delayed_extent(struct inode *inode, ext4_lblk_t lblk,2087 ext4_lblk_t len, bool lclu_allocated,2088 bool end_allocated)2089{2090 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);2091 struct extent_status newes;2092 ext4_lblk_t end = lblk + len - 1;2093 int err1 = 0, err2 = 0, err3 = 0;2094 struct extent_status *es1 = NULL;2095 struct extent_status *es2 = NULL;2096 struct pending_reservation *pr1 = NULL;2097 struct pending_reservation *pr2 = NULL;2098 2099 if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY)2100 return;2101 2102 es_debug("add [%u/%u) delayed to extent status tree of inode %lu\n",2103 lblk, len, inode->i_ino);2104 if (!len)2105 return;2106 2107 WARN_ON_ONCE((EXT4_B2C(sbi, lblk) == EXT4_B2C(sbi, end)) &&2108 end_allocated);2109 2110 newes.es_lblk = lblk;2111 newes.es_len = len;2112 ext4_es_store_pblock_status(&newes, ~0, EXTENT_STATUS_DELAYED);2113 trace_ext4_es_insert_delayed_extent(inode, &newes, lclu_allocated,2114 end_allocated);2115 2116 ext4_es_insert_extent_check(inode, &newes);2117 2118retry:2119 if (err1 && !es1)2120 es1 = __es_alloc_extent(true);2121 if ((err1 || err2) && !es2)2122 es2 = __es_alloc_extent(true);2123 if (err1 || err2 || err3 < 0) {2124 if (lclu_allocated && !pr1)2125 pr1 = __alloc_pending(true);2126 if (end_allocated && !pr2)2127 pr2 = __alloc_pending(true);2128 }2129 write_lock(&EXT4_I(inode)->i_es_lock);2130 2131 err1 = __es_remove_extent(inode, lblk, end, NULL, es1);2132 if (err1 != 0)2133 goto error;2134 /* Free preallocated extent if it didn't get used. */2135 if (es1) {2136 if (!es1->es_len)2137 __es_free_extent(es1);2138 es1 = NULL;2139 }2140 2141 err2 = __es_insert_extent(inode, &newes, es2);2142 if (err2 != 0)2143 goto error;2144 /* Free preallocated extent if it didn't get used. */2145 if (es2) {2146 if (!es2->es_len)2147 __es_free_extent(es2);2148 es2 = NULL;2149 }2150 2151 if (lclu_allocated) {2152 err3 = __insert_pending(inode, lblk, &pr1);2153 if (err3 < 0)2154 goto error;2155 if (pr1) {2156 __free_pending(pr1);2157 pr1 = NULL;2158 }2159 }2160 if (end_allocated) {2161 err3 = __insert_pending(inode, end, &pr2);2162 if (err3 < 0)2163 goto error;2164 if (pr2) {2165 __free_pending(pr2);2166 pr2 = NULL;2167 }2168 }2169error:2170 write_unlock(&EXT4_I(inode)->i_es_lock);2171 if (err1 || err2 || err3 < 0)2172 goto retry;2173 2174 ext4_es_print_tree(inode);2175 ext4_print_pending_tree(inode);2176 return;2177}2178 2179/*2180 * __revise_pending - makes, cancels, or leaves unchanged pending cluster2181 * reservations for a specified block range depending2182 * upon the presence or absence of delayed blocks2183 * outside the range within clusters at the ends of the2184 * range2185 *2186 * @inode - file containing the range2187 * @lblk - logical block defining the start of range2188 * @len - length of range in blocks2189 * @prealloc - preallocated pending entry2190 *2191 * Used after a newly allocated extent is added to the extents status tree.2192 * Requires that the extents in the range have either written or unwritten2193 * status. Must be called while holding i_es_lock. Returns number of new2194 * inserts pending cluster on insert pendings, returns 0 on remove pendings,2195 * return -ENOMEM on failure.2196 */2197static int __revise_pending(struct inode *inode, ext4_lblk_t lblk,2198 ext4_lblk_t len,2199 struct pending_reservation **prealloc)2200{2201 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);2202 ext4_lblk_t end = lblk + len - 1;2203 ext4_lblk_t first, last;2204 bool f_del = false, l_del = false;2205 int pendings = 0;2206 int ret = 0;2207 2208 if (len == 0)2209 return 0;2210 2211 /*2212 * Two cases - block range within single cluster and block range2213 * spanning two or more clusters. Note that a cluster belonging2214 * to a range starting and/or ending on a cluster boundary is treated2215 * as if it does not contain a delayed extent. The new range may2216 * have allocated space for previously delayed blocks out to the2217 * cluster boundary, requiring that any pre-existing pending2218 * reservation be canceled. Because this code only looks at blocks2219 * outside the range, it should revise pending reservations2220 * correctly even if the extent represented by the range can't be2221 * inserted in the extents status tree due to ENOSPC.2222 */2223 2224 if (EXT4_B2C(sbi, lblk) == EXT4_B2C(sbi, end)) {2225 first = EXT4_LBLK_CMASK(sbi, lblk);2226 if (first != lblk)2227 f_del = __es_scan_range(inode, &ext4_es_is_delayed,2228 first, lblk - 1);2229 if (f_del) {2230 ret = __insert_pending(inode, first, prealloc);2231 if (ret < 0)2232 goto out;2233 pendings += ret;2234 } else {2235 last = EXT4_LBLK_CMASK(sbi, end) +2236 sbi->s_cluster_ratio - 1;2237 if (last != end)2238 l_del = __es_scan_range(inode,2239 &ext4_es_is_delayed,2240 end + 1, last);2241 if (l_del) {2242 ret = __insert_pending(inode, last, prealloc);2243 if (ret < 0)2244 goto out;2245 pendings += ret;2246 } else2247 __remove_pending(inode, last);2248 }2249 } else {2250 first = EXT4_LBLK_CMASK(sbi, lblk);2251 if (first != lblk)2252 f_del = __es_scan_range(inode, &ext4_es_is_delayed,2253 first, lblk - 1);2254 if (f_del) {2255 ret = __insert_pending(inode, first, prealloc);2256 if (ret < 0)2257 goto out;2258 pendings += ret;2259 } else2260 __remove_pending(inode, first);2261 2262 last = EXT4_LBLK_CMASK(sbi, end) + sbi->s_cluster_ratio - 1;2263 if (last != end)2264 l_del = __es_scan_range(inode, &ext4_es_is_delayed,2265 end + 1, last);2266 if (l_del) {2267 ret = __insert_pending(inode, last, prealloc);2268 if (ret < 0)2269 goto out;2270 pendings += ret;2271 } else2272 __remove_pending(inode, last);2273 }2274out:2275 return (ret < 0) ? ret : pendings;2276}2277