extents_status.c 35.1 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11
/*
 *  fs/ext4/extents_status.c
 *
 * Written by Yongqiang Yang <xiaoqiangnk@gmail.com>
 * Modified by
 *	Allison Henderson <achender@linux.vnet.ibm.com>
 *	Hugh Dickins <hughd@google.com>
 *	Zheng Liu <wenqing.lz@taobao.com>
 *
 * Ext4 extents status tree core functions.
 */
12
#include <linux/list_sort.h>
13 14
#include <linux/proc_fs.h>
#include <linux/seq_file.h>
15 16
#include "ext4.h"

17 18
#include <trace/events/ext4.h>

19 20 21 22 23 24 25
/*
 * According to previous discussion in Ext4 Developer Workshop, we
 * will introduce a new structure called io tree to track all extent
 * status in order to solve some problems that we have met
 * (e.g. Reservation space warning), and provide extent-level locking.
 * Delay extent tree is the first step to achieve this goal.  It is
 * original built by Yongqiang Yang.  At that time it is called delay
Z
Zheng Liu 已提交
26
 * extent tree, whose goal is only track delayed extents in memory to
27 28
 * simplify the implementation of fiemap and bigalloc, and introduce
 * lseek SEEK_DATA/SEEK_HOLE support.  That is why it is still called
Z
Zheng Liu 已提交
29 30
 * delay extent tree at the first commit.  But for better understand
 * what it does, it has been rename to extent status tree.
31
 *
Z
Zheng Liu 已提交
32 33 34 35
 * Step1:
 * Currently the first step has been done.  All delayed extents are
 * tracked in the tree.  It maintains the delayed extent when a delayed
 * allocation is issued, and the delayed extent is written out or
36 37 38 39 40
 * invalidated.  Therefore the implementation of fiemap and bigalloc
 * are simplified, and SEEK_DATA/SEEK_HOLE are introduced.
 *
 * The following comment describes the implemenmtation of extent
 * status tree and future works.
Z
Zheng Liu 已提交
41 42 43 44 45 46 47 48 49 50 51 52 53
 *
 * Step2:
 * In this step all extent status are tracked by extent status tree.
 * Thus, we can first try to lookup a block mapping in this tree before
 * finding it in extent tree.  Hence, single extent cache can be removed
 * because extent status tree can do a better job.  Extents in status
 * tree are loaded on-demand.  Therefore, the extent status tree may not
 * contain all of the extents in a file.  Meanwhile we define a shrinker
 * to reclaim memory from extent status tree because fragmented extent
 * tree will make status tree cost too much memory.  written/unwritten/-
 * hole extents in the tree will be reclaimed by this shrinker when we
 * are under high memory pressure.  Delayed extents will not be
 * reclimed because fiemap, bigalloc, and seek_data/hole need it.
54 55 56
 */

/*
Z
Zheng Liu 已提交
57
 * Extent status tree implementation for ext4.
58 59 60
 *
 *
 * ==========================================================================
Z
Zheng Liu 已提交
61
 * Extent status tree tracks all extent status.
62
 *
Z
Zheng Liu 已提交
63
 * 1. Why we need to implement extent status tree?
64
 *
Z
Zheng Liu 已提交
65
 * Without extent status tree, ext4 identifies a delayed extent by looking
66 67 68
 * up page cache, this has several deficiencies - complicated, buggy,
 * and inefficient code.
 *
Z
Zheng Liu 已提交
69 70
 * FIEMAP, SEEK_HOLE/DATA, bigalloc, and writeout all need to know if a
 * block or a range of blocks are belonged to a delayed extent.
71
 *
Z
Zheng Liu 已提交
72
 * Let us have a look at how they do without extent status tree.
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
 *   --	FIEMAP
 *	FIEMAP looks up page cache to identify delayed allocations from holes.
 *
 *   --	SEEK_HOLE/DATA
 *	SEEK_HOLE/DATA has the same problem as FIEMAP.
 *
 *   --	bigalloc
 *	bigalloc looks up page cache to figure out if a block is
 *	already under delayed allocation or not to determine whether
 *	quota reserving is needed for the cluster.
 *
 *   --	writeout
 *	Writeout looks up whole page cache to see if a buffer is
 *	mapped, If there are not very many delayed buffers, then it is
 *	time comsuming.
 *
Z
Zheng Liu 已提交
89
 * With extent status tree implementation, FIEMAP, SEEK_HOLE/DATA,
90 91
 * bigalloc and writeout can figure out if a block or a range of
 * blocks is under delayed allocation(belonged to a delayed extent) or
Z
Zheng Liu 已提交
92
 * not by searching the extent tree.
93 94 95
 *
 *
 * ==========================================================================
Z
Zheng Liu 已提交
96 97 98 99 100 101 102 103
 * 2. Ext4 extent status tree impelmentation
 *
 *   --	extent
 *	A extent is a range of blocks which are contiguous logically and
 *	physically.  Unlike extent in extent tree, this extent in ext4 is
 *	a in-memory struct, there is no corresponding on-disk data.  There
 *	is no limit on length of extent, so an extent can contain as many
 *	blocks as they are contiguous logically and physically.
104
 *
Z
Zheng Liu 已提交
105 106 107 108
 *   --	extent status tree
 *	Every inode has an extent status tree and all allocation blocks
 *	are added to the tree with different status.  The extent in the
 *	tree are ordered by logical block no.
109
 *
Z
Zheng Liu 已提交
110 111 112
 *   --	operations on a extent status tree
 *	There are three important operations on a delayed extent tree: find
 *	next extent, adding a extent(a range of blocks) and removing a extent.
113
 *
Z
Zheng Liu 已提交
114 115
 *   --	race on a extent status tree
 *	Extent status tree is protected by inode->i_es_lock.
116
 *
Z
Zheng Liu 已提交
117 118 119 120
 *   --	memory consumption
 *      Fragmented extent tree will make extent status tree cost too much
 *      memory.  Hence, we will reclaim written/unwritten/hole extents from
 *      the tree under a heavy memory pressure.
121 122 123
 *
 *
 * ==========================================================================
Z
Zheng Liu 已提交
124 125
 * 3. Performance analysis
 *
126 127 128 129 130 131 132 133 134 135 136 137
 *   --	overhead
 *	1. There is a cache extent for write access, so if writes are
 *	not very random, adding space operaions are in O(1) time.
 *
 *   --	gain
 *	2. Code is much simpler, more readable, more maintainable and
 *	more efficient.
 *
 *
 * ==========================================================================
 * 4. TODO list
 *
Z
Zheng Liu 已提交
138
 *   -- Refactor delayed space reservation
139 140 141 142 143 144
 *
 *   -- Extent-level locking
 */

static struct kmem_cache *ext4_es_cachep;

145 146
static int __es_insert_extent(struct inode *inode, struct extent_status *newes);
static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
Z
Zheng Liu 已提交
147
			      ext4_lblk_t end);
148
static int es_reclaim_extents(struct ext4_inode_info *ei, int *nr_to_scan);
149 150
static int __es_shrink(struct ext4_sb_info *sbi, int nr_to_scan,
		       struct ext4_inode_info *locked_ei);
Z
Zheng Liu 已提交
151

152 153
int __init ext4_init_es(void)
{
T
Theodore Ts'o 已提交
154 155 156
	ext4_es_cachep = kmem_cache_create("ext4_extent_status",
					   sizeof(struct extent_status),
					   0, (SLAB_RECLAIM_ACCOUNT), NULL);
157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185
	if (ext4_es_cachep == NULL)
		return -ENOMEM;
	return 0;
}

void ext4_exit_es(void)
{
	if (ext4_es_cachep)
		kmem_cache_destroy(ext4_es_cachep);
}

void ext4_es_init_tree(struct ext4_es_tree *tree)
{
	tree->root = RB_ROOT;
	tree->cache_es = NULL;
}

#ifdef ES_DEBUG__
static void ext4_es_print_tree(struct inode *inode)
{
	struct ext4_es_tree *tree;
	struct rb_node *node;

	printk(KERN_DEBUG "status extents for inode %lu:", inode->i_ino);
	tree = &EXT4_I(inode)->i_es_tree;
	node = rb_first(&tree->root);
	while (node) {
		struct extent_status *es;
		es = rb_entry(node, struct extent_status, rb_node);
186
		printk(KERN_DEBUG " [%u/%u) %llu %x",
187 188
		       es->es_lblk, es->es_len,
		       ext4_es_pblock(es), ext4_es_status(es));
189 190 191 192 193 194 195 196
		node = rb_next(node);
	}
	printk(KERN_DEBUG "\n");
}
#else
#define ext4_es_print_tree(inode)
#endif

Z
Zheng Liu 已提交
197
static inline ext4_lblk_t ext4_es_end(struct extent_status *es)
198
{
Z
Zheng Liu 已提交
199 200
	BUG_ON(es->es_lblk + es->es_len < es->es_lblk);
	return es->es_lblk + es->es_len - 1;
201 202 203 204 205 206 207
}

/*
 * search through the tree for an delayed extent with a given offset.  If
 * it can't be found, try to find next extent.
 */
static struct extent_status *__es_tree_search(struct rb_root *root,
Z
Zheng Liu 已提交
208
					      ext4_lblk_t lblk)
209 210 211 212 213 214
{
	struct rb_node *node = root->rb_node;
	struct extent_status *es = NULL;

	while (node) {
		es = rb_entry(node, struct extent_status, rb_node);
Z
Zheng Liu 已提交
215
		if (lblk < es->es_lblk)
216
			node = node->rb_left;
Z
Zheng Liu 已提交
217
		else if (lblk > ext4_es_end(es))
218 219 220 221 222
			node = node->rb_right;
		else
			return es;
	}

Z
Zheng Liu 已提交
223
	if (es && lblk < es->es_lblk)
224 225
		return es;

Z
Zheng Liu 已提交
226
	if (es && lblk > ext4_es_end(es)) {
227 228 229 230 231 232 233 234 235
		node = rb_next(&es->rb_node);
		return node ? rb_entry(node, struct extent_status, rb_node) :
			      NULL;
	}

	return NULL;
}

/*
Y
Yan, Zheng 已提交
236 237
 * ext4_es_find_delayed_extent_range: find the 1st delayed extent covering
 * @es->lblk if it exists, otherwise, the next extent after @es->lblk.
238 239
 *
 * @inode: the inode which owns delayed extents
240
 * @lblk: the offset where we start to search
Y
Yan, Zheng 已提交
241
 * @end: the offset where we stop to search
242 243
 * @es: delayed extent that we found
 */
Y
Yan, Zheng 已提交
244 245
void ext4_es_find_delayed_extent_range(struct inode *inode,
				 ext4_lblk_t lblk, ext4_lblk_t end,
246
				 struct extent_status *es)
247 248 249 250 251
{
	struct ext4_es_tree *tree = NULL;
	struct extent_status *es1 = NULL;
	struct rb_node *node;

252
	BUG_ON(es == NULL);
Y
Yan, Zheng 已提交
253 254
	BUG_ON(end < lblk);
	trace_ext4_es_find_delayed_extent_range_enter(inode, lblk);
255

256 257 258
	read_lock(&EXT4_I(inode)->i_es_lock);
	tree = &EXT4_I(inode)->i_es_tree;

259
	/* find extent in cache firstly */
260
	es->es_lblk = es->es_len = es->es_pblk = 0;
261 262
	if (tree->cache_es) {
		es1 = tree->cache_es;
263
		if (in_range(lblk, es1->es_lblk, es1->es_len)) {
264
			es_debug("%u cached by [%u/%u) %llu %x\n",
265
				 lblk, es1->es_lblk, es1->es_len,
266
				 ext4_es_pblock(es1), ext4_es_status(es1));
267 268 269 270
			goto out;
		}
	}

271
	es1 = __es_tree_search(&tree->root, lblk);
272 273

out:
274 275 276
	if (es1 && !ext4_es_is_delayed(es1)) {
		while ((node = rb_next(&es1->rb_node)) != NULL) {
			es1 = rb_entry(node, struct extent_status, rb_node);
Y
Yan, Zheng 已提交
277 278 279 280
			if (es1->es_lblk > end) {
				es1 = NULL;
				break;
			}
281 282 283 284 285 286
			if (ext4_es_is_delayed(es1))
				break;
		}
	}

	if (es1 && ext4_es_is_delayed(es1)) {
287
		tree->cache_es = es1;
Z
Zheng Liu 已提交
288 289
		es->es_lblk = es1->es_lblk;
		es->es_len = es1->es_len;
290
		es->es_pblk = es1->es_pblk;
291 292 293
	}

	read_unlock(&EXT4_I(inode)->i_es_lock);
294

Y
Yan, Zheng 已提交
295
	trace_ext4_es_find_delayed_extent_range_exit(inode, es);
296 297
}

298
static void ext4_es_list_add(struct inode *inode)
299 300 301 302 303 304 305 306 307 308 309 310 311 312 313
{
	struct ext4_inode_info *ei = EXT4_I(inode);
	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);

	if (!list_empty(&ei->i_es_list))
		return;

	spin_lock(&sbi->s_es_lock);
	if (list_empty(&ei->i_es_list)) {
		list_add_tail(&ei->i_es_list, &sbi->s_es_list);
		sbi->s_es_nr_inode++;
	}
	spin_unlock(&sbi->s_es_lock);
}

314
static void ext4_es_list_del(struct inode *inode)
315 316 317 318 319 320 321 322 323 324 325 326 327
{
	struct ext4_inode_info *ei = EXT4_I(inode);
	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);

	spin_lock(&sbi->s_es_lock);
	if (!list_empty(&ei->i_es_list)) {
		list_del_init(&ei->i_es_list);
		sbi->s_es_nr_inode--;
		WARN_ON_ONCE(sbi->s_es_nr_inode < 0);
	}
	spin_unlock(&sbi->s_es_lock);
}

328
static struct extent_status *
329 330
ext4_es_alloc_extent(struct inode *inode, ext4_lblk_t lblk, ext4_lblk_t len,
		     ext4_fsblk_t pblk)
331 332 333 334 335
{
	struct extent_status *es;
	es = kmem_cache_alloc(ext4_es_cachep, GFP_ATOMIC);
	if (es == NULL)
		return NULL;
Z
Zheng Liu 已提交
336 337
	es->es_lblk = lblk;
	es->es_len = len;
338
	es->es_pblk = pblk;
339 340 341 342

	/*
	 * We don't count delayed extent because we never try to reclaim them
	 */
T
Theodore Ts'o 已提交
343
	if (!ext4_es_is_delayed(es)) {
344 345
		if (!EXT4_I(inode)->i_es_shk_nr++)
			ext4_es_list_add(inode);
346
		percpu_counter_inc(&EXT4_SB(inode->i_sb)->
347
					s_es_stats.es_stats_shk_cnt);
T
Theodore Ts'o 已提交
348
	}
349

350 351 352
	EXT4_I(inode)->i_es_all_nr++;
	percpu_counter_inc(&EXT4_SB(inode->i_sb)->s_es_stats.es_stats_all_cnt);

353 354 355
	return es;
}

356
static void ext4_es_free_extent(struct inode *inode, struct extent_status *es)
357
{
358 359 360
	EXT4_I(inode)->i_es_all_nr--;
	percpu_counter_dec(&EXT4_SB(inode->i_sb)->s_es_stats.es_stats_all_cnt);

361
	/* Decrease the shrink counter when this es is not delayed */
362
	if (!ext4_es_is_delayed(es)) {
363
		BUG_ON(EXT4_I(inode)->i_es_shk_nr == 0);
364 365
		if (!--EXT4_I(inode)->i_es_shk_nr)
			ext4_es_list_del(inode);
366
		percpu_counter_dec(&EXT4_SB(inode->i_sb)->
367
					s_es_stats.es_stats_shk_cnt);
368 369
	}

370 371 372
	kmem_cache_free(ext4_es_cachep, es);
}

Z
Zheng Liu 已提交
373 374 375 376
/*
 * Check whether or not two extents can be merged
 * Condition:
 *  - logical block number is contiguous
377 378
 *  - physical block number is contiguous
 *  - status is equal
Z
Zheng Liu 已提交
379 380 381 382
 */
static int ext4_es_can_be_merged(struct extent_status *es1,
				 struct extent_status *es2)
{
383
	if (ext4_es_type(es1) != ext4_es_type(es2))
Z
Zheng Liu 已提交
384 385
		return 0;

386 387 388 389 390 391
	if (((__u64) es1->es_len) + es2->es_len > EXT_MAX_BLOCKS) {
		pr_warn("ES assertion failed when merging extents. "
			"The sum of lengths of es1 (%d) and es2 (%d) "
			"is bigger than allowed file size (%d)\n",
			es1->es_len, es2->es_len, EXT_MAX_BLOCKS);
		WARN_ON(1);
392
		return 0;
393
	}
394

395
	if (((__u64) es1->es_lblk) + es1->es_len != es2->es_lblk)
396 397
		return 0;

398 399 400 401 402 403 404 405 406 407 408 409
	if ((ext4_es_is_written(es1) || ext4_es_is_unwritten(es1)) &&
	    (ext4_es_pblock(es1) + es1->es_len == ext4_es_pblock(es2)))
		return 1;

	if (ext4_es_is_hole(es1))
		return 1;

	/* we need to check delayed extent is without unwritten status */
	if (ext4_es_is_delayed(es1) && !ext4_es_is_unwritten(es1))
		return 1;

	return 0;
Z
Zheng Liu 已提交
410 411
}

412
static struct extent_status *
413
ext4_es_try_to_merge_left(struct inode *inode, struct extent_status *es)
414
{
415
	struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
416 417 418 419 420 421 422 423
	struct extent_status *es1;
	struct rb_node *node;

	node = rb_prev(&es->rb_node);
	if (!node)
		return es;

	es1 = rb_entry(node, struct extent_status, rb_node);
Z
Zheng Liu 已提交
424 425
	if (ext4_es_can_be_merged(es1, es)) {
		es1->es_len += es->es_len;
426 427
		if (ext4_es_is_referenced(es))
			ext4_es_set_referenced(es1);
428
		rb_erase(&es->rb_node, &tree->root);
429
		ext4_es_free_extent(inode, es);
430 431 432 433 434 435 436
		es = es1;
	}

	return es;
}

static struct extent_status *
437
ext4_es_try_to_merge_right(struct inode *inode, struct extent_status *es)
438
{
439
	struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
440 441 442 443 444 445 446 447
	struct extent_status *es1;
	struct rb_node *node;

	node = rb_next(&es->rb_node);
	if (!node)
		return es;

	es1 = rb_entry(node, struct extent_status, rb_node);
Z
Zheng Liu 已提交
448 449
	if (ext4_es_can_be_merged(es, es1)) {
		es->es_len += es1->es_len;
450 451
		if (ext4_es_is_referenced(es1))
			ext4_es_set_referenced(es);
452
		rb_erase(node, &tree->root);
453
		ext4_es_free_extent(inode, es1);
454 455 456 457 458
	}

	return es;
}

459
#ifdef ES_AGGRESSIVE_TEST
Z
Zheng Liu 已提交
460 461
#include "ext4_extents.h"	/* Needed when ES_AGGRESSIVE_TEST is defined */

462 463 464 465 466 467 468 469 470 471
static void ext4_es_insert_extent_ext_check(struct inode *inode,
					    struct extent_status *es)
{
	struct ext4_ext_path *path = NULL;
	struct ext4_extent *ex;
	ext4_lblk_t ee_block;
	ext4_fsblk_t ee_start;
	unsigned short ee_len;
	int depth, ee_status, es_status;

472
	path = ext4_find_extent(inode, es->es_lblk, NULL, EXT4_EX_NOCACHE);
473 474 475 476 477 478 479 480 481 482 483 484
	if (IS_ERR(path))
		return;

	depth = ext_depth(inode);
	ex = path[depth].p_ext;

	if (ex) {

		ee_block = le32_to_cpu(ex->ee_block);
		ee_start = ext4_ext_pblock(ex);
		ee_len = ext4_ext_get_actual_len(ex);

485
		ee_status = ext4_ext_is_unwritten(ex) ? 1 : 0;
486 487 488 489 490 491 492 493
		es_status = ext4_es_is_unwritten(es) ? 1 : 0;

		/*
		 * Make sure ex and es are not overlap when we try to insert
		 * a delayed/hole extent.
		 */
		if (!ext4_es_is_written(es) && !ext4_es_is_unwritten(es)) {
			if (in_range(es->es_lblk, ee_block, ee_len)) {
494
				pr_warn("ES insert assertion failed for "
495 496
					"inode: %lu we can find an extent "
					"at block [%d/%d/%llu/%c], but we "
497 498
					"want to add a delayed/hole extent "
					"[%d/%d/%llu/%x]\n",
499 500 501 502 503 504 505 506 507 508 509 510 511 512
					inode->i_ino, ee_block, ee_len,
					ee_start, ee_status ? 'u' : 'w',
					es->es_lblk, es->es_len,
					ext4_es_pblock(es), ext4_es_status(es));
			}
			goto out;
		}

		/*
		 * We don't check ee_block == es->es_lblk, etc. because es
		 * might be a part of whole extent, vice versa.
		 */
		if (es->es_lblk < ee_block ||
		    ext4_es_pblock(es) != ee_start + es->es_lblk - ee_block) {
513
			pr_warn("ES insert assertion failed for inode: %lu "
514 515 516 517 518 519 520 521 522
				"ex_status [%d/%d/%llu/%c] != "
				"es_status [%d/%d/%llu/%c]\n", inode->i_ino,
				ee_block, ee_len, ee_start,
				ee_status ? 'u' : 'w', es->es_lblk, es->es_len,
				ext4_es_pblock(es), es_status ? 'u' : 'w');
			goto out;
		}

		if (ee_status ^ es_status) {
523
			pr_warn("ES insert assertion failed for inode: %lu "
524 525 526 527 528 529 530 531 532 533 534 535
				"ex_status [%d/%d/%llu/%c] != "
				"es_status [%d/%d/%llu/%c]\n", inode->i_ino,
				ee_block, ee_len, ee_start,
				ee_status ? 'u' : 'w', es->es_lblk, es->es_len,
				ext4_es_pblock(es), es_status ? 'u' : 'w');
		}
	} else {
		/*
		 * We can't find an extent on disk.  So we need to make sure
		 * that we don't want to add an written/unwritten extent.
		 */
		if (!ext4_es_is_delayed(es) && !ext4_es_is_hole(es)) {
536
			pr_warn("ES insert assertion failed for inode: %lu "
537
				"can't find an extent at block %d but we want "
538 539
				"to add a written/unwritten extent "
				"[%d/%d/%llu/%x]\n", inode->i_ino,
540 541 542 543 544
				es->es_lblk, es->es_lblk, es->es_len,
				ext4_es_pblock(es), ext4_es_status(es));
		}
	}
out:
545 546
	ext4_ext_drop_refs(path);
	kfree(path);
547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571
}

static void ext4_es_insert_extent_ind_check(struct inode *inode,
					    struct extent_status *es)
{
	struct ext4_map_blocks map;
	int retval;

	/*
	 * Here we call ext4_ind_map_blocks to lookup a block mapping because
	 * 'Indirect' structure is defined in indirect.c.  So we couldn't
	 * access direct/indirect tree from outside.  It is too dirty to define
	 * this function in indirect.c file.
	 */

	map.m_lblk = es->es_lblk;
	map.m_len = es->es_len;

	retval = ext4_ind_map_blocks(NULL, inode, &map, 0);
	if (retval > 0) {
		if (ext4_es_is_delayed(es) || ext4_es_is_hole(es)) {
			/*
			 * We want to add a delayed/hole extent but this
			 * block has been allocated.
			 */
572
			pr_warn("ES insert assertion failed for inode: %lu "
573
				"We can find blocks but we want to add a "
574
				"delayed/hole extent [%d/%d/%llu/%x]\n",
575 576 577 578 579
				inode->i_ino, es->es_lblk, es->es_len,
				ext4_es_pblock(es), ext4_es_status(es));
			return;
		} else if (ext4_es_is_written(es)) {
			if (retval != es->es_len) {
580
				pr_warn("ES insert assertion failed for "
581 582 583 584 585
					"inode: %lu retval %d != es_len %d\n",
					inode->i_ino, retval, es->es_len);
				return;
			}
			if (map.m_pblk != ext4_es_pblock(es)) {
586
				pr_warn("ES insert assertion failed for "
587 588 589 590 591 592 593 594 595 596 597 598 599 600 601
					"inode: %lu m_pblk %llu != "
					"es_pblk %llu\n",
					inode->i_ino, map.m_pblk,
					ext4_es_pblock(es));
				return;
			}
		} else {
			/*
			 * We don't need to check unwritten extent because
			 * indirect-based file doesn't have it.
			 */
			BUG_ON(1);
		}
	} else if (retval == 0) {
		if (ext4_es_is_written(es)) {
602
			pr_warn("ES insert assertion failed for inode: %lu "
603
				"We can't find the block but we want to add "
604
				"a written extent [%d/%d/%llu/%x]\n",
605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631
				inode->i_ino, es->es_lblk, es->es_len,
				ext4_es_pblock(es), ext4_es_status(es));
			return;
		}
	}
}

static inline void ext4_es_insert_extent_check(struct inode *inode,
					       struct extent_status *es)
{
	/*
	 * We don't need to worry about the race condition because
	 * caller takes i_data_sem locking.
	 */
	BUG_ON(!rwsem_is_locked(&EXT4_I(inode)->i_data_sem));
	if (ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
		ext4_es_insert_extent_ext_check(inode, es);
	else
		ext4_es_insert_extent_ind_check(inode, es);
}
#else
static inline void ext4_es_insert_extent_check(struct inode *inode,
					       struct extent_status *es)
{
}
#endif

632
static int __es_insert_extent(struct inode *inode, struct extent_status *newes)
633
{
634
	struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
635 636 637 638 639 640 641 642
	struct rb_node **p = &tree->root.rb_node;
	struct rb_node *parent = NULL;
	struct extent_status *es;

	while (*p) {
		parent = *p;
		es = rb_entry(parent, struct extent_status, rb_node);

Z
Zheng Liu 已提交
643 644 645 646 647 648 649 650
		if (newes->es_lblk < es->es_lblk) {
			if (ext4_es_can_be_merged(newes, es)) {
				/*
				 * Here we can modify es_lblk directly
				 * because it isn't overlapped.
				 */
				es->es_lblk = newes->es_lblk;
				es->es_len += newes->es_len;
651 652 653 654
				if (ext4_es_is_written(es) ||
				    ext4_es_is_unwritten(es))
					ext4_es_store_pblock(es,
							     newes->es_pblk);
655
				es = ext4_es_try_to_merge_left(inode, es);
656 657 658
				goto out;
			}
			p = &(*p)->rb_left;
Z
Zheng Liu 已提交
659 660 661
		} else if (newes->es_lblk > ext4_es_end(es)) {
			if (ext4_es_can_be_merged(es, newes)) {
				es->es_len += newes->es_len;
662
				es = ext4_es_try_to_merge_right(inode, es);
663 664 665 666
				goto out;
			}
			p = &(*p)->rb_right;
		} else {
Z
Zheng Liu 已提交
667 668
			BUG_ON(1);
			return -EINVAL;
669 670 671
		}
	}

672
	es = ext4_es_alloc_extent(inode, newes->es_lblk, newes->es_len,
673
				  newes->es_pblk);
674 675 676 677 678 679 680 681 682 683 684
	if (!es)
		return -ENOMEM;
	rb_link_node(&es->rb_node, parent, p);
	rb_insert_color(&es->rb_node, &tree->root);

out:
	tree->cache_es = es;
	return 0;
}

/*
685 686
 * ext4_es_insert_extent() adds information to an inode's extent
 * status tree.
687 688 689
 *
 * Return 0 on success, error code on failure.
 */
Z
Zheng Liu 已提交
690
int ext4_es_insert_extent(struct inode *inode, ext4_lblk_t lblk,
691
			  ext4_lblk_t len, ext4_fsblk_t pblk,
692
			  unsigned int status)
693
{
Z
Zheng Liu 已提交
694 695
	struct extent_status newes;
	ext4_lblk_t end = lblk + len - 1;
696 697
	int err = 0;

698
	es_debug("add [%u/%u) %llu %x to extent status tree of inode %lu\n",
699
		 lblk, len, pblk, status, inode->i_ino);
Z
Zheng Liu 已提交
700

701 702 703
	if (!len)
		return 0;

Z
Zheng Liu 已提交
704 705
	BUG_ON(end < lblk);

706 707 708 709 710 711 712 713
	if ((status & EXTENT_STATUS_DELAYED) &&
	    (status & EXTENT_STATUS_WRITTEN)) {
		ext4_warning(inode->i_sb, "Inserting extent [%u/%u] as "
				" delayed and written which can potentially "
				" cause data loss.\n", lblk, len);
		WARN_ON(1);
	}

Z
Zheng Liu 已提交
714 715
	newes.es_lblk = lblk;
	newes.es_len = len;
716
	ext4_es_store_pblock_status(&newes, pblk, status);
717
	trace_ext4_es_insert_extent(inode, &newes);
718

719 720
	ext4_es_insert_extent_check(inode, &newes);

721
	write_lock(&EXT4_I(inode)->i_es_lock);
722
	err = __es_remove_extent(inode, lblk, end);
Z
Zheng Liu 已提交
723 724
	if (err != 0)
		goto error;
725
retry:
726
	err = __es_insert_extent(inode, &newes);
727
	if (err == -ENOMEM && __es_shrink(EXT4_SB(inode->i_sb),
728
					  128, EXT4_I(inode)))
729 730 731
		goto retry;
	if (err == -ENOMEM && !ext4_es_is_delayed(&newes))
		err = 0;
Z
Zheng Liu 已提交
732 733

error:
734 735 736 737 738 739 740
	write_unlock(&EXT4_I(inode)->i_es_lock);

	ext4_es_print_tree(inode);

	return err;
}

741 742 743 744 745 746 747 748 749 750 751 752 753 754 755
/*
 * ext4_es_cache_extent() inserts information into the extent status
 * tree if and only if there isn't information about the range in
 * question already.
 */
void ext4_es_cache_extent(struct inode *inode, ext4_lblk_t lblk,
			  ext4_lblk_t len, ext4_fsblk_t pblk,
			  unsigned int status)
{
	struct extent_status *es;
	struct extent_status newes;
	ext4_lblk_t end = lblk + len - 1;

	newes.es_lblk = lblk;
	newes.es_len = len;
756
	ext4_es_store_pblock_status(&newes, pblk, status);
757 758 759 760 761 762 763 764 765 766
	trace_ext4_es_cache_extent(inode, &newes);

	if (!len)
		return;

	BUG_ON(end < lblk);

	write_lock(&EXT4_I(inode)->i_es_lock);

	es = __es_tree_search(&EXT4_I(inode)->i_es_tree.root, lblk);
767 768
	if (!es || es->es_lblk > end)
		__es_insert_extent(inode, &newes);
769 770 771
	write_unlock(&EXT4_I(inode)->i_es_lock);
}

772 773 774 775 776 777 778 779 780 781 782
/*
 * ext4_es_lookup_extent() looks up an extent in extent status tree.
 *
 * ext4_es_lookup_extent is called by ext4_map_blocks/ext4_da_map_blocks.
 *
 * Return: 1 on found, 0 on not
 */
int ext4_es_lookup_extent(struct inode *inode, ext4_lblk_t lblk,
			  struct extent_status *es)
{
	struct ext4_es_tree *tree;
783
	struct ext4_es_stats *stats;
784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819
	struct extent_status *es1 = NULL;
	struct rb_node *node;
	int found = 0;

	trace_ext4_es_lookup_extent_enter(inode, lblk);
	es_debug("lookup extent in block %u\n", lblk);

	tree = &EXT4_I(inode)->i_es_tree;
	read_lock(&EXT4_I(inode)->i_es_lock);

	/* find extent in cache firstly */
	es->es_lblk = es->es_len = es->es_pblk = 0;
	if (tree->cache_es) {
		es1 = tree->cache_es;
		if (in_range(lblk, es1->es_lblk, es1->es_len)) {
			es_debug("%u cached by [%u/%u)\n",
				 lblk, es1->es_lblk, es1->es_len);
			found = 1;
			goto out;
		}
	}

	node = tree->root.rb_node;
	while (node) {
		es1 = rb_entry(node, struct extent_status, rb_node);
		if (lblk < es1->es_lblk)
			node = node->rb_left;
		else if (lblk > ext4_es_end(es1))
			node = node->rb_right;
		else {
			found = 1;
			break;
		}
	}

out:
820
	stats = &EXT4_SB(inode->i_sb)->s_es_stats;
821 822 823 824 825
	if (found) {
		BUG_ON(!es1);
		es->es_lblk = es1->es_lblk;
		es->es_len = es1->es_len;
		es->es_pblk = es1->es_pblk;
826 827
		if (!ext4_es_is_referenced(es))
			ext4_es_set_referenced(es);
828 829 830
		stats->es_stats_cache_hits++;
	} else {
		stats->es_stats_cache_misses++;
831 832 833 834 835 836 837 838
	}

	read_unlock(&EXT4_I(inode)->i_es_lock);

	trace_ext4_es_lookup_extent_exit(inode, es, found);
	return found;
}

839 840
static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
			      ext4_lblk_t end)
841
{
842
	struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
843 844 845
	struct rb_node *node;
	struct extent_status *es;
	struct extent_status orig_es;
Z
Zheng Liu 已提交
846
	ext4_lblk_t len1, len2;
847
	ext4_fsblk_t block;
848
	int err;
849

850 851
retry:
	err = 0;
Z
Zheng Liu 已提交
852
	es = __es_tree_search(&tree->root, lblk);
853 854
	if (!es)
		goto out;
Z
Zheng Liu 已提交
855
	if (es->es_lblk > end)
856 857 858 859 860
		goto out;

	/* Simply invalidate cache_es. */
	tree->cache_es = NULL;

Z
Zheng Liu 已提交
861 862
	orig_es.es_lblk = es->es_lblk;
	orig_es.es_len = es->es_len;
863 864
	orig_es.es_pblk = es->es_pblk;

Z
Zheng Liu 已提交
865 866
	len1 = lblk > es->es_lblk ? lblk - es->es_lblk : 0;
	len2 = ext4_es_end(es) > end ? ext4_es_end(es) - end : 0;
867
	if (len1 > 0)
Z
Zheng Liu 已提交
868
		es->es_len = len1;
869 870
	if (len2 > 0) {
		if (len1 > 0) {
Z
Zheng Liu 已提交
871 872 873 874
			struct extent_status newes;

			newes.es_lblk = end + 1;
			newes.es_len = len2;
875
			block = 0x7FDEADBEEFULL;
876
			if (ext4_es_is_written(&orig_es) ||
877
			    ext4_es_is_unwritten(&orig_es))
878 879
				block = ext4_es_pblock(&orig_es) +
					orig_es.es_len - len2;
880 881
			ext4_es_store_pblock_status(&newes, block,
						    ext4_es_status(&orig_es));
882
			err = __es_insert_extent(inode, &newes);
883
			if (err) {
Z
Zheng Liu 已提交
884 885
				es->es_lblk = orig_es.es_lblk;
				es->es_len = orig_es.es_len;
886
				if ((err == -ENOMEM) &&
887
				    __es_shrink(EXT4_SB(inode->i_sb),
888
							128, EXT4_I(inode)))
889
					goto retry;
890 891 892
				goto out;
			}
		} else {
Z
Zheng Liu 已提交
893 894
			es->es_lblk = end + 1;
			es->es_len = len2;
895 896 897 898 899
			if (ext4_es_is_written(es) ||
			    ext4_es_is_unwritten(es)) {
				block = orig_es.es_pblk + orig_es.es_len - len2;
				ext4_es_store_pblock(es, block);
			}
900 901 902 903 904 905 906 907 908 909 910 911
		}
		goto out;
	}

	if (len1 > 0) {
		node = rb_next(&es->rb_node);
		if (node)
			es = rb_entry(node, struct extent_status, rb_node);
		else
			es = NULL;
	}

Z
Zheng Liu 已提交
912
	while (es && ext4_es_end(es) <= end) {
913 914
		node = rb_next(&es->rb_node);
		rb_erase(&es->rb_node, &tree->root);
915
		ext4_es_free_extent(inode, es);
916 917 918 919 920 921 922
		if (!node) {
			es = NULL;
			break;
		}
		es = rb_entry(node, struct extent_status, rb_node);
	}

Z
Zheng Liu 已提交
923
	if (es && es->es_lblk < end + 1) {
924 925
		ext4_lblk_t orig_len = es->es_len;

Z
Zheng Liu 已提交
926 927 928
		len1 = ext4_es_end(es) - end;
		es->es_lblk = end + 1;
		es->es_len = len1;
929 930 931 932
		if (ext4_es_is_written(es) || ext4_es_is_unwritten(es)) {
			block = es->es_pblk + orig_len - len1;
			ext4_es_store_pblock(es, block);
		}
933 934 935
	}

out:
Z
Zheng Liu 已提交
936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953
	return err;
}

/*
 * ext4_es_remove_extent() removes a space from a extent status tree.
 *
 * Return 0 on success, error code on failure.
 */
int ext4_es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
			  ext4_lblk_t len)
{
	ext4_lblk_t end;
	int err = 0;

	trace_ext4_es_remove_extent(inode, lblk, len);
	es_debug("remove [%u/%u) from extent status tree of inode %lu\n",
		 lblk, len, inode->i_ino);

954 955 956
	if (!len)
		return err;

Z
Zheng Liu 已提交
957 958 959
	end = lblk + len - 1;
	BUG_ON(end < lblk);

960 961 962 963 964
	/*
	 * ext4_clear_inode() depends on us taking i_es_lock unconditionally
	 * so that we are sure __es_shrink() is done with the inode before it
	 * is reclaimed.
	 */
Z
Zheng Liu 已提交
965
	write_lock(&EXT4_I(inode)->i_es_lock);
966
	err = __es_remove_extent(inode, lblk, end);
967 968 969 970
	write_unlock(&EXT4_I(inode)->i_es_lock);
	ext4_es_print_tree(inode);
	return err;
}
971

972 973
static int __es_shrink(struct ext4_sb_info *sbi, int nr_to_scan,
		       struct ext4_inode_info *locked_ei)
974 975
{
	struct ext4_inode_info *ei;
976 977 978
	struct ext4_es_stats *es_stats;
	ktime_t start_time;
	u64 scan_time;
979
	int nr_to_walk;
980
	int nr_shrunk = 0;
981
	int retried = 0, nr_skipped = 0;
982

983 984
	es_stats = &sbi->s_es_stats;
	start_time = ktime_get();
985

986
retry:
987 988 989 990 991 992 993 994 995 996
	spin_lock(&sbi->s_es_lock);
	nr_to_walk = sbi->s_es_nr_inode;
	while (nr_to_walk-- > 0) {
		if (list_empty(&sbi->s_es_list)) {
			spin_unlock(&sbi->s_es_lock);
			goto out;
		}
		ei = list_first_entry(&sbi->s_es_list, struct ext4_inode_info,
				      i_es_list);
		/* Move the inode to the tail */
997
		list_move_tail(&ei->i_es_list, &sbi->s_es_list);
998

999
		/*
1000 1001
		 * Normally we try hard to avoid shrinking precached inodes,
		 * but we will as a last resort.
1002
		 */
1003 1004
		if (!retried && ext4_test_inode_state(&ei->vfs_inode,
						EXT4_STATE_EXT_PRECACHED)) {
1005
			nr_skipped++;
1006 1007
			continue;
		}
1008

1009 1010
		if (ei == locked_ei || !write_trylock(&ei->i_es_lock)) {
			nr_skipped++;
1011
			continue;
1012 1013 1014 1015 1016 1017
		}
		/*
		 * Now we hold i_es_lock which protects us from inode reclaim
		 * freeing inode under us
		 */
		spin_unlock(&sbi->s_es_lock);
1018

1019
		nr_shrunk += es_reclaim_extents(ei, &nr_to_scan);
1020 1021
		write_unlock(&ei->i_es_lock);

1022
		if (nr_to_scan <= 0)
1023 1024
			goto out;
		spin_lock(&sbi->s_es_lock);
1025
	}
1026
	spin_unlock(&sbi->s_es_lock);
1027 1028 1029

	/*
	 * If we skipped any inodes, and we weren't able to make any
1030
	 * forward progress, try again to scan precached inodes.
1031 1032 1033 1034 1035 1036
	 */
	if ((nr_shrunk == 0) && nr_skipped && !retried) {
		retried++;
		goto retry;
	}

1037
	if (locked_ei && nr_shrunk == 0)
1038
		nr_shrunk = es_reclaim_extents(locked_ei, &nr_to_scan);
1039

1040
out:
1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054
	scan_time = ktime_to_ns(ktime_sub(ktime_get(), start_time));
	if (likely(es_stats->es_stats_scan_time))
		es_stats->es_stats_scan_time = (scan_time +
				es_stats->es_stats_scan_time*3) / 4;
	else
		es_stats->es_stats_scan_time = scan_time;
	if (scan_time > es_stats->es_stats_max_scan_time)
		es_stats->es_stats_max_scan_time = scan_time;
	if (likely(es_stats->es_stats_shrunk))
		es_stats->es_stats_shrunk = (nr_shrunk +
				es_stats->es_stats_shrunk*3) / 4;
	else
		es_stats->es_stats_shrunk = nr_shrunk;

1055
	trace_ext4_es_shrink(sbi->s_sb, nr_shrunk, scan_time,
1056
			     nr_skipped, retried);
1057 1058 1059
	return nr_shrunk;
}

1060 1061 1062 1063 1064 1065 1066
static unsigned long ext4_es_count(struct shrinker *shrink,
				   struct shrink_control *sc)
{
	unsigned long nr;
	struct ext4_sb_info *sbi;

	sbi = container_of(shrink, struct ext4_sb_info, s_es_shrinker);
1067
	nr = percpu_counter_read_positive(&sbi->s_es_stats.es_stats_shk_cnt);
1068
	trace_ext4_es_shrink_count(sbi->s_sb, sc->nr_to_scan, nr);
1069 1070 1071 1072 1073
	return nr;
}

static unsigned long ext4_es_scan(struct shrinker *shrink,
				  struct shrink_control *sc)
1074 1075 1076 1077 1078 1079
{
	struct ext4_sb_info *sbi = container_of(shrink,
					struct ext4_sb_info, s_es_shrinker);
	int nr_to_scan = sc->nr_to_scan;
	int ret, nr_shrunk;

1080
	ret = percpu_counter_read_positive(&sbi->s_es_stats.es_stats_shk_cnt);
1081
	trace_ext4_es_shrink_scan_enter(sbi->s_sb, nr_to_scan, ret);
1082 1083 1084 1085

	if (!nr_to_scan)
		return ret;

1086
	nr_shrunk = __es_shrink(sbi, nr_to_scan, NULL);
1087

1088
	trace_ext4_es_shrink_scan_exit(sbi->s_sb, nr_shrunk, ret);
1089
	return nr_shrunk;
1090 1091
}

1092
static void *ext4_es_seq_shrinker_info_start(struct seq_file *seq, loff_t *pos)
1093
{
1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113
	return *pos ? NULL : SEQ_START_TOKEN;
}

static void *
ext4_es_seq_shrinker_info_next(struct seq_file *seq, void *v, loff_t *pos)
{
	return NULL;
}

static int ext4_es_seq_shrinker_info_show(struct seq_file *seq, void *v)
{
	struct ext4_sb_info *sbi = seq->private;
	struct ext4_es_stats *es_stats = &sbi->s_es_stats;
	struct ext4_inode_info *ei, *max = NULL;
	unsigned int inode_cnt = 0;

	if (v != SEQ_START_TOKEN)
		return 0;

	/* here we just find an inode that has the max nr. of objects */
1114 1115
	spin_lock(&sbi->s_es_lock);
	list_for_each_entry(ei, &sbi->s_es_list, i_es_list) {
1116 1117 1118 1119 1120 1121
		inode_cnt++;
		if (max && max->i_es_all_nr < ei->i_es_all_nr)
			max = ei;
		else if (!max)
			max = ei;
	}
1122
	spin_unlock(&sbi->s_es_lock);
1123 1124 1125

	seq_printf(seq, "stats:\n  %lld objects\n  %lld reclaimable objects\n",
		   percpu_counter_sum_positive(&es_stats->es_stats_all_cnt),
1126
		   percpu_counter_sum_positive(&es_stats->es_stats_shk_cnt));
1127 1128 1129 1130
	seq_printf(seq, "  %lu/%lu cache hits/misses\n",
		   es_stats->es_stats_cache_hits,
		   es_stats->es_stats_cache_misses);
	if (inode_cnt)
1131
		seq_printf(seq, "  %d inodes on list\n", inode_cnt);
1132 1133 1134 1135 1136 1137 1138 1139

	seq_printf(seq, "average:\n  %llu us scan time\n",
	    div_u64(es_stats->es_stats_scan_time, 1000));
	seq_printf(seq, "  %lu shrunk objects\n", es_stats->es_stats_shrunk);
	if (inode_cnt)
		seq_printf(seq,
		    "maximum:\n  %lu inode (%u objects, %u reclaimable)\n"
		    "  %llu us max scan time\n",
1140
		    max->vfs_inode.i_ino, max->i_es_all_nr, max->i_es_shk_nr,
1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185
		    div_u64(es_stats->es_stats_max_scan_time, 1000));

	return 0;
}

static void ext4_es_seq_shrinker_info_stop(struct seq_file *seq, void *v)
{
}

static const struct seq_operations ext4_es_seq_shrinker_info_ops = {
	.start = ext4_es_seq_shrinker_info_start,
	.next  = ext4_es_seq_shrinker_info_next,
	.stop  = ext4_es_seq_shrinker_info_stop,
	.show  = ext4_es_seq_shrinker_info_show,
};

static int
ext4_es_seq_shrinker_info_open(struct inode *inode, struct file *file)
{
	int ret;

	ret = seq_open(file, &ext4_es_seq_shrinker_info_ops);
	if (!ret) {
		struct seq_file *m = file->private_data;
		m->private = PDE_DATA(inode);
	}

	return ret;
}

static int
ext4_es_seq_shrinker_info_release(struct inode *inode, struct file *file)
{
	return seq_release(inode, file);
}

static const struct file_operations ext4_es_seq_shrinker_info_fops = {
	.owner		= THIS_MODULE,
	.open		= ext4_es_seq_shrinker_info_open,
	.read		= seq_read,
	.llseek		= seq_lseek,
	.release	= ext4_es_seq_shrinker_info_release,
};

int ext4_es_register_shrinker(struct ext4_sb_info *sbi)
1186
{
1187 1188
	int err;

1189 1190
	/* Make sure we have enough bits for physical block number */
	BUILD_BUG_ON(ES_SHIFT < 48);
1191 1192 1193
	INIT_LIST_HEAD(&sbi->s_es_list);
	sbi->s_es_nr_inode = 0;
	spin_lock_init(&sbi->s_es_lock);
1194 1195 1196 1197 1198
	sbi->s_es_stats.es_stats_shrunk = 0;
	sbi->s_es_stats.es_stats_cache_hits = 0;
	sbi->s_es_stats.es_stats_cache_misses = 0;
	sbi->s_es_stats.es_stats_scan_time = 0;
	sbi->s_es_stats.es_stats_max_scan_time = 0;
1199
	err = percpu_counter_init(&sbi->s_es_stats.es_stats_all_cnt, 0, GFP_KERNEL);
1200 1201
	if (err)
		return err;
1202
	err = percpu_counter_init(&sbi->s_es_stats.es_stats_shk_cnt, 0, GFP_KERNEL);
1203 1204 1205
	if (err)
		goto err1;

1206 1207
	sbi->s_es_shrinker.scan_objects = ext4_es_scan;
	sbi->s_es_shrinker.count_objects = ext4_es_count;
1208
	sbi->s_es_shrinker.seeks = DEFAULT_SEEKS;
1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219
	err = register_shrinker(&sbi->s_es_shrinker);
	if (err)
		goto err2;

	if (sbi->s_proc)
		proc_create_data("es_shrinker_info", S_IRUGO, sbi->s_proc,
				 &ext4_es_seq_shrinker_info_fops, sbi);

	return 0;

err2:
1220
	percpu_counter_destroy(&sbi->s_es_stats.es_stats_shk_cnt);
1221 1222 1223
err1:
	percpu_counter_destroy(&sbi->s_es_stats.es_stats_all_cnt);
	return err;
1224 1225
}

1226
void ext4_es_unregister_shrinker(struct ext4_sb_info *sbi)
1227
{
1228 1229 1230
	if (sbi->s_proc)
		remove_proc_entry("es_shrinker_info", sbi->s_proc);
	percpu_counter_destroy(&sbi->s_es_stats.es_stats_all_cnt);
1231
	percpu_counter_destroy(&sbi->s_es_stats.es_stats_shk_cnt);
1232
	unregister_shrinker(&sbi->s_es_shrinker);
1233 1234
}

1235 1236 1237 1238 1239 1240 1241 1242 1243 1244
/*
 * Shrink extents in given inode from ei->i_es_shrink_lblk till end. Scan at
 * most *nr_to_scan extents, update *nr_to_scan accordingly.
 *
 * Return 0 if we hit end of tree / interval, 1 if we exhausted nr_to_scan.
 * Increment *nr_shrunk by the number of reclaimed extents. Also update
 * ei->i_es_shrink_lblk to where we should continue scanning.
 */
static int es_do_reclaim_extents(struct ext4_inode_info *ei, ext4_lblk_t end,
				 int *nr_to_scan, int *nr_shrunk)
1245 1246 1247 1248
{
	struct inode *inode = &ei->vfs_inode;
	struct ext4_es_tree *tree = &ei->i_es_tree;
	struct extent_status *es;
1249
	struct rb_node *node;
1250

1251 1252 1253 1254 1255 1256 1257 1258 1259
	es = __es_tree_search(&tree->root, ei->i_es_shrink_lblk);
	if (!es)
		goto out_wrap;
	node = &es->rb_node;
	while (*nr_to_scan > 0) {
		if (es->es_lblk > end) {
			ei->i_es_shrink_lblk = end + 1;
			return 0;
		}
1260

1261
		(*nr_to_scan)--;
1262 1263 1264 1265 1266
		node = rb_next(&es->rb_node);
		/*
		 * We can't reclaim delayed extent from status tree because
		 * fiemap, bigallic, and seek_data/hole need to use it.
		 */
1267 1268 1269 1270 1271
		if (ext4_es_is_delayed(es))
			goto next;
		if (ext4_es_is_referenced(es)) {
			ext4_es_clear_referenced(es);
			goto next;
1272
		}
1273 1274 1275 1276 1277

		rb_erase(&es->rb_node, &tree->root);
		ext4_es_free_extent(inode, es);
		(*nr_shrunk)++;
next:
1278 1279 1280
		if (!node)
			goto out_wrap;
		es = rb_entry(node, struct extent_status, rb_node);
1281
	}
1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308
	ei->i_es_shrink_lblk = es->es_lblk;
	return 1;
out_wrap:
	ei->i_es_shrink_lblk = 0;
	return 0;
}

static int es_reclaim_extents(struct ext4_inode_info *ei, int *nr_to_scan)
{
	struct inode *inode = &ei->vfs_inode;
	int nr_shrunk = 0;
	ext4_lblk_t start = ei->i_es_shrink_lblk;
	static DEFINE_RATELIMIT_STATE(_rs, DEFAULT_RATELIMIT_INTERVAL,
				      DEFAULT_RATELIMIT_BURST);

	if (ei->i_es_shk_nr == 0)
		return 0;

	if (ext4_test_inode_state(inode, EXT4_STATE_EXT_PRECACHED) &&
	    __ratelimit(&_rs))
		ext4_warning(inode->i_sb, "forced shrink of precached extents");

	if (!es_do_reclaim_extents(ei, EXT_MAX_BLOCKS, nr_to_scan, &nr_shrunk) &&
	    start != 0)
		es_do_reclaim_extents(ei, start - 1, nr_to_scan, &nr_shrunk);

	ei->i_es_tree.cache_es = NULL;
1309 1310
	return nr_shrunk;
}