extents_status.c 14.2 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;

Z
Zheng Liu 已提交
145 146 147 148 149
static int __es_insert_extent(struct ext4_es_tree *tree,
			      struct extent_status *newes);
static int __es_remove_extent(struct ext4_es_tree *tree, ext4_lblk_t lblk,
			      ext4_lblk_t end);

150 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
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);
Z
Zheng Liu 已提交
182
		printk(KERN_DEBUG " [%u/%u)", es->es_lblk, es->es_len);
183 184 185 186 187 188 189 190
		node = rb_next(node);
	}
	printk(KERN_DEBUG "\n");
}
#else
#define ext4_es_print_tree(inode)
#endif

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

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

Z
Zheng Liu 已提交
217
	if (es && lblk < es->es_lblk)
218 219
		return es;

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

	return NULL;
}

/*
Z
Zheng Liu 已提交
230 231
 * ext4_es_find_extent: find the 1st delayed extent covering @es->lblk
 * if it exists, otherwise, the next extent after @es->lblk.
232 233 234 235 236 237 238 239 240 241 242 243 244 245 246
 *
 * @inode: the inode which owns delayed extents
 * @es: delayed extent that we found
 *
 * Returns the first block of the next extent after es, otherwise
 * EXT_MAX_BLOCKS if no delay extent is found.
 * Delayed extent is returned via @es.
 */
ext4_lblk_t ext4_es_find_extent(struct inode *inode, struct extent_status *es)
{
	struct ext4_es_tree *tree = NULL;
	struct extent_status *es1 = NULL;
	struct rb_node *node;
	ext4_lblk_t ret = EXT_MAX_BLOCKS;

Z
Zheng Liu 已提交
247
	trace_ext4_es_find_extent_enter(inode, es->es_lblk);
248

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

	/* find delay extent in cache firstly */
	if (tree->cache_es) {
		es1 = tree->cache_es;
Z
Zheng Liu 已提交
255
		if (in_range(es->es_lblk, es1->es_lblk, es1->es_len)) {
256
			es_debug("%u cached by [%u/%u)\n",
Z
Zheng Liu 已提交
257
				 es->es_lblk, es1->es_lblk, es1->es_len);
258 259 260 261
			goto out;
		}
	}

Z
Zheng Liu 已提交
262 263
	es->es_len = 0;
	es1 = __es_tree_search(&tree->root, es->es_lblk);
264 265 266 267

out:
	if (es1) {
		tree->cache_es = es1;
Z
Zheng Liu 已提交
268 269
		es->es_lblk = es1->es_lblk;
		es->es_len = es1->es_len;
270 271 272
		node = rb_next(&es1->rb_node);
		if (node) {
			es1 = rb_entry(node, struct extent_status, rb_node);
Z
Zheng Liu 已提交
273
			ret = es1->es_lblk;
274 275 276 277
		}
	}

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

	trace_ext4_es_find_extent_exit(inode, es, ret);
280 281 282 283
	return ret;
}

static struct extent_status *
Z
Zheng Liu 已提交
284
ext4_es_alloc_extent(ext4_lblk_t lblk, ext4_lblk_t len)
285 286 287 288 289
{
	struct extent_status *es;
	es = kmem_cache_alloc(ext4_es_cachep, GFP_ATOMIC);
	if (es == NULL)
		return NULL;
Z
Zheng Liu 已提交
290 291
	es->es_lblk = lblk;
	es->es_len = len;
292 293 294 295 296 297 298 299
	return es;
}

static void ext4_es_free_extent(struct extent_status *es)
{
	kmem_cache_free(ext4_es_cachep, es);
}

Z
Zheng Liu 已提交
300 301 302 303 304 305 306 307 308 309 310 311 312 313
/*
 * Check whether or not two extents can be merged
 * Condition:
 *  - logical block number is contiguous
 */
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;

	return 1;
}

314 315 316 317 318 319 320 321 322 323 324
static struct extent_status *
ext4_es_try_to_merge_left(struct ext4_es_tree *tree, struct extent_status *es)
{
	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 已提交
325 326
	if (ext4_es_can_be_merged(es1, es)) {
		es1->es_len += es->es_len;
327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345
		rb_erase(&es->rb_node, &tree->root);
		ext4_es_free_extent(es);
		es = es1;
	}

	return es;
}

static struct extent_status *
ext4_es_try_to_merge_right(struct ext4_es_tree *tree, struct extent_status *es)
{
	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 已提交
346 347
	if (ext4_es_can_be_merged(es, es1)) {
		es->es_len += es1->es_len;
348 349 350 351 352 353 354
		rb_erase(node, &tree->root);
		ext4_es_free_extent(es1);
	}

	return es;
}

Z
Zheng Liu 已提交
355 356
static int __es_insert_extent(struct ext4_es_tree *tree,
			      struct extent_status *newes)
357 358 359 360 361 362 363 364 365
{
	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 已提交
366 367 368 369 370 371 372 373
		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;
374 375 376 377
				es = ext4_es_try_to_merge_left(tree, es);
				goto out;
			}
			p = &(*p)->rb_left;
Z
Zheng Liu 已提交
378 379 380
		} else if (newes->es_lblk > ext4_es_end(es)) {
			if (ext4_es_can_be_merged(es, newes)) {
				es->es_len += newes->es_len;
381 382 383 384 385
				es = ext4_es_try_to_merge_right(tree, es);
				goto out;
			}
			p = &(*p)->rb_right;
		} else {
Z
Zheng Liu 已提交
386 387
			BUG_ON(1);
			return -EINVAL;
388 389 390
		}
	}

Z
Zheng Liu 已提交
391
	es = ext4_es_alloc_extent(newes->es_lblk, newes->es_len);
392 393 394 395 396 397 398 399 400 401 402
	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 已提交
403
 * ext4_es_insert_extent() adds a space to a extent status tree.
404 405 406 407 408 409
 *
 * 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 已提交
410
int ext4_es_insert_extent(struct inode *inode, ext4_lblk_t lblk,
411 412 413
			  ext4_lblk_t len)
{
	struct ext4_es_tree *tree;
Z
Zheng Liu 已提交
414 415
	struct extent_status newes;
	ext4_lblk_t end = lblk + len - 1;
416 417
	int err = 0;

Z
Zheng Liu 已提交
418
	trace_ext4_es_insert_extent(inode, lblk, len);
419
	es_debug("add [%u/%u) to extent status tree of inode %lu\n",
Z
Zheng Liu 已提交
420 421 422 423 424 425
		 lblk, len, inode->i_ino);

	BUG_ON(end < lblk);

	newes.es_lblk = lblk;
	newes.es_len = len;
426 427 428

	write_lock(&EXT4_I(inode)->i_es_lock);
	tree = &EXT4_I(inode)->i_es_tree;
Z
Zheng Liu 已提交
429 430 431 432 433 434
	err = __es_remove_extent(tree, lblk, end);
	if (err != 0)
		goto error;
	err = __es_insert_extent(tree, &newes);

error:
435 436 437 438 439 440 441
	write_unlock(&EXT4_I(inode)->i_es_lock);

	ext4_es_print_tree(inode);

	return err;
}

Z
Zheng Liu 已提交
442 443
static int __es_remove_extent(struct ext4_es_tree *tree, ext4_lblk_t lblk,
				 ext4_lblk_t end)
444 445 446 447
{
	struct rb_node *node;
	struct extent_status *es;
	struct extent_status orig_es;
Z
Zheng Liu 已提交
448
	ext4_lblk_t len1, len2;
449 450
	int err = 0;

Z
Zheng Liu 已提交
451
	es = __es_tree_search(&tree->root, lblk);
452 453
	if (!es)
		goto out;
Z
Zheng Liu 已提交
454
	if (es->es_lblk > end)
455 456 457 458 459
		goto out;

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

Z
Zheng Liu 已提交
460 461 462 463
	orig_es.es_lblk = es->es_lblk;
	orig_es.es_len = es->es_len;
	len1 = lblk > es->es_lblk ? lblk - es->es_lblk : 0;
	len2 = ext4_es_end(es) > end ? ext4_es_end(es) - end : 0;
464
	if (len1 > 0)
Z
Zheng Liu 已提交
465
		es->es_len = len1;
466 467
	if (len2 > 0) {
		if (len1 > 0) {
Z
Zheng Liu 已提交
468 469 470 471 472
			struct extent_status newes;

			newes.es_lblk = end + 1;
			newes.es_len = len2;
			err = __es_insert_extent(tree, &newes);
473
			if (err) {
Z
Zheng Liu 已提交
474 475
				es->es_lblk = orig_es.es_lblk;
				es->es_len = orig_es.es_len;
476 477 478
				goto out;
			}
		} else {
Z
Zheng Liu 已提交
479 480
			es->es_lblk = end + 1;
			es->es_len = len2;
481 482 483 484 485 486 487 488 489 490 491 492
		}
		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 已提交
493
	while (es && ext4_es_end(es) <= end) {
494 495 496 497 498 499 500 501 502 503
		node = rb_next(&es->rb_node);
		rb_erase(&es->rb_node, &tree->root);
		ext4_es_free_extent(es);
		if (!node) {
			es = NULL;
			break;
		}
		es = rb_entry(node, struct extent_status, rb_node);
	}

Z
Zheng Liu 已提交
504 505 506 507
	if (es && es->es_lblk < end + 1) {
		len1 = ext4_es_end(es) - end;
		es->es_lblk = end + 1;
		es->es_len = len1;
508 509 510
	}

out:
Z
Zheng Liu 已提交
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
	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)
{
	struct ext4_es_tree *tree;
	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);

	end = lblk + len - 1;
	BUG_ON(end < lblk);

	tree = &EXT4_I(inode)->i_es_tree;

	write_lock(&EXT4_I(inode)->i_es_lock);
	err = __es_remove_extent(tree, lblk, end);
537 538 539 540
	write_unlock(&EXT4_I(inode)->i_es_lock);
	ext4_es_print_tree(inode);
	return err;
}