extents_status.c 21.0 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 150
static int __es_try_to_reclaim_extents(struct ext4_inode_info *ei,
				       int nr_to_scan);
static int ext4_es_reclaim_extents_count(struct super_block *sb);
Z
Zheng Liu 已提交
151

152 153 154 155 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
int __init ext4_init_es(void)
{
	ext4_es_cachep = KMEM_CACHE(extent_status, SLAB_RECLAIM_ACCOUNT);
	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);
184 185 186
		printk(KERN_DEBUG " [%u/%u) %llu %llx",
		       es->es_lblk, es->es_len,
		       ext4_es_pblock(es), ext4_es_status(es));
187 188 189 190 191 192 193 194
		node = rb_next(node);
	}
	printk(KERN_DEBUG "\n");
}
#else
#define ext4_es_print_tree(inode)
#endif

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

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

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

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

	return NULL;
}

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

248 249
	BUG_ON(es == NULL);
	trace_ext4_es_find_delayed_extent_enter(inode, lblk);
250

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

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

266
	es1 = __es_tree_search(&tree->root, lblk);
267 268

out:
269 270 271 272 273 274 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);
			if (ext4_es_is_delayed(es1))
				break;
		}
	}

	if (es1 && ext4_es_is_delayed(es1)) {
278
		tree->cache_es = es1;
Z
Zheng Liu 已提交
279 280
		es->es_lblk = es1->es_lblk;
		es->es_len = es1->es_len;
281
		es->es_pblk = es1->es_pblk;
282 283 284
	}

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

286
	ext4_es_lru_add(inode);
287
	trace_ext4_es_find_delayed_extent_exit(inode, es);
288 289 290
}

static struct extent_status *
291 292
ext4_es_alloc_extent(struct inode *inode, ext4_lblk_t lblk, ext4_lblk_t len,
		     ext4_fsblk_t pblk)
293 294 295 296 297
{
	struct extent_status *es;
	es = kmem_cache_alloc(ext4_es_cachep, GFP_ATOMIC);
	if (es == NULL)
		return NULL;
Z
Zheng Liu 已提交
298 299
	es->es_lblk = lblk;
	es->es_len = len;
300
	es->es_pblk = pblk;
301 302 303 304 305 306 307

	/*
	 * We don't count delayed extent because we never try to reclaim them
	 */
	if (!ext4_es_is_delayed(es))
		EXT4_I(inode)->i_es_lru_nr++;

308 309 310
	return es;
}

311
static void ext4_es_free_extent(struct inode *inode, struct extent_status *es)
312
{
313 314 315 316 317 318
	/* 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--;
	}

319 320 321
	kmem_cache_free(ext4_es_cachep, es);
}

Z
Zheng Liu 已提交
322 323 324 325
/*
 * Check whether or not two extents can be merged
 * Condition:
 *  - logical block number is contiguous
326 327
 *  - physical block number is contiguous
 *  - status is equal
Z
Zheng Liu 已提交
328 329 330 331 332 333 334
 */
static int ext4_es_can_be_merged(struct extent_status *es1,
				 struct extent_status *es2)
{
	if (es1->es_lblk + es1->es_len != es2->es_lblk)
		return 0;

335 336 337 338 339 340 341
	if (ext4_es_status(es1) != ext4_es_status(es2))
		return 0;

	if ((ext4_es_is_written(es1) || ext4_es_is_unwritten(es1)) &&
	    (ext4_es_pblock(es1) + es1->es_len != ext4_es_pblock(es2)))
		return 0;

Z
Zheng Liu 已提交
342 343 344
	return 1;
}

345
static struct extent_status *
346
ext4_es_try_to_merge_left(struct inode *inode, struct extent_status *es)
347
{
348
	struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
349 350 351 352 353 354 355 356
	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 已提交
357 358
	if (ext4_es_can_be_merged(es1, es)) {
		es1->es_len += es->es_len;
359
		rb_erase(&es->rb_node, &tree->root);
360
		ext4_es_free_extent(inode, es);
361 362 363 364 365 366 367
		es = es1;
	}

	return es;
}

static struct extent_status *
368
ext4_es_try_to_merge_right(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_next(&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(es, es1)) {
		es->es_len += es1->es_len;
381
		rb_erase(node, &tree->root);
382
		ext4_es_free_extent(inode, es1);
383 384 385 386 387
	}

	return es;
}

388
static int __es_insert_extent(struct inode *inode, struct extent_status *newes)
389
{
390
	struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
391 392 393 394 395 396 397 398
	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 已提交
399 400 401 402 403 404 405 406
		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;
407 408 409 410
				if (ext4_es_is_written(es) ||
				    ext4_es_is_unwritten(es))
					ext4_es_store_pblock(es,
							     newes->es_pblk);
411
				es = ext4_es_try_to_merge_left(inode, es);
412 413 414
				goto out;
			}
			p = &(*p)->rb_left;
Z
Zheng Liu 已提交
415 416 417
		} else if (newes->es_lblk > ext4_es_end(es)) {
			if (ext4_es_can_be_merged(es, newes)) {
				es->es_len += newes->es_len;
418
				es = ext4_es_try_to_merge_right(inode, es);
419 420 421 422
				goto out;
			}
			p = &(*p)->rb_right;
		} else {
Z
Zheng Liu 已提交
423 424
			BUG_ON(1);
			return -EINVAL;
425 426 427
		}
	}

428
	es = ext4_es_alloc_extent(inode, newes->es_lblk, newes->es_len,
429
				  newes->es_pblk);
430 431 432 433 434 435 436 437 438 439 440
	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 已提交
441
 * ext4_es_insert_extent() adds a space to a extent status tree.
442 443 444 445 446 447
 *
 * 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 已提交
448
int ext4_es_insert_extent(struct inode *inode, ext4_lblk_t lblk,
449 450
			  ext4_lblk_t len, ext4_fsblk_t pblk,
			  unsigned long long status)
451
{
Z
Zheng Liu 已提交
452 453
	struct extent_status newes;
	ext4_lblk_t end = lblk + len - 1;
454 455
	int err = 0;

456 457
	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 已提交
458

459 460 461
	if (!len)
		return 0;

Z
Zheng Liu 已提交
462 463 464 465
	BUG_ON(end < lblk);

	newes.es_lblk = lblk;
	newes.es_len = len;
466 467 468
	ext4_es_store_pblock(&newes, pblk);
	ext4_es_store_status(&newes, status);
	trace_ext4_es_insert_extent(inode, &newes);
469 470

	write_lock(&EXT4_I(inode)->i_es_lock);
471
	err = __es_remove_extent(inode, lblk, end);
Z
Zheng Liu 已提交
472 473
	if (err != 0)
		goto error;
474
	err = __es_insert_extent(inode, &newes);
Z
Zheng Liu 已提交
475 476

error:
477 478
	write_unlock(&EXT4_I(inode)->i_es_lock);

479
	ext4_es_lru_add(inode);
480 481 482 483 484
	ext4_es_print_tree(inode);

	return err;
}

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

541
	ext4_es_lru_add(inode);
542 543 544 545
	trace_ext4_es_lookup_extent_exit(inode, es, found);
	return found;
}

546 547
static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
			      ext4_lblk_t end)
548
{
549
	struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
550 551 552
	struct rb_node *node;
	struct extent_status *es;
	struct extent_status orig_es;
Z
Zheng Liu 已提交
553
	ext4_lblk_t len1, len2;
554
	ext4_fsblk_t block;
555 556
	int err = 0;

Z
Zheng Liu 已提交
557
	es = __es_tree_search(&tree->root, lblk);
558 559
	if (!es)
		goto out;
Z
Zheng Liu 已提交
560
	if (es->es_lblk > end)
561 562 563 564 565
		goto out;

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

Z
Zheng Liu 已提交
566 567
	orig_es.es_lblk = es->es_lblk;
	orig_es.es_len = es->es_len;
568 569
	orig_es.es_pblk = es->es_pblk;

Z
Zheng Liu 已提交
570 571
	len1 = lblk > es->es_lblk ? lblk - es->es_lblk : 0;
	len2 = ext4_es_end(es) > end ? ext4_es_end(es) - end : 0;
572
	if (len1 > 0)
Z
Zheng Liu 已提交
573
		es->es_len = len1;
574 575
	if (len2 > 0) {
		if (len1 > 0) {
Z
Zheng Liu 已提交
576 577 578 579
			struct extent_status newes;

			newes.es_lblk = end + 1;
			newes.es_len = len2;
580 581 582 583 584 585 586
			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));
587
			err = __es_insert_extent(inode, &newes);
588
			if (err) {
Z
Zheng Liu 已提交
589 590
				es->es_lblk = orig_es.es_lblk;
				es->es_len = orig_es.es_len;
591 592 593
				goto out;
			}
		} else {
Z
Zheng Liu 已提交
594 595
			es->es_lblk = end + 1;
			es->es_len = len2;
596 597 598 599 600
			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);
			}
601 602 603 604 605 606 607 608 609 610 611 612
		}
		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 已提交
613
	while (es && ext4_es_end(es) <= end) {
614 615
		node = rb_next(&es->rb_node);
		rb_erase(&es->rb_node, &tree->root);
616
		ext4_es_free_extent(inode, es);
617 618 619 620 621 622 623
		if (!node) {
			es = NULL;
			break;
		}
		es = rb_entry(node, struct extent_status, rb_node);
	}

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

Z
Zheng Liu 已提交
627 628 629
		len1 = ext4_es_end(es) - end;
		es->es_lblk = end + 1;
		es->es_len = len1;
630 631 632 633
		if (ext4_es_is_written(es) || ext4_es_is_unwritten(es)) {
			block = es->es_pblk + orig_len - len1;
			ext4_es_store_pblock(es, block);
		}
634 635 636
	}

out:
Z
Zheng Liu 已提交
637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654
	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);

655 656 657
	if (!len)
		return err;

Z
Zheng Liu 已提交
658 659 660 661
	end = lblk + len - 1;
	BUG_ON(end < lblk);

	write_lock(&EXT4_I(inode)->i_es_lock);
662
	err = __es_remove_extent(inode, lblk, end);
663 664 665 666
	write_unlock(&EXT4_I(inode)->i_es_lock);
	ext4_es_print_tree(inode);
	return err;
}
667 668 669 670 671 672 673 674 675 676 677 678 679 680 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 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 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803

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;

	trace_ext4_es_shrink_enter(sbi->s_sb, nr_to_scan);

	if (!nr_to_scan)
		return ext4_es_reclaim_extents_count(sbi->s_sb);

	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);
	trace_ext4_es_shrink_exit(sbi->s_sb, nr_shrunk);

	return ext4_es_reclaim_extents_count(sbi->s_sb);
}

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 ext4_es_reclaim_extents_count(struct super_block *sb)
{
	struct ext4_sb_info *sbi = EXT4_SB(sb);
	struct ext4_inode_info *ei;
	struct list_head *cur;
	int nr_cached = 0;

	spin_lock(&sbi->s_es_lru_lock);
	list_for_each(cur, &sbi->s_es_lru) {
		ei = list_entry(cur, struct ext4_inode_info, i_es_lru);
		read_lock(&ei->i_es_lock);
		nr_cached += ei->i_es_lru_nr;
		read_unlock(&ei->i_es_lock);
	}
	spin_unlock(&sbi->s_es_lru_lock);
	trace_ext4_es_reclaim_extents_count(sb, nr_cached);
	return nr_cached;
}

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