1// SPDX-License-Identifier: GPL-2.0
   2/*
   3 *  fs/ext4/extents_status.c
   4 *
   5 * Written by Yongqiang Yang <xiaoqiangnk@gmail.com>
   6 * Modified by
   7 *	Allison Henderson <achender@linux.vnet.ibm.com>
   8 *	Hugh Dickins <hughd@google.com>
   9 *	Zheng Liu <wenqing.lz@taobao.com>
  10 *
  11 * Ext4 extents status tree core functions.
  12 */
  13#include <linux/list_sort.h>
  14#include <linux/proc_fs.h>
  15#include <linux/seq_file.h>
  16#include "ext4.h"
  17
  18#include <trace/events/ext4.h>
  19
  20/*
  21 * According to previous discussion in Ext4 Developer Workshop, we
  22 * will introduce a new structure called io tree to track all extent
  23 * status in order to solve some problems that we have met
  24 * (e.g. Reservation space warning), and provide extent-level locking.
  25 * Delay extent tree is the first step to achieve this goal.  It is
  26 * original built by Yongqiang Yang.  At that time it is called delay
  27 * extent tree, whose goal is only track delayed extents in memory to
  28 * simplify the implementation of fiemap and bigalloc, and introduce
  29 * lseek SEEK_DATA/SEEK_HOLE support.  That is why it is still called
  30 * delay extent tree at the first commit.  But for better understand
  31 * what it does, it has been rename to extent status tree.
  32 *
  33 * Step1:
  34 * Currently the first step has been done.  All delayed extents are
  35 * tracked in the tree.  It maintains the delayed extent when a delayed
  36 * allocation is issued, and the delayed extent is written out or
  37 * invalidated.  Therefore the implementation of fiemap and bigalloc
  38 * are simplified, and SEEK_DATA/SEEK_HOLE are introduced.
  39 *
  40 * The following comment describes the implemenmtation of extent
  41 * status tree and future works.
  42 *
  43 * Step2:
  44 * In this step all extent status are tracked by extent status tree.
  45 * Thus, we can first try to lookup a block mapping in this tree before
  46 * finding it in extent tree.  Hence, single extent cache can be removed
  47 * because extent status tree can do a better job.  Extents in status
  48 * tree are loaded on-demand.  Therefore, the extent status tree may not
  49 * contain all of the extents in a file.  Meanwhile we define a shrinker
  50 * to reclaim memory from extent status tree because fragmented extent
  51 * tree will make status tree cost too much memory.  written/unwritten/-
  52 * hole extents in the tree will be reclaimed by this shrinker when we
  53 * are under high memory pressure.  Delayed extents will not be
  54 * reclimed because fiemap, bigalloc, and seek_data/hole need it.
  55 */
  56
  57/*
  58 * Extent status tree implementation for ext4.
  59 *
  60 *
  61 * ==========================================================================
  62 * Extent status tree tracks all extent status.
  63 *
  64 * 1. Why we need to implement extent status tree?
  65 *
  66 * Without extent status tree, ext4 identifies a delayed extent by looking
  67 * up page cache, this has several deficiencies - complicated, buggy,
  68 * and inefficient code.
  69 *
  70 * FIEMAP, SEEK_HOLE/DATA, bigalloc, and writeout all need to know if a
  71 * block or a range of blocks are belonged to a delayed extent.
  72 *
  73 * Let us have a look at how they do without extent status tree.
  74 *   --	FIEMAP
  75 *	FIEMAP looks up page cache to identify delayed allocations from holes.
  76 *
  77 *   --	SEEK_HOLE/DATA
  78 *	SEEK_HOLE/DATA has the same problem as FIEMAP.
  79 *
  80 *   --	bigalloc
  81 *	bigalloc looks up page cache to figure out if a block is
  82 *	already under delayed allocation or not to determine whether
  83 *	quota reserving is needed for the cluster.
  84 *
  85 *   --	writeout
  86 *	Writeout looks up whole page cache to see if a buffer is
  87 *	mapped, If there are not very many delayed buffers, then it is
  88 *	time consuming.
  89 *
  90 * With extent status tree implementation, FIEMAP, SEEK_HOLE/DATA,
  91 * bigalloc and writeout can figure out if a block or a range of
  92 * blocks is under delayed allocation(belonged to a delayed extent) or
  93 * not by searching the extent tree.
  94 *
  95 *
  96 * ==========================================================================
  97 * 2. Ext4 extent status tree impelmentation
  98 *
  99 *   --	extent
 100 *	A extent is a range of blocks which are contiguous logically and
 101 *	physically.  Unlike extent in extent tree, this extent in ext4 is
 102 *	a in-memory struct, there is no corresponding on-disk data.  There
 103 *	is no limit on length of extent, so an extent can contain as many
 104 *	blocks as they are contiguous logically and physically.
 105 *
 106 *   --	extent status tree
 107 *	Every inode has an extent status tree and all allocation blocks
 108 *	are added to the tree with different status.  The extent in the
 109 *	tree are ordered by logical block no.
 110 *
 111 *   --	operations on a extent status tree
 112 *	There are three important operations on a delayed extent tree: find
 113 *	next extent, adding a extent(a range of blocks) and removing a extent.
 114 *
 115 *   --	race on a extent status tree
 116 *	Extent status tree is protected by inode->i_es_lock.
 117 *
 118 *   --	memory consumption
 119 *      Fragmented extent tree will make extent status tree cost too much
 120 *      memory.  Hence, we will reclaim written/unwritten/hole extents from
 121 *      the tree under a heavy memory pressure.
 122 *
 123 *
 124 * ==========================================================================
 125 * 3. Performance analysis
 126 *
 127 *   --	overhead
 128 *	1. There is a cache extent for write access, so if writes are
 129 *	not very random, adding space operaions are in O(1) time.
 130 *
 131 *   --	gain
 132 *	2. Code is much simpler, more readable, more maintainable and
 133 *	more efficient.
 134 *
 135 *
 136 * ==========================================================================
 137 * 4. TODO list
 138 *
 139 *   -- Refactor delayed space reservation
 140 *
 141 *   -- Extent-level locking
 142 */
 143
 144static struct kmem_cache *ext4_es_cachep;
 145static struct kmem_cache *ext4_pending_cachep;
 146
 147static int __es_insert_extent(struct inode *inode, struct extent_status *newes,
 148			      struct extent_status *prealloc);
 149static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
 150			      ext4_lblk_t end, int *reserved,
 151			      struct extent_status *prealloc);
 152static int es_reclaim_extents(struct ext4_inode_info *ei, int *nr_to_scan);
 153static int __es_shrink(struct ext4_sb_info *sbi, int nr_to_scan,
 154		       struct ext4_inode_info *locked_ei);
 155static int __revise_pending(struct inode *inode, ext4_lblk_t lblk,
 156			    ext4_lblk_t len,
 157			    struct pending_reservation **prealloc);
 158
 159int __init ext4_init_es(void)
 160{
 161	ext4_es_cachep = KMEM_CACHE(extent_status, SLAB_RECLAIM_ACCOUNT);
 
 
 162	if (ext4_es_cachep == NULL)
 163		return -ENOMEM;
 164	return 0;
 165}
 166
 167void ext4_exit_es(void)
 168{
 169	kmem_cache_destroy(ext4_es_cachep);
 170}
 171
 172void ext4_es_init_tree(struct ext4_es_tree *tree)
 173{
 174	tree->root = RB_ROOT;
 175	tree->cache_es = NULL;
 176}
 177
 178#ifdef ES_DEBUG__
 179static void ext4_es_print_tree(struct inode *inode)
 180{
 181	struct ext4_es_tree *tree;
 182	struct rb_node *node;
 183
 184	printk(KERN_DEBUG "status extents for inode %lu:", inode->i_ino);
 185	tree = &EXT4_I(inode)->i_es_tree;
 186	node = rb_first(&tree->root);
 187	while (node) {
 188		struct extent_status *es;
 189		es = rb_entry(node, struct extent_status, rb_node);
 190		printk(KERN_DEBUG " [%u/%u) %llu %x",
 191		       es->es_lblk, es->es_len,
 192		       ext4_es_pblock(es), ext4_es_status(es));
 193		node = rb_next(node);
 194	}
 195	printk(KERN_DEBUG "\n");
 196}
 197#else
 198#define ext4_es_print_tree(inode)
 199#endif
 200
 201static inline ext4_lblk_t ext4_es_end(struct extent_status *es)
 202{
 203	BUG_ON(es->es_lblk + es->es_len < es->es_lblk);
 204	return es->es_lblk + es->es_len - 1;
 205}
 206
 207/*
 208 * search through the tree for an delayed extent with a given offset.  If
 209 * it can't be found, try to find next extent.
 210 */
 211static struct extent_status *__es_tree_search(struct rb_root *root,
 212					      ext4_lblk_t lblk)
 213{
 214	struct rb_node *node = root->rb_node;
 215	struct extent_status *es = NULL;
 216
 217	while (node) {
 218		es = rb_entry(node, struct extent_status, rb_node);
 219		if (lblk < es->es_lblk)
 220			node = node->rb_left;
 221		else if (lblk > ext4_es_end(es))
 222			node = node->rb_right;
 223		else
 224			return es;
 225	}
 226
 227	if (es && lblk < es->es_lblk)
 228		return es;
 229
 230	if (es && lblk > ext4_es_end(es)) {
 231		node = rb_next(&es->rb_node);
 232		return node ? rb_entry(node, struct extent_status, rb_node) :
 233			      NULL;
 234	}
 235
 236	return NULL;
 237}
 238
 239/*
 240 * ext4_es_find_extent_range - find extent with specified status within block
 241 *                             range or next extent following block range in
 242 *                             extents status tree
 243 *
 244 * @inode - file containing the range
 245 * @matching_fn - pointer to function that matches extents with desired status
 246 * @lblk - logical block defining start of range
 247 * @end - logical block defining end of range
 248 * @es - extent found, if any
 249 *
 250 * Find the first extent within the block range specified by @lblk and @end
 251 * in the extents status tree that satisfies @matching_fn.  If a match
 252 * is found, it's returned in @es.  If not, and a matching extent is found
 253 * beyond the block range, it's returned in @es.  If no match is found, an
 254 * extent is returned in @es whose es_lblk, es_len, and es_pblk components
 255 * are 0.
 256 */
 257static void __es_find_extent_range(struct inode *inode,
 258				   int (*matching_fn)(struct extent_status *es),
 259				   ext4_lblk_t lblk, ext4_lblk_t end,
 260				   struct extent_status *es)
 261{
 262	struct ext4_es_tree *tree = NULL;
 263	struct extent_status *es1 = NULL;
 264	struct rb_node *node;
 265
 266	WARN_ON(es == NULL);
 267	WARN_ON(end < lblk);
 268
 269	tree = &EXT4_I(inode)->i_es_tree;
 270
 271	/* see if the extent has been cached */
 272	es->es_lblk = es->es_len = es->es_pblk = 0;
 273	es1 = READ_ONCE(tree->cache_es);
 274	if (es1 && in_range(lblk, es1->es_lblk, es1->es_len)) {
 275		es_debug("%u cached by [%u/%u) %llu %x\n",
 276			 lblk, es1->es_lblk, es1->es_len,
 277			 ext4_es_pblock(es1), ext4_es_status(es1));
 278		goto out;
 
 
 279	}
 280
 281	es1 = __es_tree_search(&tree->root, lblk);
 282
 283out:
 284	if (es1 && !matching_fn(es1)) {
 285		while ((node = rb_next(&es1->rb_node)) != NULL) {
 286			es1 = rb_entry(node, struct extent_status, rb_node);
 287			if (es1->es_lblk > end) {
 288				es1 = NULL;
 289				break;
 290			}
 291			if (matching_fn(es1))
 292				break;
 293		}
 294	}
 295
 296	if (es1 && matching_fn(es1)) {
 297		WRITE_ONCE(tree->cache_es, es1);
 298		es->es_lblk = es1->es_lblk;
 299		es->es_len = es1->es_len;
 300		es->es_pblk = es1->es_pblk;
 301	}
 302
 303}
 304
 305/*
 306 * Locking for __es_find_extent_range() for external use
 307 */
 308void ext4_es_find_extent_range(struct inode *inode,
 309			       int (*matching_fn)(struct extent_status *es),
 310			       ext4_lblk_t lblk, ext4_lblk_t end,
 311			       struct extent_status *es)
 312{
 313	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 status
 329 *                   in extents status tree
 330 *
 331 * @inode - file containing the range
 332 * @matching_fn - pointer to function that matches extents with desired status
 333 * @lblk - logical block defining start of range
 334 * @end - logical block defining end of range
 335 *
 336 * Returns true if at least one block in the specified block range satisfies
 337 * the criterion specified by @matching_fn, and false if not.  If at least
 338 * one extent has the specified status, then there is at least one block
 339 * in the cluster with that status.  Should only be called by code that has
 340 * 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	else
 357		return false;
 358}
 359/*
 360 * Locking for __es_scan_range() for external use
 361 */
 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 in
 380 *                 extents status tree
 381 *
 382 * @inode - file containing the cluster
 383 * @matching_fn - pointer to function that matches extents with desired status
 384 * @lblk - logical block in cluster to be searched
 385 *
 386 * Returns true if at least one extent in the cluster containing @lblk
 387 * satisfies the criterion specified by @matching_fn, and false if not.  If at
 388 * least one extent has the specified status, then there is at least one block
 389 * in the cluster with that status.  Should only be called by code that has
 390 * 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 use
 407 */
 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_status
 469 * 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 merged
 531 * Condition:
 532 *  - logical block number is contiguous
 533 *  - physical block number is contiguous
 534 *  - status is equal
 535 */
 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_TEST
 616#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 insert
 646		 * 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 es
 665		 * 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 sure
 689		 * 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 because
 712	 * 'Indirect' structure is defined in indirect.c.  So we couldn't
 713	 * access direct/indirect tree from outside.  It is too dirty to define
 714	 * 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 this
 725			 * 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 because
 751			 * 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 because
 772	 * 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	else
 778		ext4_es_insert_extent_ind_check(inode, es);
 779}
 780#else
 781static inline void ext4_es_insert_extent_check(struct inode *inode,
 782					       struct extent_status *es)
 783{
 784}
 785#endif
 786
 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 directly
 803				 * 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	else
 831		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 extent
 847 * 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, bool delalloc_reserve_used)
 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 %d to extent status tree of inode %lu\n",
 867		 lblk, len, pblk, status, delalloc_reserve_used, 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 deferred
 931	 * allocation of delayed allocated clusters or direct allocation of
 932	 * clusters discovered to be delayed allocated.  Once allocated, a
 933	 * cluster is not included in the reserved count.
 934	 *
 935	 * When direct allocating (from fallocate, filemap, DIO, or clusters
 936	 * allocated when delalloc has been disabled by ext4_nonda_switch())
 937	 * an extent either 1) contains delayed blocks but start with
 938	 * non-delayed allocated blocks (e.g. hole) or 2) contains non-delayed
 939	 * allocated blocks which belong to delayed allocated clusters when
 940	 * bigalloc feature is enabled, quota has already been claimed by
 941	 * ext4_mb_new_blocks(), so release the quota reservations made for
 942	 * any previously delayed allocated clusters instead of claim them
 943	 * again.
 944	 */
 945	resv_used += pending;
 946	if (resv_used)
 947		ext4_da_update_reserve_space(inode, resv_used,
 948					     delalloc_reserve_used);
 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 status
 959 * tree if and only if there isn't information about the range in
 960 * 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 not
 997 */
 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			} else
1057				*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 range
1081 *	       in file from extent status tree
1082 *
1083 * @inode - file containing range
1084 * @lblk - first block in range
1085 * @es - pointer to first extent in range
1086 * @rc - pointer to reserved count data
1087 *
1088 * Assumes es is not NULL
1089 */
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 not
1100	 * been found, record the extent containing the block to the left of
1101	 * the region to be removed, if any, and note that there's no partial
1102	 * cluster to track
1103	 */
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 range
1120 *	        within an extent and add to the running tally in rsvd_count
 
1121 *
1122 * @inode - file containing extent
1123 * @lblk - first block in range
1124 * @len - length of range in blocks
1125 * @es - pointer to extent containing clusters to be counted
1126 * @rc - pointer to reserved count data
1127 *
1128 * Tracks partial clusters found at the beginning and end of extents so
1129 * they aren't overcounted when they span adjacent extents
1130 */
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 extent
1164	 * doesn't start with it, count it and stop tracking
1165	 */
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 but
1173	 * ends on one, count it
1174	 */
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 the
1185	 * number of whole delayed clusters in the extent
1186	 */
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 end
1195	 * of the current extent and we're not already tracking one
1196	 */
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 reservation
1205 *
1206 * @root - root of pending reservation tree
1207 * @lclu - logical cluster to search for
1208 *
1209 * Returns the pending reservation for the cluster identified by @lclu
1210 * 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		else
1226			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 be
1240 *	      released when removing a block range from the extent status tree
1241 *	      and releases any pending reservations within the range
1242 *
1243 * @inode - file containing block range
1244 * @end - last block in range
1245 * @right_es - pointer to extent containing next block beyond end or NULL
1246 * @rc - pointer to reserved count data
1247 *
1248 * The number of reservations to be released is equal to the number of
1249 * clusters containing delayed blocks within the range, minus the number of
1250 * clusters still containing delayed blocks at the ends of the range, and
1251 * 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 the
1278		 * ends of the range that still contain delayed blocks -
1279		 * these clusters still need to be reserved
1280		 */
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 for
1321		 * pending reservations, if any.  Clusters on the ends of the
1322		 * original removed range containing delayed blocks are
1323		 * excluded.  They've already been accounted for and it's not
1324		 * possible to determine if an associated pending reservation
1325		 * should be released with the information available in the
1326		 * extents status tree.
1327		 */
1328		if (first_lclu == last_lclu) {
1329			if (left_delayed | right_delayed)
1330				count_pending = false;
1331			else
1332				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			else
1341				count_pending = false;
1342		}
1343
1344		/*
1345		 * a pending reservation found between first_lclu and last_lclu
1346		 * represents an allocated cluster that contained at least one
1347		 * delayed block, so the delayed total must be reduced by one
1348		 * for each pending reservation found and released
1349		 */
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 tree
1370 *
1371 * @inode - file containing range
1372 * @lblk - first block in range
1373 * @end - last block in range
1374 * @reserved - number of cluster reservations released
1375 * @prealloc - pre-allocated es to avoid memory allocation failures
1376 *
1377 * If @reserved is not NULL and delayed allocation is enabled, counts
1378 * block/cluster reservations freed by removing range and if bigalloc
1379 * 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		else
1463			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 tree
1503 *
1504 * @inode - file containing range
1505 * @lblk - first block in range
1506 * @len - number of blocks to remove
1507 *
1508 * Reduces block/cluster reservation count and for bigalloc cancels pending
1509 * 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 unconditionally
1537	 * so that we are sure __es_shrink() is done with the inode before it
1538	 * 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 reclaim
1600		 * freeing inode under us
1601		 */
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 any
1615	 * 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	else
1631		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	else
1638		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 at
1779 * 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 update
1783 * 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 remove
1853 * discretionary entries from the extent status cache.  (Some entries
1854 * 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#else
1897#define ext4_print_pending_tree(inode)
1898#endif
1899
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 reservation
1920 *
1921 * @inode - file containing the pending cluster reservation
1922 * @lclu - logical cluster of interest
1923 *
1924 * Returns a pointer to a pending reservation if it's a member of
1925 * 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 of
1951 *                    pending reservations
1952 *
1953 * @inode - file containing the cluster
1954 * @lblk - logical block in the cluster to be added
1955 * @prealloc - preallocated pending entry
1956 *
1957 * Returns 1 on successful insertion and -ENOMEM on failure.  If the
1958 * 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 set
2009 *                    of pending reservations
2010 *
2011 * @inode - file containing the cluster
2012 * @lblk - logical block in the pending cluster reservation to be removed
2013 *
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 set
2032 *                       of pending reservations
2033 *
2034 * @inode - file containing the cluster
2035 * @lblk - logical block in the pending cluster reservation to be removed
2036 *
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 reservation
2050 *                   on it
2051 *
2052 * @inode - file containing the cluster
2053 * @lblk - logical block in the cluster
2054 *
2055 * Returns true if there's a pending reservation for the cluster in the
2056 * 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 extents
2073 *                                 status tree, adding a pending reservation
2074 *                                 where needed
2075 *
2076 * @inode - file containing the newly added block
2077 * @lblk - start logical block to be added
2078 * @len - length of blocks to be added
2079 * @lclu_allocated/end_allocated - indicates whether a physical cluster has
2080 *                                 been allocated for the logical cluster
2081 *                                 that contains the start/end block. Note that
2082 *                                 end_allocated should always be set to false
2083 *                                 if the start and the end block are in the
2084 *                                 same cluster
2085 */
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 cluster
2181 *                    reservations for a specified block range depending
2182 *                    upon the presence or absence of delayed blocks
2183 *                    outside the range within clusters at the ends of the
2184 *                    range
2185 *
2186 * @inode - file containing the range
2187 * @lblk - logical block defining the start of range
2188 * @len  - length of range in blocks
2189 * @prealloc - preallocated pending entry
2190 *
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 unwritten
2193 * status.  Must be called while holding i_es_lock. Returns number of new
2194 * 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 range
2213	 * spanning two or more clusters.  Note that a cluster belonging
2214	 * to a range starting and/or ending on a cluster boundary is treated
2215	 * as if it does not contain a delayed extent.  The new range may
2216	 * have allocated space for previously delayed blocks out to the
2217	 * cluster boundary, requiring that any pre-existing pending
2218	 * reservation be canceled.  Because this code only looks at blocks
2219	 * outside the range, it should revise pending reservations
2220	 * correctly even if the extent represented by the range can't be
2221	 * 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			} else
2247				__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		} else
2260			__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		} else
2272			__remove_pending(inode, last);
2273	}
2274out:
2275	return (ret < 0) ? ret : pendings;
2276}