extents_status.c 29.9 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
	if (((__u64) es1->es_len) + es2->es_len > 0xFFFFFFFFULL)
348 349
		return 0;

350
	if (((__u64) es1->es_lblk) + es1->es_len != es2->es_lblk)
351 352
		return 0;

353 354 355 356 357 358 359 360 361 362 363 364
	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 已提交
365 366
}

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

	return es;
}

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

	return es;
}

410
#ifdef ES_AGGRESSIVE_TEST
Z
Zheng Liu 已提交
411 412
#include "ext4_extents.h"	/* Needed when ES_AGGRESSIVE_TEST is defined */

413 414 415 416 417 418 419 420 421 422
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;

423
	path = ext4_ext_find_extent(inode, es->es_lblk, NULL, EXT4_EX_NOCACHE);
424 425 426 427 428 429 430 431 432 433 434 435
	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);

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

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

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

625
	es = ext4_es_alloc_extent(inode, newes->es_lblk, newes->es_len,
626
				  newes->es_pblk);
627 628 629 630 631 632 633 634 635 636 637
	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;
}

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

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

654 655 656
	if (!len)
		return 0;

Z
Zheng Liu 已提交
657 658 659 660
	BUG_ON(end < lblk);

	newes.es_lblk = lblk;
	newes.es_len = len;
661
	ext4_es_store_pblock_status(&newes, pblk, status);
662
	trace_ext4_es_insert_extent(inode, &newes);
663

664 665
	ext4_es_insert_extent_check(inode, &newes);

666
	write_lock(&EXT4_I(inode)->i_es_lock);
667
	err = __es_remove_extent(inode, lblk, end);
Z
Zheng Liu 已提交
668 669
	if (err != 0)
		goto error;
670
retry:
671
	err = __es_insert_extent(inode, &newes);
672 673 674 675 676
	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 已提交
677 678

error:
679 680 681 682 683 684 685
	write_unlock(&EXT4_I(inode)->i_es_lock);

	ext4_es_print_tree(inode);

	return err;
}

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

717 718 719 720 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
/*
 * 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;
}

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

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

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

Z
Zheng Liu 已提交
799 800
	orig_es.es_lblk = es->es_lblk;
	orig_es.es_len = es->es_len;
801 802
	orig_es.es_pblk = es->es_pblk;

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

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

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

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

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

892 893 894
	if (!len)
		return err;

Z
Zheng Liu 已提交
895 896 897 898
	end = lblk + len - 1;
	BUG_ON(end < lblk);

	write_lock(&EXT4_I(inode)->i_es_lock);
899
	err = __es_remove_extent(inode, lblk, end);
900 901 902 903
	write_unlock(&EXT4_I(inode)->i_es_lock);
	ext4_es_print_tree(inode);
	return err;
}
904

905 906 907 908 909 910 911
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);

912 913 914 915 916 917
	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;
918 919 920 921 922 923 924 925
	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;
}

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

	spin_lock(&sbi->s_es_lru_lock);
936

937
retry:
938
	list_for_each_safe(cur, tmp, &sbi->s_es_lru) {
939 940
		int shrunk;

941 942 943 944 945 946
		/*
		 * 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;
947 948 949

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

950 951 952 953 954 955 956 957 958 959
		/*
		 * 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);
960 961
			continue;
		}
962

963
		if (ei->i_es_lru_nr == 0 || ei == locked_ei)
964
			continue;
965 966

		write_lock(&ei->i_es_lock);
967
		shrunk = __es_try_to_reclaim_extents(ei, nr_to_scan);
968 969
		if (ei->i_es_lru_nr == 0)
			list_del_init(&ei->i_es_lru);
970 971
		write_unlock(&ei->i_es_lock);

972 973
		nr_shrunk += shrunk;
		nr_to_scan -= shrunk;
974 975 976
		if (nr_to_scan == 0)
			break;
	}
977 978

	/* Move the newer inodes into the tail of the LRU list. */
979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001
	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;
	}

1002 1003
	spin_unlock(&sbi->s_es_lru_lock);

1004
	if (locked_ei && nr_shrunk == 0)
1005
		nr_shrunk = __es_try_to_reclaim_extents(locked_ei, nr_to_scan);
1006 1007 1008 1009

	return nr_shrunk;
}

1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023
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);
	trace_ext4_es_shrink_enter(sbi->s_sb, sc->nr_to_scan, nr);
	return nr;
}

static unsigned long ext4_es_scan(struct shrinker *shrink,
				  struct shrink_control *sc)
1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037
{
	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);
	trace_ext4_es_shrink_enter(sbi->s_sb, nr_to_scan, ret);

	if (!nr_to_scan)
		return ret;

	nr_shrunk = __ext4_es_shrink(sbi, nr_to_scan, NULL);

T
Theodore Ts'o 已提交
1038
	trace_ext4_es_shrink_exit(sbi->s_sb, nr_shrunk, ret);
1039
	return nr_shrunk;
1040 1041
}

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

1053
void ext4_es_unregister_shrinker(struct ext4_sb_info *sbi)
1054
{
1055
	unregister_shrinker(&sbi->s_es_shrinker);
1056 1057 1058 1059 1060 1061 1062
}

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);

1063 1064 1065 1066 1067
	ei->i_touch_when = jiffies;

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

1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091
	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;
1092
	unsigned long nr_shrunk = 0;
1093 1094
	static DEFINE_RATELIMIT_STATE(_rs, DEFAULT_RATELIMIT_INTERVAL,
				      DEFAULT_RATELIMIT_BURST);
1095 1096 1097 1098

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

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

1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121
	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;
}