extents_status.c 30.2 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12
/*
 *  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.
 */
#include <linux/rbtree.h>
13
#include <linux/list_sort.h>
14 15 16
#include "ext4.h"
#include "extents_status.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 149
static int __es_try_to_reclaim_extents(struct ext4_inode_info *ei,
				       int nr_to_scan);
150 151
static int __ext4_es_shrink(struct ext4_sb_info *sbi, int nr_to_scan,
			    struct ext4_inode_info *locked_ei);
Z
Zheng Liu 已提交
152

153 154
int __init ext4_init_es(void)
{
T
Theodore Ts'o 已提交
155 156 157
	ext4_es_cachep = kmem_cache_create("ext4_extent_status",
					   sizeof(struct extent_status),
					   0, (SLAB_RECLAIM_ACCOUNT), NULL);
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 186
	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);
187
		printk(KERN_DEBUG " [%u/%u) %llu %x",
188 189
		       es->es_lblk, es->es_len,
		       ext4_es_pblock(es), ext4_es_status(es));
190 191 192 193 194 195 196 197
		node = rb_next(node);
	}
	printk(KERN_DEBUG "\n");
}
#else
#define ext4_es_print_tree(inode)
#endif

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

/*
 * 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 已提交
209
					      ext4_lblk_t lblk)
210 211 212 213 214 215
{
	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 已提交
216
		if (lblk < es->es_lblk)
217
			node = node->rb_left;
Z
Zheng Liu 已提交
218
		else if (lblk > ext4_es_end(es))
219 220 221 222 223
			node = node->rb_right;
		else
			return es;
	}

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

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

	return NULL;
}

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

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

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

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

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

out:
275 276 277
	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 已提交
278 279 280 281
			if (es1->es_lblk > end) {
				es1 = NULL;
				break;
			}
282 283 284 285 286 287
			if (ext4_es_is_delayed(es1))
				break;
		}
	}

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

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

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

static struct extent_status *
300 301
ext4_es_alloc_extent(struct inode *inode, ext4_lblk_t lblk, ext4_lblk_t len,
		     ext4_fsblk_t pblk)
302 303 304 305 306
{
	struct extent_status *es;
	es = kmem_cache_alloc(ext4_es_cachep, GFP_ATOMIC);
	if (es == NULL)
		return NULL;
Z
Zheng Liu 已提交
307 308
	es->es_lblk = lblk;
	es->es_len = len;
309
	es->es_pblk = pblk;
310 311 312 313

	/*
	 * We don't count delayed extent because we never try to reclaim them
	 */
T
Theodore Ts'o 已提交
314
	if (!ext4_es_is_delayed(es)) {
315
		EXT4_I(inode)->i_es_lru_nr++;
316
		percpu_counter_inc(&EXT4_SB(inode->i_sb)->s_extent_cache_cnt);
T
Theodore Ts'o 已提交
317
	}
318

319 320 321
	return es;
}

322
static void ext4_es_free_extent(struct inode *inode, struct extent_status *es)
323
{
324 325 326 327
	/* Decrease the lru counter when this es is not delayed */
	if (!ext4_es_is_delayed(es)) {
		BUG_ON(EXT4_I(inode)->i_es_lru_nr == 0);
		EXT4_I(inode)->i_es_lru_nr--;
328
		percpu_counter_dec(&EXT4_SB(inode->i_sb)->s_extent_cache_cnt);
329 330
	}

331 332 333
	kmem_cache_free(ext4_es_cachep, es);
}

Z
Zheng Liu 已提交
334 335 336 337
/*
 * Check whether or not two extents can be merged
 * Condition:
 *  - logical block number is contiguous
338 339
 *  - physical block number is contiguous
 *  - status is equal
Z
Zheng Liu 已提交
340 341 342 343
 */
static int ext4_es_can_be_merged(struct extent_status *es1,
				 struct extent_status *es2)
{
344
	if (ext4_es_status(es1) != ext4_es_status(es2))
Z
Zheng Liu 已提交
345 346
		return 0;

347 348 349 350 351 352
	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);
353
		return 0;
354
	}
355

356
	if (((__u64) es1->es_lblk) + es1->es_len != es2->es_lblk)
357 358
		return 0;

359 360 361 362 363 364 365 366 367 368 369 370
	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 已提交
371 372
}

373
static struct extent_status *
374
ext4_es_try_to_merge_left(struct inode *inode, struct extent_status *es)
375
{
376
	struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
377 378 379 380 381 382 383 384
	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 已提交
385 386
	if (ext4_es_can_be_merged(es1, es)) {
		es1->es_len += es->es_len;
387
		rb_erase(&es->rb_node, &tree->root);
388
		ext4_es_free_extent(inode, es);
389 390 391 392 393 394 395
		es = es1;
	}

	return es;
}

static struct extent_status *
396
ext4_es_try_to_merge_right(struct inode *inode, struct extent_status *es)
397
{
398
	struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
399 400 401 402 403 404 405 406
	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 已提交
407 408
	if (ext4_es_can_be_merged(es, es1)) {
		es->es_len += es1->es_len;
409
		rb_erase(node, &tree->root);
410
		ext4_es_free_extent(inode, es1);
411 412 413 414 415
	}

	return es;
}

416
#ifdef ES_AGGRESSIVE_TEST
Z
Zheng Liu 已提交
417 418
#include "ext4_extents.h"	/* Needed when ES_AGGRESSIVE_TEST is defined */

419 420 421 422 423 424 425 426 427 428
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;

429
	path = ext4_find_extent(inode, es->es_lblk, NULL, EXT4_EX_NOCACHE);
430 431 432 433 434 435 436 437 438 439 440 441
	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);

442
		ee_status = ext4_ext_is_unwritten(ex) ? 1 : 0;
443 444 445 446 447 448 449 450
		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)) {
451
				pr_warn("ES insert assertion failed for "
452 453
					"inode: %lu we can find an extent "
					"at block [%d/%d/%llu/%c], but we "
454 455
					"want to add a delayed/hole extent "
					"[%d/%d/%llu/%x]\n",
456 457 458 459 460 461 462 463 464 465 466 467 468 469
					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) {
470
			pr_warn("ES insert assertion failed for inode: %lu "
471 472 473 474 475 476 477 478 479
				"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) {
480
			pr_warn("ES insert assertion failed for inode: %lu "
481 482 483 484 485 486 487 488 489 490 491 492
				"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)) {
493
			pr_warn("ES insert assertion failed for inode: %lu "
494
				"can't find an extent at block %d but we want "
495 496
				"to add a written/unwritten extent "
				"[%d/%d/%llu/%x]\n", inode->i_ino,
497 498 499 500 501
				es->es_lblk, es->es_lblk, es->es_len,
				ext4_es_pblock(es), ext4_es_status(es));
		}
	}
out:
502 503
	ext4_ext_drop_refs(path);
	kfree(path);
504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528
}

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.
			 */
529
			pr_warn("ES insert assertion failed for inode: %lu "
530
				"We can find blocks but we want to add a "
531
				"delayed/hole extent [%d/%d/%llu/%x]\n",
532 533 534 535 536
				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) {
537
				pr_warn("ES insert assertion failed for "
538 539 540 541 542
					"inode: %lu retval %d != es_len %d\n",
					inode->i_ino, retval, es->es_len);
				return;
			}
			if (map.m_pblk != ext4_es_pblock(es)) {
543
				pr_warn("ES insert assertion failed for "
544 545 546 547 548 549 550 551 552 553 554 555 556 557 558
					"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)) {
559
			pr_warn("ES insert assertion failed for inode: %lu "
560
				"We can't find the block but we want to add "
561
				"a written extent [%d/%d/%llu/%x]\n",
562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588
				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

589
static int __es_insert_extent(struct inode *inode, struct extent_status *newes)
590
{
591
	struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
592 593 594 595 596 597 598 599
	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 已提交
600 601 602 603 604 605 606 607
		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;
608 609 610 611
				if (ext4_es_is_written(es) ||
				    ext4_es_is_unwritten(es))
					ext4_es_store_pblock(es,
							     newes->es_pblk);
612
				es = ext4_es_try_to_merge_left(inode, es);
613 614 615
				goto out;
			}
			p = &(*p)->rb_left;
Z
Zheng Liu 已提交
616 617 618
		} else if (newes->es_lblk > ext4_es_end(es)) {
			if (ext4_es_can_be_merged(es, newes)) {
				es->es_len += newes->es_len;
619
				es = ext4_es_try_to_merge_right(inode, es);
620 621 622 623
				goto out;
			}
			p = &(*p)->rb_right;
		} else {
Z
Zheng Liu 已提交
624 625
			BUG_ON(1);
			return -EINVAL;
626 627 628
		}
	}

629
	es = ext4_es_alloc_extent(inode, newes->es_lblk, newes->es_len,
630
				  newes->es_pblk);
631 632 633 634 635 636 637 638 639 640 641
	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;
}

/*
642 643
 * ext4_es_insert_extent() adds information to an inode's extent
 * status tree.
644 645 646
 *
 * Return 0 on success, error code on failure.
 */
Z
Zheng Liu 已提交
647
int ext4_es_insert_extent(struct inode *inode, ext4_lblk_t lblk,
648
			  ext4_lblk_t len, ext4_fsblk_t pblk,
649
			  unsigned int status)
650
{
Z
Zheng Liu 已提交
651 652
	struct extent_status newes;
	ext4_lblk_t end = lblk + len - 1;
653 654
	int err = 0;

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

658 659 660
	if (!len)
		return 0;

Z
Zheng Liu 已提交
661 662 663 664
	BUG_ON(end < lblk);

	newes.es_lblk = lblk;
	newes.es_len = len;
665
	ext4_es_store_pblock_status(&newes, pblk, status);
666
	trace_ext4_es_insert_extent(inode, &newes);
667

668 669
	ext4_es_insert_extent_check(inode, &newes);

670
	write_lock(&EXT4_I(inode)->i_es_lock);
671
	err = __es_remove_extent(inode, lblk, end);
Z
Zheng Liu 已提交
672 673
	if (err != 0)
		goto error;
674
retry:
675
	err = __es_insert_extent(inode, &newes);
676 677 678 679 680
	if (err == -ENOMEM && __ext4_es_shrink(EXT4_SB(inode->i_sb), 1,
					       EXT4_I(inode)))
		goto retry;
	if (err == -ENOMEM && !ext4_es_is_delayed(&newes))
		err = 0;
Z
Zheng Liu 已提交
681 682

error:
683 684 685 686 687 688 689
	write_unlock(&EXT4_I(inode)->i_es_lock);

	ext4_es_print_tree(inode);

	return err;
}

690 691 692 693 694 695 696 697 698 699 700 701 702 703 704
/*
 * 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;
705
	ext4_es_store_pblock_status(&newes, pblk, status);
706 707 708 709 710 711 712 713 714 715
	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);
716 717
	if (!es || es->es_lblk > end)
		__es_insert_extent(inode, &newes);
718 719 720
	write_unlock(&EXT4_I(inode)->i_es_lock);
}

721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780
/*
 * 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;
	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:
	if (found) {
		BUG_ON(!es1);
		es->es_lblk = es1->es_lblk;
		es->es_len = es1->es_len;
		es->es_pblk = es1->es_pblk;
	}

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

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

781 782
static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
			      ext4_lblk_t end)
783
{
784
	struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
785 786 787
	struct rb_node *node;
	struct extent_status *es;
	struct extent_status orig_es;
Z
Zheng Liu 已提交
788
	ext4_lblk_t len1, len2;
789
	ext4_fsblk_t block;
790
	int err;
791

792 793
retry:
	err = 0;
Z
Zheng Liu 已提交
794
	es = __es_tree_search(&tree->root, lblk);
795 796
	if (!es)
		goto out;
Z
Zheng Liu 已提交
797
	if (es->es_lblk > end)
798 799 800 801 802
		goto out;

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

Z
Zheng Liu 已提交
803 804
	orig_es.es_lblk = es->es_lblk;
	orig_es.es_len = es->es_len;
805 806
	orig_es.es_pblk = es->es_pblk;

Z
Zheng Liu 已提交
807 808
	len1 = lblk > es->es_lblk ? lblk - es->es_lblk : 0;
	len2 = ext4_es_end(es) > end ? ext4_es_end(es) - end : 0;
809
	if (len1 > 0)
Z
Zheng Liu 已提交
810
		es->es_len = len1;
811 812
	if (len2 > 0) {
		if (len1 > 0) {
Z
Zheng Liu 已提交
813 814 815 816
			struct extent_status newes;

			newes.es_lblk = end + 1;
			newes.es_len = len2;
817
			block = 0x7FDEADBEEFULL;
818
			if (ext4_es_is_written(&orig_es) ||
819
			    ext4_es_is_unwritten(&orig_es))
820 821
				block = ext4_es_pblock(&orig_es) +
					orig_es.es_len - len2;
822 823
			ext4_es_store_pblock_status(&newes, block,
						    ext4_es_status(&orig_es));
824
			err = __es_insert_extent(inode, &newes);
825
			if (err) {
Z
Zheng Liu 已提交
826 827
				es->es_lblk = orig_es.es_lblk;
				es->es_len = orig_es.es_len;
828 829 830 831
				if ((err == -ENOMEM) &&
				    __ext4_es_shrink(EXT4_SB(inode->i_sb), 1,
						     EXT4_I(inode)))
					goto retry;
832 833 834
				goto out;
			}
		} else {
Z
Zheng Liu 已提交
835 836
			es->es_lblk = end + 1;
			es->es_len = len2;
837 838 839 840 841
			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);
			}
842 843 844 845 846 847 848 849 850 851 852 853
		}
		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 已提交
854
	while (es && ext4_es_end(es) <= end) {
855 856
		node = rb_next(&es->rb_node);
		rb_erase(&es->rb_node, &tree->root);
857
		ext4_es_free_extent(inode, es);
858 859 860 861 862 863 864
		if (!node) {
			es = NULL;
			break;
		}
		es = rb_entry(node, struct extent_status, rb_node);
	}

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

Z
Zheng Liu 已提交
868 869 870
		len1 = ext4_es_end(es) - end;
		es->es_lblk = end + 1;
		es->es_len = len1;
871 872 873 874
		if (ext4_es_is_written(es) || ext4_es_is_unwritten(es)) {
			block = es->es_pblk + orig_len - len1;
			ext4_es_store_pblock(es, block);
		}
875 876 877
	}

out:
Z
Zheng Liu 已提交
878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895
	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);

896 897 898
	if (!len)
		return err;

Z
Zheng Liu 已提交
899 900 901 902
	end = lblk + len - 1;
	BUG_ON(end < lblk);

	write_lock(&EXT4_I(inode)->i_es_lock);
903
	err = __es_remove_extent(inode, lblk, end);
904 905 906 907
	write_unlock(&EXT4_I(inode)->i_es_lock);
	ext4_es_print_tree(inode);
	return err;
}
908

909 910 911 912 913 914 915
static int ext4_inode_touch_time_cmp(void *priv, struct list_head *a,
				     struct list_head *b)
{
	struct ext4_inode_info *eia, *eib;
	eia = list_entry(a, struct ext4_inode_info, i_es_lru);
	eib = list_entry(b, struct ext4_inode_info, i_es_lru);

916 917 918 919 920 921
	if (ext4_test_inode_state(&eia->vfs_inode, EXT4_STATE_EXT_PRECACHED) &&
	    !ext4_test_inode_state(&eib->vfs_inode, EXT4_STATE_EXT_PRECACHED))
		return 1;
	if (!ext4_test_inode_state(&eia->vfs_inode, EXT4_STATE_EXT_PRECACHED) &&
	    ext4_test_inode_state(&eib->vfs_inode, EXT4_STATE_EXT_PRECACHED))
		return -1;
922 923 924 925 926 927 928 929
	if (eia->i_touch_when == eib->i_touch_when)
		return 0;
	if (time_after(eia->i_touch_when, eib->i_touch_when))
		return 1;
	else
		return -1;
}

930 931
static int __ext4_es_shrink(struct ext4_sb_info *sbi, int nr_to_scan,
			    struct ext4_inode_info *locked_ei)
932 933
{
	struct ext4_inode_info *ei;
934
	struct list_head *cur, *tmp;
935
	LIST_HEAD(skipped);
936
	int nr_shrunk = 0;
937
	int retried = 0, skip_precached = 1, nr_skipped = 0;
938 939

	spin_lock(&sbi->s_es_lru_lock);
940

941
retry:
942
	list_for_each_safe(cur, tmp, &sbi->s_es_lru) {
943 944
		int shrunk;

945 946 947 948 949 950
		/*
		 * If we have already reclaimed all extents from extent
		 * status tree, just stop the loop immediately.
		 */
		if (percpu_counter_read_positive(&sbi->s_extent_cache_cnt) == 0)
			break;
951 952 953

		ei = list_entry(cur, struct ext4_inode_info, i_es_lru);

954 955 956 957 958 959 960 961 962 963
		/*
		 * Skip the inode that is newer than the last_sorted
		 * time.  Normally we try hard to avoid shrinking
		 * precached inodes, but we will as a last resort.
		 */
		if ((sbi->s_es_last_sorted < ei->i_touch_when) ||
		    (skip_precached && ext4_test_inode_state(&ei->vfs_inode,
						EXT4_STATE_EXT_PRECACHED))) {
			nr_skipped++;
			list_move_tail(cur, &skipped);
964 965
			continue;
		}
966

967 968
		if (ei->i_es_lru_nr == 0 || ei == locked_ei ||
		    !write_trylock(&ei->i_es_lock))
969
			continue;
970

971
		shrunk = __es_try_to_reclaim_extents(ei, nr_to_scan);
972 973
		if (ei->i_es_lru_nr == 0)
			list_del_init(&ei->i_es_lru);
974 975
		write_unlock(&ei->i_es_lock);

976 977
		nr_shrunk += shrunk;
		nr_to_scan -= shrunk;
978 979 980
		if (nr_to_scan == 0)
			break;
	}
981 982

	/* Move the newer inodes into the tail of the LRU list. */
983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005
	list_splice_tail(&skipped, &sbi->s_es_lru);
	INIT_LIST_HEAD(&skipped);

	/*
	 * If we skipped any inodes, and we weren't able to make any
	 * forward progress, sort the list and try again.
	 */
	if ((nr_shrunk == 0) && nr_skipped && !retried) {
		retried++;
		list_sort(NULL, &sbi->s_es_lru, ext4_inode_touch_time_cmp);
		sbi->s_es_last_sorted = jiffies;
		ei = list_first_entry(&sbi->s_es_lru, struct ext4_inode_info,
				      i_es_lru);
		/*
		 * If there are no non-precached inodes left on the
		 * list, start releasing precached extents.
		 */
		if (ext4_test_inode_state(&ei->vfs_inode,
					  EXT4_STATE_EXT_PRECACHED))
			skip_precached = 0;
		goto retry;
	}

1006 1007
	spin_unlock(&sbi->s_es_lru_lock);

1008
	if (locked_ei && nr_shrunk == 0)
1009
		nr_shrunk = __es_try_to_reclaim_extents(locked_ei, nr_to_scan);
1010 1011 1012 1013

	return nr_shrunk;
}

1014 1015 1016 1017 1018 1019 1020 1021
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);
	nr = percpu_counter_read_positive(&sbi->s_extent_cache_cnt);
1022
	trace_ext4_es_shrink_count(sbi->s_sb, sc->nr_to_scan, nr);
1023 1024 1025 1026 1027
	return nr;
}

static unsigned long ext4_es_scan(struct shrinker *shrink,
				  struct shrink_control *sc)
1028 1029 1030 1031 1032 1033 1034
{
	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;

	ret = percpu_counter_read_positive(&sbi->s_extent_cache_cnt);
1035
	trace_ext4_es_shrink_scan_enter(sbi->s_sb, nr_to_scan, ret);
1036 1037 1038 1039 1040 1041

	if (!nr_to_scan)
		return ret;

	nr_shrunk = __ext4_es_shrink(sbi, nr_to_scan, NULL);

1042
	trace_ext4_es_shrink_scan_exit(sbi->s_sb, nr_shrunk, ret);
1043
	return nr_shrunk;
1044 1045
}

1046
void ext4_es_register_shrinker(struct ext4_sb_info *sbi)
1047 1048 1049
{
	INIT_LIST_HEAD(&sbi->s_es_lru);
	spin_lock_init(&sbi->s_es_lru_lock);
1050
	sbi->s_es_last_sorted = 0;
1051 1052
	sbi->s_es_shrinker.scan_objects = ext4_es_scan;
	sbi->s_es_shrinker.count_objects = ext4_es_count;
1053 1054 1055 1056
	sbi->s_es_shrinker.seeks = DEFAULT_SEEKS;
	register_shrinker(&sbi->s_es_shrinker);
}

1057
void ext4_es_unregister_shrinker(struct ext4_sb_info *sbi)
1058
{
1059
	unregister_shrinker(&sbi->s_es_shrinker);
1060 1061 1062 1063 1064 1065 1066
}

void ext4_es_lru_add(struct inode *inode)
{
	struct ext4_inode_info *ei = EXT4_I(inode);
	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);

1067 1068 1069 1070 1071
	ei->i_touch_when = jiffies;

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

1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095
	spin_lock(&sbi->s_es_lru_lock);
	if (list_empty(&ei->i_es_lru))
		list_add_tail(&ei->i_es_lru, &sbi->s_es_lru);
	spin_unlock(&sbi->s_es_lru_lock);
}

void ext4_es_lru_del(struct inode *inode)
{
	struct ext4_inode_info *ei = EXT4_I(inode);
	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);

	spin_lock(&sbi->s_es_lru_lock);
	if (!list_empty(&ei->i_es_lru))
		list_del_init(&ei->i_es_lru);
	spin_unlock(&sbi->s_es_lru_lock);
}

static int __es_try_to_reclaim_extents(struct ext4_inode_info *ei,
				       int nr_to_scan)
{
	struct inode *inode = &ei->vfs_inode;
	struct ext4_es_tree *tree = &ei->i_es_tree;
	struct rb_node *node;
	struct extent_status *es;
1096
	unsigned long nr_shrunk = 0;
1097 1098
	static DEFINE_RATELIMIT_STATE(_rs, DEFAULT_RATELIMIT_INTERVAL,
				      DEFAULT_RATELIMIT_BURST);
1099 1100 1101 1102

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

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

1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125
	node = rb_first(&tree->root);
	while (node != NULL) {
		es = rb_entry(node, struct extent_status, rb_node);
		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.
		 */
		if (!ext4_es_is_delayed(es)) {
			rb_erase(&es->rb_node, &tree->root);
			ext4_es_free_extent(inode, es);
			nr_shrunk++;
			if (--nr_to_scan == 0)
				break;
		}
	}
	tree->cache_es = NULL;
	return nr_shrunk;
}