extents_status.c 26.4 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
/*
 *  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>
#include "ext4.h"
#include "extents_status.h"
#include "ext4_extents.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);
Z
Zheng Liu 已提交
150

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

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

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

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

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

	return NULL;
}

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

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

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

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

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

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

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

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

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

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

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

318 319 320
	return es;
}

321
static void ext4_es_free_extent(struct inode *inode, struct extent_status *es)
322
{
323 324 325 326
	/* 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--;
327
		percpu_counter_dec(&EXT4_SB(inode->i_sb)->s_extent_cache_cnt);
328 329
	}

330 331 332
	kmem_cache_free(ext4_es_cachep, es);
}

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

346
	if (((__u64) es1->es_len) + es2->es_len > 0xFFFFFFFFULL)
347 348
		return 0;

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

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

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

	return es;
}

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

	return es;
}

409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 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 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 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 572 573 574 575 576 577 578 579 580 581
#ifdef ES_AGGRESSIVE_TEST
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;

	path = ext4_ext_find_extent(inode, es->es_lblk, NULL);
	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);

		ee_status = ext4_ext_is_uninitialized(ex) ? 1 : 0;
		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)) {
				pr_warn("ES insert assertation failed for "
					"inode: %lu we can find an extent "
					"at block [%d/%d/%llu/%c], but we "
					"want to add an delayed/hole extent "
					"[%d/%d/%llu/%llx]\n",
					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) {
			pr_warn("ES insert assertation failed for inode: %lu "
				"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) {
			pr_warn("ES insert assertation failed for inode: %lu "
				"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)) {
			pr_warn("ES insert assertation failed for inode: %lu "
				"can't find an extent at block %d but we want "
				"to add an written/unwritten extent "
				"[%d/%d/%llu/%llx]\n", inode->i_ino,
				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.
			 */
			pr_warn("ES insert assertation failed for inode: %lu "
				"We can find blocks but we want to add a "
				"delayed/hole extent [%d/%d/%llu/%llx]\n",
				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) {
				pr_warn("ES insert assertation failed for "
					"inode: %lu retval %d != es_len %d\n",
					inode->i_ino, retval, es->es_len);
				return;
			}
			if (map.m_pblk != ext4_es_pblock(es)) {
				pr_warn("ES insert assertation failed for "
					"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)) {
			pr_warn("ES insert assertation failed for inode: %lu "
				"We can't find the block but we want to add "
				"an written extent [%d/%d/%llu/%llx]\n",
				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

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

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

/*
Z
Zheng Liu 已提交
635
 * ext4_es_insert_extent() adds a space to a extent status tree.
636 637 638 639 640 641
 *
 * ext4_es_insert_extent is called by ext4_da_write_begin and
 * ext4_es_remove_extent.
 *
 * Return 0 on success, error code on failure.
 */
Z
Zheng Liu 已提交
642
int ext4_es_insert_extent(struct inode *inode, ext4_lblk_t lblk,
643 644
			  ext4_lblk_t len, ext4_fsblk_t pblk,
			  unsigned long long status)
645
{
Z
Zheng Liu 已提交
646 647
	struct extent_status newes;
	ext4_lblk_t end = lblk + len - 1;
648 649
	int err = 0;

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

653 654 655
	if (!len)
		return 0;

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

	newes.es_lblk = lblk;
	newes.es_len = len;
660 661 662
	ext4_es_store_pblock(&newes, pblk);
	ext4_es_store_status(&newes, status);
	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
	err = __es_insert_extent(inode, &newes);
Z
Zheng Liu 已提交
671 672

error:
673 674
	write_unlock(&EXT4_I(inode)->i_es_lock);

675
	ext4_es_lru_add(inode);
676 677 678 679 680
	ext4_es_print_tree(inode);

	return err;
}

681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736
/*
 * 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);

737
	ext4_es_lru_add(inode);
738 739 740 741
	trace_ext4_es_lookup_extent_exit(inode, es, found);
	return found;
}

742 743
static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
			      ext4_lblk_t end)
744
{
745
	struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
746 747 748
	struct rb_node *node;
	struct extent_status *es;
	struct extent_status orig_es;
Z
Zheng Liu 已提交
749
	ext4_lblk_t len1, len2;
750
	ext4_fsblk_t block;
751 752
	int err = 0;

Z
Zheng Liu 已提交
753
	es = __es_tree_search(&tree->root, lblk);
754 755
	if (!es)
		goto out;
Z
Zheng Liu 已提交
756
	if (es->es_lblk > end)
757 758 759 760 761
		goto out;

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

Z
Zheng Liu 已提交
762 763
	orig_es.es_lblk = es->es_lblk;
	orig_es.es_len = es->es_len;
764 765
	orig_es.es_pblk = es->es_pblk;

Z
Zheng Liu 已提交
766 767
	len1 = lblk > es->es_lblk ? lblk - es->es_lblk : 0;
	len2 = ext4_es_end(es) > end ? ext4_es_end(es) - end : 0;
768
	if (len1 > 0)
Z
Zheng Liu 已提交
769
		es->es_len = len1;
770 771
	if (len2 > 0) {
		if (len1 > 0) {
Z
Zheng Liu 已提交
772 773 774 775
			struct extent_status newes;

			newes.es_lblk = end + 1;
			newes.es_len = len2;
776 777 778 779 780 781 782
			if (ext4_es_is_written(&orig_es) ||
			    ext4_es_is_unwritten(&orig_es)) {
				block = ext4_es_pblock(&orig_es) +
					orig_es.es_len - len2;
				ext4_es_store_pblock(&newes, block);
			}
			ext4_es_store_status(&newes, ext4_es_status(&orig_es));
783
			err = __es_insert_extent(inode, &newes);
784
			if (err) {
Z
Zheng Liu 已提交
785 786
				es->es_lblk = orig_es.es_lblk;
				es->es_len = orig_es.es_len;
787 788 789
				goto out;
			}
		} else {
Z
Zheng Liu 已提交
790 791
			es->es_lblk = end + 1;
			es->es_len = len2;
792 793 794 795 796
			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);
			}
797 798 799 800 801 802 803 804 805 806 807 808
		}
		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 已提交
809
	while (es && ext4_es_end(es) <= end) {
810 811
		node = rb_next(&es->rb_node);
		rb_erase(&es->rb_node, &tree->root);
812
		ext4_es_free_extent(inode, es);
813 814 815 816 817 818 819
		if (!node) {
			es = NULL;
			break;
		}
		es = rb_entry(node, struct extent_status, rb_node);
	}

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

Z
Zheng Liu 已提交
823 824 825
		len1 = ext4_es_end(es) - end;
		es->es_lblk = end + 1;
		es->es_len = len1;
826 827 828 829
		if (ext4_es_is_written(es) || ext4_es_is_unwritten(es)) {
			block = es->es_pblk + orig_len - len1;
			ext4_es_store_pblock(es, block);
		}
830 831 832
	}

out:
Z
Zheng Liu 已提交
833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850
	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);

851 852 853
	if (!len)
		return err;

Z
Zheng Liu 已提交
854 855 856 857
	end = lblk + len - 1;
	BUG_ON(end < lblk);

	write_lock(&EXT4_I(inode)->i_es_lock);
858
	err = __es_remove_extent(inode, lblk, end);
859 860 861 862
	write_unlock(&EXT4_I(inode)->i_es_lock);
	ext4_es_print_tree(inode);
	return err;
}
863

864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880
int ext4_es_zeroout(struct inode *inode, struct ext4_extent *ex)
{
	ext4_lblk_t  ee_block;
	ext4_fsblk_t ee_pblock;
	unsigned int ee_len;

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

	if (ee_len == 0)
		return 0;

	return ext4_es_insert_extent(inode, ee_block, ee_len, ee_pblock,
				     EXTENT_STATUS_WRITTEN);
}

881 882 883 884 885 886 887 888 889
static int ext4_es_shrink(struct shrinker *shrink, struct shrink_control *sc)
{
	struct ext4_sb_info *sbi = container_of(shrink,
					struct ext4_sb_info, s_es_shrinker);
	struct ext4_inode_info *ei;
	struct list_head *cur, *tmp, scanned;
	int nr_to_scan = sc->nr_to_scan;
	int ret, nr_shrunk = 0;

890
	ret = percpu_counter_read_positive(&sbi->s_extent_cache_cnt);
T
Theodore Ts'o 已提交
891
	trace_ext4_es_shrink_enter(sbi->s_sb, nr_to_scan, ret);
892 893

	if (!nr_to_scan)
T
Theodore Ts'o 已提交
894
		return ret;
895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922

	INIT_LIST_HEAD(&scanned);

	spin_lock(&sbi->s_es_lru_lock);
	list_for_each_safe(cur, tmp, &sbi->s_es_lru) {
		list_move_tail(cur, &scanned);

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

		read_lock(&ei->i_es_lock);
		if (ei->i_es_lru_nr == 0) {
			read_unlock(&ei->i_es_lock);
			continue;
		}
		read_unlock(&ei->i_es_lock);

		write_lock(&ei->i_es_lock);
		ret = __es_try_to_reclaim_extents(ei, nr_to_scan);
		write_unlock(&ei->i_es_lock);

		nr_shrunk += ret;
		nr_to_scan -= ret;
		if (nr_to_scan == 0)
			break;
	}
	list_splice_tail(&scanned, &sbi->s_es_lru);
	spin_unlock(&sbi->s_es_lru_lock);

923
	ret = percpu_counter_read_positive(&sbi->s_extent_cache_cnt);
T
Theodore Ts'o 已提交
924 925
	trace_ext4_es_shrink_exit(sbi->s_sb, nr_shrunk, ret);
	return ret;
926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999
}

void ext4_es_register_shrinker(struct super_block *sb)
{
	struct ext4_sb_info *sbi;

	sbi = EXT4_SB(sb);
	INIT_LIST_HEAD(&sbi->s_es_lru);
	spin_lock_init(&sbi->s_es_lru_lock);
	sbi->s_es_shrinker.shrink = ext4_es_shrink;
	sbi->s_es_shrinker.seeks = DEFAULT_SEEKS;
	register_shrinker(&sbi->s_es_shrinker);
}

void ext4_es_unregister_shrinker(struct super_block *sb)
{
	unregister_shrinker(&EXT4_SB(sb)->s_es_shrinker);
}

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

	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);
	else
		list_move_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;
	int nr_shrunk = 0;

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

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