1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  *  fs/ext4/extents_status.c
4  *
5  * Written by Yongqiang Yang <xiaoqiangnk@gmail.com>
6  * Modified by
7  *	Allison Henderson <achender@linux.vnet.ibm.com>
8  *	Hugh Dickins <hughd@google.com>
9  *	Zheng Liu <wenqing.lz@taobao.com>
10  *
11  * Ext4 extents status tree core functions.
12  */
13 #include <linux/list_sort.h>
14 #include <linux/proc_fs.h>
15 #include <linux/seq_file.h>
16 #include "ext4.h"
17 
18 #include <trace/events/ext4.h>
19 
20 /*
21  * According to previous discussion in Ext4 Developer Workshop, we
22  * will introduce a new structure called io tree to track all extent
23  * status in order to solve some problems that we have met
24  * (e.g. Reservation space warning), and provide extent-level locking.
25  * Delay extent tree is the first step to achieve this goal.  It is
26  * original built by Yongqiang Yang.  At that time it is called delay
27  * extent tree, whose goal is only track delayed extents in memory to
28  * simplify the implementation of fiemap and bigalloc, and introduce
29  * lseek SEEK_DATA/SEEK_HOLE support.  That is why it is still called
30  * delay extent tree at the first commit.  But for better understand
31  * what it does, it has been rename to extent status tree.
32  *
33  * Step1:
34  * Currently the first step has been done.  All delayed extents are
35  * tracked in the tree.  It maintains the delayed extent when a delayed
36  * allocation is issued, and the delayed extent is written out or
37  * invalidated.  Therefore the implementation of fiemap and bigalloc
38  * are simplified, and SEEK_DATA/SEEK_HOLE are introduced.
39  *
40  * The following comment describes the implemenmtation of extent
41  * status tree and future works.
42  *
43  * Step2:
44  * In this step all extent status are tracked by extent status tree.
45  * Thus, we can first try to lookup a block mapping in this tree before
46  * finding it in extent tree.  Hence, single extent cache can be removed
47  * because extent status tree can do a better job.  Extents in status
48  * tree are loaded on-demand.  Therefore, the extent status tree may not
49  * contain all of the extents in a file.  Meanwhile we define a shrinker
50  * to reclaim memory from extent status tree because fragmented extent
51  * tree will make status tree cost too much memory.  written/unwritten/-
52  * hole extents in the tree will be reclaimed by this shrinker when we
53  * are under high memory pressure.  Delayed extents will not be
54  * reclimed because fiemap, bigalloc, and seek_data/hole need it.
55  */
56 
57 /*
58  * Extent status tree implementation for ext4.
59  *
60  *
61  * ==========================================================================
62  * Extent status tree tracks all extent status.
63  *
64  * 1. Why we need to implement extent status tree?
65  *
66  * Without extent status tree, ext4 identifies a delayed extent by looking
67  * up page cache, this has several deficiencies - complicated, buggy,
68  * and inefficient code.
69  *
70  * FIEMAP, SEEK_HOLE/DATA, bigalloc, and writeout all need to know if a
71  * block or a range of blocks are belonged to a delayed extent.
72  *
73  * Let us have a look at how they do without extent status tree.
74  *   --	FIEMAP
75  *	FIEMAP looks up page cache to identify delayed allocations from holes.
76  *
77  *   --	SEEK_HOLE/DATA
78  *	SEEK_HOLE/DATA has the same problem as FIEMAP.
79  *
80  *   --	bigalloc
81  *	bigalloc looks up page cache to figure out if a block is
82  *	already under delayed allocation or not to determine whether
83  *	quota reserving is needed for the cluster.
84  *
85  *   --	writeout
86  *	Writeout looks up whole page cache to see if a buffer is
87  *	mapped, If there are not very many delayed buffers, then it is
88  *	time consuming.
89  *
90  * With extent status tree implementation, FIEMAP, SEEK_HOLE/DATA,
91  * bigalloc and writeout can figure out if a block or a range of
92  * blocks is under delayed allocation(belonged to a delayed extent) or
93  * not by searching the extent tree.
94  *
95  *
96  * ==========================================================================
97  * 2. Ext4 extent status tree impelmentation
98  *
99  *   --	extent
100  *	A extent is a range of blocks which are contiguous logically and
101  *	physically.  Unlike extent in extent tree, this extent in ext4 is
102  *	a in-memory struct, there is no corresponding on-disk data.  There
103  *	is no limit on length of extent, so an extent can contain as many
104  *	blocks as they are contiguous logically and physically.
105  *
106  *   --	extent status tree
107  *	Every inode has an extent status tree and all allocation blocks
108  *	are added to the tree with different status.  The extent in the
109  *	tree are ordered by logical block no.
110  *
111  *   --	operations on a extent status tree
112  *	There are three important operations on a delayed extent tree: find
113  *	next extent, adding a extent(a range of blocks) and removing a extent.
114  *
115  *   --	race on a extent status tree
116  *	Extent status tree is protected by inode->i_es_lock.
117  *
118  *   --	memory consumption
119  *      Fragmented extent tree will make extent status tree cost too much
120  *      memory.  Hence, we will reclaim written/unwritten/hole extents from
121  *      the tree under a heavy memory pressure.
122  *
123  *
124  * ==========================================================================
125  * 3. Performance analysis
126  *
127  *   --	overhead
128  *	1. There is a cache extent for write access, so if writes are
129  *	not very random, adding space operaions are in O(1) time.
130  *
131  *   --	gain
132  *	2. Code is much simpler, more readable, more maintainable and
133  *	more efficient.
134  *
135  *
136  * ==========================================================================
137  * 4. TODO list
138  *
139  *   -- Refactor delayed space reservation
140  *
141  *   -- Extent-level locking
142  */
143 
144 static struct kmem_cache *ext4_es_cachep;
145 static struct kmem_cache *ext4_pending_cachep;
146 
147 static int __es_insert_extent(struct inode *inode, struct extent_status *newes);
148 static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
149 			      ext4_lblk_t end, int *reserved);
150 static int es_reclaim_extents(struct ext4_inode_info *ei, int *nr_to_scan);
151 static int __es_shrink(struct ext4_sb_info *sbi, int nr_to_scan,
152 		       struct ext4_inode_info *locked_ei);
153 static void __revise_pending(struct inode *inode, ext4_lblk_t lblk,
154 			     ext4_lblk_t len);
155 
ext4_init_es(void)156 int __init ext4_init_es(void)
157 {
158 	ext4_es_cachep = kmem_cache_create("ext4_extent_status",
159 					   sizeof(struct extent_status),
160 					   0, (SLAB_RECLAIM_ACCOUNT), NULL);
161 	if (ext4_es_cachep == NULL)
162 		return -ENOMEM;
163 	return 0;
164 }
165 
ext4_exit_es(void)166 void ext4_exit_es(void)
167 {
168 	kmem_cache_destroy(ext4_es_cachep);
169 }
170 
ext4_es_init_tree(struct ext4_es_tree * tree)171 void ext4_es_init_tree(struct ext4_es_tree *tree)
172 {
173 	tree->root = RB_ROOT;
174 	tree->cache_es = NULL;
175 }
176 
177 #ifdef ES_DEBUG__
ext4_es_print_tree(struct inode * inode)178 static void ext4_es_print_tree(struct inode *inode)
179 {
180 	struct ext4_es_tree *tree;
181 	struct rb_node *node;
182 
183 	printk(KERN_DEBUG "status extents for inode %lu:", inode->i_ino);
184 	tree = &EXT4_I(inode)->i_es_tree;
185 	node = rb_first(&tree->root);
186 	while (node) {
187 		struct extent_status *es;
188 		es = rb_entry(node, struct extent_status, rb_node);
189 		printk(KERN_DEBUG " [%u/%u) %llu %x",
190 		       es->es_lblk, es->es_len,
191 		       ext4_es_pblock(es), ext4_es_status(es));
192 		node = rb_next(node);
193 	}
194 	printk(KERN_DEBUG "\n");
195 }
196 #else
197 #define ext4_es_print_tree(inode)
198 #endif
199 
ext4_es_end(struct extent_status * es)200 static inline ext4_lblk_t ext4_es_end(struct extent_status *es)
201 {
202 	BUG_ON(es->es_lblk + es->es_len < es->es_lblk);
203 	return es->es_lblk + es->es_len - 1;
204 }
205 
206 /*
207  * search through the tree for an delayed extent with a given offset.  If
208  * it can't be found, try to find next extent.
209  */
__es_tree_search(struct rb_root * root,ext4_lblk_t lblk)210 static struct extent_status *__es_tree_search(struct rb_root *root,
211 					      ext4_lblk_t lblk)
212 {
213 	struct rb_node *node = root->rb_node;
214 	struct extent_status *es = NULL;
215 
216 	while (node) {
217 		es = rb_entry(node, struct extent_status, rb_node);
218 		if (lblk < es->es_lblk)
219 			node = node->rb_left;
220 		else if (lblk > ext4_es_end(es))
221 			node = node->rb_right;
222 		else
223 			return es;
224 	}
225 
226 	if (es && lblk < es->es_lblk)
227 		return es;
228 
229 	if (es && lblk > ext4_es_end(es)) {
230 		node = rb_next(&es->rb_node);
231 		return node ? rb_entry(node, struct extent_status, rb_node) :
232 			      NULL;
233 	}
234 
235 	return NULL;
236 }
237 
238 /*
239  * ext4_es_find_extent_range - find extent with specified status within block
240  *                             range or next extent following block range in
241  *                             extents status tree
242  *
243  * @inode - file containing the range
244  * @matching_fn - pointer to function that matches extents with desired status
245  * @lblk - logical block defining start of range
246  * @end - logical block defining end of range
247  * @es - extent found, if any
248  *
249  * Find the first extent within the block range specified by @lblk and @end
250  * in the extents status tree that satisfies @matching_fn.  If a match
251  * is found, it's returned in @es.  If not, and a matching extent is found
252  * beyond the block range, it's returned in @es.  If no match is found, an
253  * extent is returned in @es whose es_lblk, es_len, and es_pblk components
254  * are 0.
255  */
__es_find_extent_range(struct inode * inode,int (* matching_fn)(struct extent_status * es),ext4_lblk_t lblk,ext4_lblk_t end,struct extent_status * es)256 static void __es_find_extent_range(struct inode *inode,
257 				   int (*matching_fn)(struct extent_status *es),
258 				   ext4_lblk_t lblk, ext4_lblk_t end,
259 				   struct extent_status *es)
260 {
261 	struct ext4_es_tree *tree = NULL;
262 	struct extent_status *es1 = NULL;
263 	struct rb_node *node;
264 
265 	WARN_ON(es == NULL);
266 	WARN_ON(end < lblk);
267 
268 	tree = &EXT4_I(inode)->i_es_tree;
269 
270 	/* see if the extent has been cached */
271 	es->es_lblk = es->es_len = es->es_pblk = 0;
272 	if (tree->cache_es) {
273 		es1 = tree->cache_es;
274 		if (in_range(lblk, es1->es_lblk, es1->es_len)) {
275 			es_debug("%u cached by [%u/%u) %llu %x\n",
276 				 lblk, es1->es_lblk, es1->es_len,
277 				 ext4_es_pblock(es1), ext4_es_status(es1));
278 			goto out;
279 		}
280 	}
281 
282 	es1 = __es_tree_search(&tree->root, lblk);
283 
284 out:
285 	if (es1 && !matching_fn(es1)) {
286 		while ((node = rb_next(&es1->rb_node)) != NULL) {
287 			es1 = rb_entry(node, struct extent_status, rb_node);
288 			if (es1->es_lblk > end) {
289 				es1 = NULL;
290 				break;
291 			}
292 			if (matching_fn(es1))
293 				break;
294 		}
295 	}
296 
297 	if (es1 && matching_fn(es1)) {
298 		tree->cache_es = es1;
299 		es->es_lblk = es1->es_lblk;
300 		es->es_len = es1->es_len;
301 		es->es_pblk = es1->es_pblk;
302 	}
303 
304 }
305 
306 /*
307  * Locking for __es_find_extent_range() for external use
308  */
ext4_es_find_extent_range(struct inode * inode,int (* matching_fn)(struct extent_status * es),ext4_lblk_t lblk,ext4_lblk_t end,struct extent_status * es)309 void ext4_es_find_extent_range(struct inode *inode,
310 			       int (*matching_fn)(struct extent_status *es),
311 			       ext4_lblk_t lblk, ext4_lblk_t end,
312 			       struct extent_status *es)
313 {
314 	if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY)
315 		return;
316 
317 	trace_ext4_es_find_extent_range_enter(inode, lblk);
318 
319 	read_lock(&EXT4_I(inode)->i_es_lock);
320 	__es_find_extent_range(inode, matching_fn, lblk, end, es);
321 	read_unlock(&EXT4_I(inode)->i_es_lock);
322 
323 	trace_ext4_es_find_extent_range_exit(inode, es);
324 }
325 
326 /*
327  * __es_scan_range - search block range for block with specified status
328  *                   in extents status tree
329  *
330  * @inode - file containing the range
331  * @matching_fn - pointer to function that matches extents with desired status
332  * @lblk - logical block defining start of range
333  * @end - logical block defining end of range
334  *
335  * Returns true if at least one block in the specified block range satisfies
336  * the criterion specified by @matching_fn, and false if not.  If at least
337  * one extent has the specified status, then there is at least one block
338  * in the cluster with that status.  Should only be called by code that has
339  * taken i_es_lock.
340  */
__es_scan_range(struct inode * inode,int (* matching_fn)(struct extent_status * es),ext4_lblk_t start,ext4_lblk_t end)341 static bool __es_scan_range(struct inode *inode,
342 			    int (*matching_fn)(struct extent_status *es),
343 			    ext4_lblk_t start, ext4_lblk_t end)
344 {
345 	struct extent_status es;
346 
347 	__es_find_extent_range(inode, matching_fn, start, end, &es);
348 	if (es.es_len == 0)
349 		return false;   /* no matching extent in the tree */
350 	else if (es.es_lblk <= start &&
351 		 start < es.es_lblk + es.es_len)
352 		return true;
353 	else if (start <= es.es_lblk && es.es_lblk <= end)
354 		return true;
355 	else
356 		return false;
357 }
358 /*
359  * Locking for __es_scan_range() for external use
360  */
ext4_es_scan_range(struct inode * inode,int (* matching_fn)(struct extent_status * es),ext4_lblk_t lblk,ext4_lblk_t end)361 bool ext4_es_scan_range(struct inode *inode,
362 			int (*matching_fn)(struct extent_status *es),
363 			ext4_lblk_t lblk, ext4_lblk_t end)
364 {
365 	bool ret;
366 
367 	if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY)
368 		return false;
369 
370 	read_lock(&EXT4_I(inode)->i_es_lock);
371 	ret = __es_scan_range(inode, matching_fn, lblk, end);
372 	read_unlock(&EXT4_I(inode)->i_es_lock);
373 
374 	return ret;
375 }
376 
377 /*
378  * __es_scan_clu - search cluster for block with specified status in
379  *                 extents status tree
380  *
381  * @inode - file containing the cluster
382  * @matching_fn - pointer to function that matches extents with desired status
383  * @lblk - logical block in cluster to be searched
384  *
385  * Returns true if at least one extent in the cluster containing @lblk
386  * satisfies the criterion specified by @matching_fn, and false if not.  If at
387  * least one extent has the specified status, then there is at least one block
388  * in the cluster with that status.  Should only be called by code that has
389  * taken i_es_lock.
390  */
__es_scan_clu(struct inode * inode,int (* matching_fn)(struct extent_status * es),ext4_lblk_t lblk)391 static bool __es_scan_clu(struct inode *inode,
392 			  int (*matching_fn)(struct extent_status *es),
393 			  ext4_lblk_t lblk)
394 {
395 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
396 	ext4_lblk_t lblk_start, lblk_end;
397 
398 	lblk_start = EXT4_LBLK_CMASK(sbi, lblk);
399 	lblk_end = lblk_start + sbi->s_cluster_ratio - 1;
400 
401 	return __es_scan_range(inode, matching_fn, lblk_start, lblk_end);
402 }
403 
404 /*
405  * Locking for __es_scan_clu() for external use
406  */
ext4_es_scan_clu(struct inode * inode,int (* matching_fn)(struct extent_status * es),ext4_lblk_t lblk)407 bool ext4_es_scan_clu(struct inode *inode,
408 		      int (*matching_fn)(struct extent_status *es),
409 		      ext4_lblk_t lblk)
410 {
411 	bool ret;
412 
413 	if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY)
414 		return false;
415 
416 	read_lock(&EXT4_I(inode)->i_es_lock);
417 	ret = __es_scan_clu(inode, matching_fn, lblk);
418 	read_unlock(&EXT4_I(inode)->i_es_lock);
419 
420 	return ret;
421 }
422 
ext4_es_list_add(struct inode * inode)423 static void ext4_es_list_add(struct inode *inode)
424 {
425 	struct ext4_inode_info *ei = EXT4_I(inode);
426 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
427 
428 	if (!list_empty(&ei->i_es_list))
429 		return;
430 
431 	spin_lock(&sbi->s_es_lock);
432 	if (list_empty(&ei->i_es_list)) {
433 		list_add_tail(&ei->i_es_list, &sbi->s_es_list);
434 		sbi->s_es_nr_inode++;
435 	}
436 	spin_unlock(&sbi->s_es_lock);
437 }
438 
ext4_es_list_del(struct inode * inode)439 static void ext4_es_list_del(struct inode *inode)
440 {
441 	struct ext4_inode_info *ei = EXT4_I(inode);
442 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
443 
444 	spin_lock(&sbi->s_es_lock);
445 	if (!list_empty(&ei->i_es_list)) {
446 		list_del_init(&ei->i_es_list);
447 		sbi->s_es_nr_inode--;
448 		WARN_ON_ONCE(sbi->s_es_nr_inode < 0);
449 	}
450 	spin_unlock(&sbi->s_es_lock);
451 }
452 
453 static struct extent_status *
ext4_es_alloc_extent(struct inode * inode,ext4_lblk_t lblk,ext4_lblk_t len,ext4_fsblk_t pblk)454 ext4_es_alloc_extent(struct inode *inode, ext4_lblk_t lblk, ext4_lblk_t len,
455 		     ext4_fsblk_t pblk)
456 {
457 	struct extent_status *es;
458 	es = kmem_cache_alloc(ext4_es_cachep, GFP_ATOMIC);
459 	if (es == NULL)
460 		return NULL;
461 	es->es_lblk = lblk;
462 	es->es_len = len;
463 	es->es_pblk = pblk;
464 
465 	/*
466 	 * We don't count delayed extent because we never try to reclaim them
467 	 */
468 	if (!ext4_es_is_delayed(es)) {
469 		if (!EXT4_I(inode)->i_es_shk_nr++)
470 			ext4_es_list_add(inode);
471 		percpu_counter_inc(&EXT4_SB(inode->i_sb)->
472 					s_es_stats.es_stats_shk_cnt);
473 	}
474 
475 	EXT4_I(inode)->i_es_all_nr++;
476 	percpu_counter_inc(&EXT4_SB(inode->i_sb)->s_es_stats.es_stats_all_cnt);
477 
478 	return es;
479 }
480 
ext4_es_free_extent(struct inode * inode,struct extent_status * es)481 static void ext4_es_free_extent(struct inode *inode, struct extent_status *es)
482 {
483 	EXT4_I(inode)->i_es_all_nr--;
484 	percpu_counter_dec(&EXT4_SB(inode->i_sb)->s_es_stats.es_stats_all_cnt);
485 
486 	/* Decrease the shrink counter when this es is not delayed */
487 	if (!ext4_es_is_delayed(es)) {
488 		BUG_ON(EXT4_I(inode)->i_es_shk_nr == 0);
489 		if (!--EXT4_I(inode)->i_es_shk_nr)
490 			ext4_es_list_del(inode);
491 		percpu_counter_dec(&EXT4_SB(inode->i_sb)->
492 					s_es_stats.es_stats_shk_cnt);
493 	}
494 
495 	kmem_cache_free(ext4_es_cachep, es);
496 }
497 
498 /*
499  * Check whether or not two extents can be merged
500  * Condition:
501  *  - logical block number is contiguous
502  *  - physical block number is contiguous
503  *  - status is equal
504  */
ext4_es_can_be_merged(struct extent_status * es1,struct extent_status * es2)505 static int ext4_es_can_be_merged(struct extent_status *es1,
506 				 struct extent_status *es2)
507 {
508 	if (ext4_es_type(es1) != ext4_es_type(es2))
509 		return 0;
510 
511 	if (((__u64) es1->es_len) + es2->es_len > EXT_MAX_BLOCKS) {
512 		pr_warn("ES assertion failed when merging extents. "
513 			"The sum of lengths of es1 (%d) and es2 (%d) "
514 			"is bigger than allowed file size (%d)\n",
515 			es1->es_len, es2->es_len, EXT_MAX_BLOCKS);
516 		WARN_ON(1);
517 		return 0;
518 	}
519 
520 	if (((__u64) es1->es_lblk) + es1->es_len != es2->es_lblk)
521 		return 0;
522 
523 	if ((ext4_es_is_written(es1) || ext4_es_is_unwritten(es1)) &&
524 	    (ext4_es_pblock(es1) + es1->es_len == ext4_es_pblock(es2)))
525 		return 1;
526 
527 	if (ext4_es_is_hole(es1))
528 		return 1;
529 
530 	/* we need to check delayed extent is without unwritten status */
531 	if (ext4_es_is_delayed(es1) && !ext4_es_is_unwritten(es1))
532 		return 1;
533 
534 	return 0;
535 }
536 
537 static struct extent_status *
ext4_es_try_to_merge_left(struct inode * inode,struct extent_status * es)538 ext4_es_try_to_merge_left(struct inode *inode, struct extent_status *es)
539 {
540 	struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
541 	struct extent_status *es1;
542 	struct rb_node *node;
543 
544 	node = rb_prev(&es->rb_node);
545 	if (!node)
546 		return es;
547 
548 	es1 = rb_entry(node, struct extent_status, rb_node);
549 	if (ext4_es_can_be_merged(es1, es)) {
550 		es1->es_len += es->es_len;
551 		if (ext4_es_is_referenced(es))
552 			ext4_es_set_referenced(es1);
553 		rb_erase(&es->rb_node, &tree->root);
554 		ext4_es_free_extent(inode, es);
555 		es = es1;
556 	}
557 
558 	return es;
559 }
560 
561 static struct extent_status *
ext4_es_try_to_merge_right(struct inode * inode,struct extent_status * es)562 ext4_es_try_to_merge_right(struct inode *inode, struct extent_status *es)
563 {
564 	struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
565 	struct extent_status *es1;
566 	struct rb_node *node;
567 
568 	node = rb_next(&es->rb_node);
569 	if (!node)
570 		return es;
571 
572 	es1 = rb_entry(node, struct extent_status, rb_node);
573 	if (ext4_es_can_be_merged(es, es1)) {
574 		es->es_len += es1->es_len;
575 		if (ext4_es_is_referenced(es1))
576 			ext4_es_set_referenced(es);
577 		rb_erase(node, &tree->root);
578 		ext4_es_free_extent(inode, es1);
579 	}
580 
581 	return es;
582 }
583 
584 #ifdef ES_AGGRESSIVE_TEST
585 #include "ext4_extents.h"	/* Needed when ES_AGGRESSIVE_TEST is defined */
586 
ext4_es_insert_extent_ext_check(struct inode * inode,struct extent_status * es)587 static void ext4_es_insert_extent_ext_check(struct inode *inode,
588 					    struct extent_status *es)
589 {
590 	struct ext4_ext_path *path = NULL;
591 	struct ext4_extent *ex;
592 	ext4_lblk_t ee_block;
593 	ext4_fsblk_t ee_start;
594 	unsigned short ee_len;
595 	int depth, ee_status, es_status;
596 
597 	path = ext4_find_extent(inode, es->es_lblk, NULL, EXT4_EX_NOCACHE);
598 	if (IS_ERR(path))
599 		return;
600 
601 	depth = ext_depth(inode);
602 	ex = path[depth].p_ext;
603 
604 	if (ex) {
605 
606 		ee_block = le32_to_cpu(ex->ee_block);
607 		ee_start = ext4_ext_pblock(ex);
608 		ee_len = ext4_ext_get_actual_len(ex);
609 
610 		ee_status = ext4_ext_is_unwritten(ex) ? 1 : 0;
611 		es_status = ext4_es_is_unwritten(es) ? 1 : 0;
612 
613 		/*
614 		 * Make sure ex and es are not overlap when we try to insert
615 		 * a delayed/hole extent.
616 		 */
617 		if (!ext4_es_is_written(es) && !ext4_es_is_unwritten(es)) {
618 			if (in_range(es->es_lblk, ee_block, ee_len)) {
619 				pr_warn("ES insert assertion failed for "
620 					"inode: %lu we can find an extent "
621 					"at block [%d/%d/%llu/%c], but we "
622 					"want to add a delayed/hole extent "
623 					"[%d/%d/%llu/%x]\n",
624 					inode->i_ino, ee_block, ee_len,
625 					ee_start, ee_status ? 'u' : 'w',
626 					es->es_lblk, es->es_len,
627 					ext4_es_pblock(es), ext4_es_status(es));
628 			}
629 			goto out;
630 		}
631 
632 		/*
633 		 * We don't check ee_block == es->es_lblk, etc. because es
634 		 * might be a part of whole extent, vice versa.
635 		 */
636 		if (es->es_lblk < ee_block ||
637 		    ext4_es_pblock(es) != ee_start + es->es_lblk - ee_block) {
638 			pr_warn("ES insert assertion failed for inode: %lu "
639 				"ex_status [%d/%d/%llu/%c] != "
640 				"es_status [%d/%d/%llu/%c]\n", inode->i_ino,
641 				ee_block, ee_len, ee_start,
642 				ee_status ? 'u' : 'w', es->es_lblk, es->es_len,
643 				ext4_es_pblock(es), es_status ? 'u' : 'w');
644 			goto out;
645 		}
646 
647 		if (ee_status ^ es_status) {
648 			pr_warn("ES insert assertion failed for inode: %lu "
649 				"ex_status [%d/%d/%llu/%c] != "
650 				"es_status [%d/%d/%llu/%c]\n", inode->i_ino,
651 				ee_block, ee_len, ee_start,
652 				ee_status ? 'u' : 'w', es->es_lblk, es->es_len,
653 				ext4_es_pblock(es), es_status ? 'u' : 'w');
654 		}
655 	} else {
656 		/*
657 		 * We can't find an extent on disk.  So we need to make sure
658 		 * that we don't want to add an written/unwritten extent.
659 		 */
660 		if (!ext4_es_is_delayed(es) && !ext4_es_is_hole(es)) {
661 			pr_warn("ES insert assertion failed for inode: %lu "
662 				"can't find an extent at block %d but we want "
663 				"to add a written/unwritten extent "
664 				"[%d/%d/%llu/%x]\n", inode->i_ino,
665 				es->es_lblk, es->es_lblk, es->es_len,
666 				ext4_es_pblock(es), ext4_es_status(es));
667 		}
668 	}
669 out:
670 	ext4_free_ext_path(path);
671 }
672 
ext4_es_insert_extent_ind_check(struct inode * inode,struct extent_status * es)673 static void ext4_es_insert_extent_ind_check(struct inode *inode,
674 					    struct extent_status *es)
675 {
676 	struct ext4_map_blocks map;
677 	int retval;
678 
679 	/*
680 	 * Here we call ext4_ind_map_blocks to lookup a block mapping because
681 	 * 'Indirect' structure is defined in indirect.c.  So we couldn't
682 	 * access direct/indirect tree from outside.  It is too dirty to define
683 	 * this function in indirect.c file.
684 	 */
685 
686 	map.m_lblk = es->es_lblk;
687 	map.m_len = es->es_len;
688 
689 	retval = ext4_ind_map_blocks(NULL, inode, &map, 0);
690 	if (retval > 0) {
691 		if (ext4_es_is_delayed(es) || ext4_es_is_hole(es)) {
692 			/*
693 			 * We want to add a delayed/hole extent but this
694 			 * block has been allocated.
695 			 */
696 			pr_warn("ES insert assertion failed for inode: %lu "
697 				"We can find blocks but we want to add a "
698 				"delayed/hole extent [%d/%d/%llu/%x]\n",
699 				inode->i_ino, es->es_lblk, es->es_len,
700 				ext4_es_pblock(es), ext4_es_status(es));
701 			return;
702 		} else if (ext4_es_is_written(es)) {
703 			if (retval != es->es_len) {
704 				pr_warn("ES insert assertion failed for "
705 					"inode: %lu retval %d != es_len %d\n",
706 					inode->i_ino, retval, es->es_len);
707 				return;
708 			}
709 			if (map.m_pblk != ext4_es_pblock(es)) {
710 				pr_warn("ES insert assertion failed for "
711 					"inode: %lu m_pblk %llu != "
712 					"es_pblk %llu\n",
713 					inode->i_ino, map.m_pblk,
714 					ext4_es_pblock(es));
715 				return;
716 			}
717 		} else {
718 			/*
719 			 * We don't need to check unwritten extent because
720 			 * indirect-based file doesn't have it.
721 			 */
722 			BUG();
723 		}
724 	} else if (retval == 0) {
725 		if (ext4_es_is_written(es)) {
726 			pr_warn("ES insert assertion failed for inode: %lu "
727 				"We can't find the block but we want to add "
728 				"a written extent [%d/%d/%llu/%x]\n",
729 				inode->i_ino, es->es_lblk, es->es_len,
730 				ext4_es_pblock(es), ext4_es_status(es));
731 			return;
732 		}
733 	}
734 }
735 
ext4_es_insert_extent_check(struct inode * inode,struct extent_status * es)736 static inline void ext4_es_insert_extent_check(struct inode *inode,
737 					       struct extent_status *es)
738 {
739 	/*
740 	 * We don't need to worry about the race condition because
741 	 * caller takes i_data_sem locking.
742 	 */
743 	BUG_ON(!rwsem_is_locked(&EXT4_I(inode)->i_data_sem));
744 	if (ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
745 		ext4_es_insert_extent_ext_check(inode, es);
746 	else
747 		ext4_es_insert_extent_ind_check(inode, es);
748 }
749 #else
ext4_es_insert_extent_check(struct inode * inode,struct extent_status * es)750 static inline void ext4_es_insert_extent_check(struct inode *inode,
751 					       struct extent_status *es)
752 {
753 }
754 #endif
755 
__es_insert_extent(struct inode * inode,struct extent_status * newes)756 static int __es_insert_extent(struct inode *inode, struct extent_status *newes)
757 {
758 	struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
759 	struct rb_node **p = &tree->root.rb_node;
760 	struct rb_node *parent = NULL;
761 	struct extent_status *es;
762 
763 	while (*p) {
764 		parent = *p;
765 		es = rb_entry(parent, struct extent_status, rb_node);
766 
767 		if (newes->es_lblk < es->es_lblk) {
768 			if (ext4_es_can_be_merged(newes, es)) {
769 				/*
770 				 * Here we can modify es_lblk directly
771 				 * because it isn't overlapped.
772 				 */
773 				es->es_lblk = newes->es_lblk;
774 				es->es_len += newes->es_len;
775 				if (ext4_es_is_written(es) ||
776 				    ext4_es_is_unwritten(es))
777 					ext4_es_store_pblock(es,
778 							     newes->es_pblk);
779 				es = ext4_es_try_to_merge_left(inode, es);
780 				goto out;
781 			}
782 			p = &(*p)->rb_left;
783 		} else if (newes->es_lblk > ext4_es_end(es)) {
784 			if (ext4_es_can_be_merged(es, newes)) {
785 				es->es_len += newes->es_len;
786 				es = ext4_es_try_to_merge_right(inode, es);
787 				goto out;
788 			}
789 			p = &(*p)->rb_right;
790 		} else {
791 			BUG();
792 			return -EINVAL;
793 		}
794 	}
795 
796 	es = ext4_es_alloc_extent(inode, newes->es_lblk, newes->es_len,
797 				  newes->es_pblk);
798 	if (!es)
799 		return -ENOMEM;
800 	rb_link_node(&es->rb_node, parent, p);
801 	rb_insert_color(&es->rb_node, &tree->root);
802 
803 out:
804 	tree->cache_es = es;
805 	return 0;
806 }
807 
808 /*
809  * ext4_es_insert_extent() adds information to an inode's extent
810  * status tree.
811  *
812  * Return 0 on success, error code on failure.
813  */
ext4_es_insert_extent(struct inode * inode,ext4_lblk_t lblk,ext4_lblk_t len,ext4_fsblk_t pblk,unsigned int status)814 int ext4_es_insert_extent(struct inode *inode, ext4_lblk_t lblk,
815 			  ext4_lblk_t len, ext4_fsblk_t pblk,
816 			  unsigned int status)
817 {
818 	struct extent_status newes;
819 	ext4_lblk_t end = lblk + len - 1;
820 	int err = 0;
821 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
822 
823 	if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY)
824 		return 0;
825 
826 	es_debug("add [%u/%u) %llu %x to extent status tree of inode %lu\n",
827 		 lblk, len, pblk, status, inode->i_ino);
828 
829 	if (!len)
830 		return 0;
831 
832 	BUG_ON(end < lblk);
833 
834 	if ((status & EXTENT_STATUS_DELAYED) &&
835 	    (status & EXTENT_STATUS_WRITTEN)) {
836 		ext4_warning(inode->i_sb, "Inserting extent [%u/%u] as "
837 				" delayed and written which can potentially "
838 				" cause data loss.", lblk, len);
839 		WARN_ON(1);
840 	}
841 
842 	newes.es_lblk = lblk;
843 	newes.es_len = len;
844 	ext4_es_store_pblock_status(&newes, pblk, status);
845 	trace_ext4_es_insert_extent(inode, &newes);
846 
847 	ext4_es_insert_extent_check(inode, &newes);
848 
849 	write_lock(&EXT4_I(inode)->i_es_lock);
850 	err = __es_remove_extent(inode, lblk, end, NULL);
851 	if (err != 0)
852 		goto error;
853 retry:
854 	err = __es_insert_extent(inode, &newes);
855 	if (err == -ENOMEM && __es_shrink(EXT4_SB(inode->i_sb),
856 					  128, EXT4_I(inode)))
857 		goto retry;
858 	if (err == -ENOMEM && !ext4_es_is_delayed(&newes))
859 		err = 0;
860 
861 	if (sbi->s_cluster_ratio > 1 && test_opt(inode->i_sb, DELALLOC) &&
862 	    (status & EXTENT_STATUS_WRITTEN ||
863 	     status & EXTENT_STATUS_UNWRITTEN))
864 		__revise_pending(inode, lblk, len);
865 
866 error:
867 	write_unlock(&EXT4_I(inode)->i_es_lock);
868 
869 	ext4_es_print_tree(inode);
870 
871 	return err;
872 }
873 
874 /*
875  * ext4_es_cache_extent() inserts information into the extent status
876  * tree if and only if there isn't information about the range in
877  * question already.
878  */
ext4_es_cache_extent(struct inode * inode,ext4_lblk_t lblk,ext4_lblk_t len,ext4_fsblk_t pblk,unsigned int status)879 void ext4_es_cache_extent(struct inode *inode, ext4_lblk_t lblk,
880 			  ext4_lblk_t len, ext4_fsblk_t pblk,
881 			  unsigned int status)
882 {
883 	struct extent_status *es;
884 	struct extent_status newes;
885 	ext4_lblk_t end = lblk + len - 1;
886 
887 	if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY)
888 		return;
889 
890 	newes.es_lblk = lblk;
891 	newes.es_len = len;
892 	ext4_es_store_pblock_status(&newes, pblk, status);
893 	trace_ext4_es_cache_extent(inode, &newes);
894 
895 	if (!len)
896 		return;
897 
898 	BUG_ON(end < lblk);
899 
900 	write_lock(&EXT4_I(inode)->i_es_lock);
901 
902 	es = __es_tree_search(&EXT4_I(inode)->i_es_tree.root, lblk);
903 	if (!es || es->es_lblk > end)
904 		__es_insert_extent(inode, &newes);
905 	write_unlock(&EXT4_I(inode)->i_es_lock);
906 }
907 
908 /*
909  * ext4_es_lookup_extent() looks up an extent in extent status tree.
910  *
911  * ext4_es_lookup_extent is called by ext4_map_blocks/ext4_da_map_blocks.
912  *
913  * Return: 1 on found, 0 on not
914  */
ext4_es_lookup_extent(struct inode * inode,ext4_lblk_t lblk,ext4_lblk_t * next_lblk,struct extent_status * es)915 int ext4_es_lookup_extent(struct inode *inode, ext4_lblk_t lblk,
916 			  ext4_lblk_t *next_lblk,
917 			  struct extent_status *es)
918 {
919 	struct ext4_es_tree *tree;
920 	struct ext4_es_stats *stats;
921 	struct extent_status *es1 = NULL;
922 	struct rb_node *node;
923 	int found = 0;
924 
925 	if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY)
926 		return 0;
927 
928 	trace_ext4_es_lookup_extent_enter(inode, lblk);
929 	es_debug("lookup extent in block %u\n", lblk);
930 
931 	tree = &EXT4_I(inode)->i_es_tree;
932 	read_lock(&EXT4_I(inode)->i_es_lock);
933 
934 	/* find extent in cache firstly */
935 	es->es_lblk = es->es_len = es->es_pblk = 0;
936 	if (tree->cache_es) {
937 		es1 = tree->cache_es;
938 		if (in_range(lblk, es1->es_lblk, es1->es_len)) {
939 			es_debug("%u cached by [%u/%u)\n",
940 				 lblk, es1->es_lblk, es1->es_len);
941 			found = 1;
942 			goto out;
943 		}
944 	}
945 
946 	node = tree->root.rb_node;
947 	while (node) {
948 		es1 = rb_entry(node, struct extent_status, rb_node);
949 		if (lblk < es1->es_lblk)
950 			node = node->rb_left;
951 		else if (lblk > ext4_es_end(es1))
952 			node = node->rb_right;
953 		else {
954 			found = 1;
955 			break;
956 		}
957 	}
958 
959 out:
960 	stats = &EXT4_SB(inode->i_sb)->s_es_stats;
961 	if (found) {
962 		BUG_ON(!es1);
963 		es->es_lblk = es1->es_lblk;
964 		es->es_len = es1->es_len;
965 		es->es_pblk = es1->es_pblk;
966 		if (!ext4_es_is_referenced(es1))
967 			ext4_es_set_referenced(es1);
968 		percpu_counter_inc(&stats->es_stats_cache_hits);
969 		if (next_lblk) {
970 			node = rb_next(&es1->rb_node);
971 			if (node) {
972 				es1 = rb_entry(node, struct extent_status,
973 					       rb_node);
974 				*next_lblk = es1->es_lblk;
975 			} else
976 				*next_lblk = 0;
977 		}
978 	} else {
979 		percpu_counter_inc(&stats->es_stats_cache_misses);
980 	}
981 
982 	read_unlock(&EXT4_I(inode)->i_es_lock);
983 
984 	trace_ext4_es_lookup_extent_exit(inode, es, found);
985 	return found;
986 }
987 
988 struct rsvd_count {
989 	int ndelonly;
990 	bool first_do_lblk_found;
991 	ext4_lblk_t first_do_lblk;
992 	ext4_lblk_t last_do_lblk;
993 	struct extent_status *left_es;
994 	bool partial;
995 	ext4_lblk_t lclu;
996 };
997 
998 /*
999  * init_rsvd - initialize reserved count data before removing block range
1000  *	       in file from extent status tree
1001  *
1002  * @inode - file containing range
1003  * @lblk - first block in range
1004  * @es - pointer to first extent in range
1005  * @rc - pointer to reserved count data
1006  *
1007  * Assumes es is not NULL
1008  */
init_rsvd(struct inode * inode,ext4_lblk_t lblk,struct extent_status * es,struct rsvd_count * rc)1009 static void init_rsvd(struct inode *inode, ext4_lblk_t lblk,
1010 		      struct extent_status *es, struct rsvd_count *rc)
1011 {
1012 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
1013 	struct rb_node *node;
1014 
1015 	rc->ndelonly = 0;
1016 
1017 	/*
1018 	 * for bigalloc, note the first delonly block in the range has not
1019 	 * been found, record the extent containing the block to the left of
1020 	 * the region to be removed, if any, and note that there's no partial
1021 	 * cluster to track
1022 	 */
1023 	if (sbi->s_cluster_ratio > 1) {
1024 		rc->first_do_lblk_found = false;
1025 		if (lblk > es->es_lblk) {
1026 			rc->left_es = es;
1027 		} else {
1028 			node = rb_prev(&es->rb_node);
1029 			rc->left_es = node ? rb_entry(node,
1030 						      struct extent_status,
1031 						      rb_node) : NULL;
1032 		}
1033 		rc->partial = false;
1034 	}
1035 }
1036 
1037 /*
1038  * count_rsvd - count the clusters containing delayed and not unwritten
1039  *		(delonly) blocks in a range within an extent and add to
1040  *	        the running tally in rsvd_count
1041  *
1042  * @inode - file containing extent
1043  * @lblk - first block in range
1044  * @len - length of range in blocks
1045  * @es - pointer to extent containing clusters to be counted
1046  * @rc - pointer to reserved count data
1047  *
1048  * Tracks partial clusters found at the beginning and end of extents so
1049  * they aren't overcounted when they span adjacent extents
1050  */
count_rsvd(struct inode * inode,ext4_lblk_t lblk,long len,struct extent_status * es,struct rsvd_count * rc)1051 static void count_rsvd(struct inode *inode, ext4_lblk_t lblk, long len,
1052 		       struct extent_status *es, struct rsvd_count *rc)
1053 {
1054 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
1055 	ext4_lblk_t i, end, nclu;
1056 
1057 	if (!ext4_es_is_delonly(es))
1058 		return;
1059 
1060 	WARN_ON(len <= 0);
1061 
1062 	if (sbi->s_cluster_ratio == 1) {
1063 		rc->ndelonly += (int) len;
1064 		return;
1065 	}
1066 
1067 	/* bigalloc */
1068 
1069 	i = (lblk < es->es_lblk) ? es->es_lblk : lblk;
1070 	end = lblk + (ext4_lblk_t) len - 1;
1071 	end = (end > ext4_es_end(es)) ? ext4_es_end(es) : end;
1072 
1073 	/* record the first block of the first delonly extent seen */
1074 	if (!rc->first_do_lblk_found) {
1075 		rc->first_do_lblk = i;
1076 		rc->first_do_lblk_found = true;
1077 	}
1078 
1079 	/* update the last lblk in the region seen so far */
1080 	rc->last_do_lblk = end;
1081 
1082 	/*
1083 	 * if we're tracking a partial cluster and the current extent
1084 	 * doesn't start with it, count it and stop tracking
1085 	 */
1086 	if (rc->partial && (rc->lclu != EXT4_B2C(sbi, i))) {
1087 		rc->ndelonly++;
1088 		rc->partial = false;
1089 	}
1090 
1091 	/*
1092 	 * if the first cluster doesn't start on a cluster boundary but
1093 	 * ends on one, count it
1094 	 */
1095 	if (EXT4_LBLK_COFF(sbi, i) != 0) {
1096 		if (end >= EXT4_LBLK_CFILL(sbi, i)) {
1097 			rc->ndelonly++;
1098 			rc->partial = false;
1099 			i = EXT4_LBLK_CFILL(sbi, i) + 1;
1100 		}
1101 	}
1102 
1103 	/*
1104 	 * if the current cluster starts on a cluster boundary, count the
1105 	 * number of whole delonly clusters in the extent
1106 	 */
1107 	if ((i + sbi->s_cluster_ratio - 1) <= end) {
1108 		nclu = (end - i + 1) >> sbi->s_cluster_bits;
1109 		rc->ndelonly += nclu;
1110 		i += nclu << sbi->s_cluster_bits;
1111 	}
1112 
1113 	/*
1114 	 * start tracking a partial cluster if there's a partial at the end
1115 	 * of the current extent and we're not already tracking one
1116 	 */
1117 	if (!rc->partial && i <= end) {
1118 		rc->partial = true;
1119 		rc->lclu = EXT4_B2C(sbi, i);
1120 	}
1121 }
1122 
1123 /*
1124  * __pr_tree_search - search for a pending cluster reservation
1125  *
1126  * @root - root of pending reservation tree
1127  * @lclu - logical cluster to search for
1128  *
1129  * Returns the pending reservation for the cluster identified by @lclu
1130  * if found.  If not, returns a reservation for the next cluster if any,
1131  * and if not, returns NULL.
1132  */
__pr_tree_search(struct rb_root * root,ext4_lblk_t lclu)1133 static struct pending_reservation *__pr_tree_search(struct rb_root *root,
1134 						    ext4_lblk_t lclu)
1135 {
1136 	struct rb_node *node = root->rb_node;
1137 	struct pending_reservation *pr = NULL;
1138 
1139 	while (node) {
1140 		pr = rb_entry(node, struct pending_reservation, rb_node);
1141 		if (lclu < pr->lclu)
1142 			node = node->rb_left;
1143 		else if (lclu > pr->lclu)
1144 			node = node->rb_right;
1145 		else
1146 			return pr;
1147 	}
1148 	if (pr && lclu < pr->lclu)
1149 		return pr;
1150 	if (pr && lclu > pr->lclu) {
1151 		node = rb_next(&pr->rb_node);
1152 		return node ? rb_entry(node, struct pending_reservation,
1153 				       rb_node) : NULL;
1154 	}
1155 	return NULL;
1156 }
1157 
1158 /*
1159  * get_rsvd - calculates and returns the number of cluster reservations to be
1160  *	      released when removing a block range from the extent status tree
1161  *	      and releases any pending reservations within the range
1162  *
1163  * @inode - file containing block range
1164  * @end - last block in range
1165  * @right_es - pointer to extent containing next block beyond end or NULL
1166  * @rc - pointer to reserved count data
1167  *
1168  * The number of reservations to be released is equal to the number of
1169  * clusters containing delayed and not unwritten (delonly) blocks within
1170  * the range, minus the number of clusters still containing delonly blocks
1171  * at the ends of the range, and minus the number of pending reservations
1172  * within the range.
1173  */
get_rsvd(struct inode * inode,ext4_lblk_t end,struct extent_status * right_es,struct rsvd_count * rc)1174 static unsigned int get_rsvd(struct inode *inode, ext4_lblk_t end,
1175 			     struct extent_status *right_es,
1176 			     struct rsvd_count *rc)
1177 {
1178 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
1179 	struct pending_reservation *pr;
1180 	struct ext4_pending_tree *tree = &EXT4_I(inode)->i_pending_tree;
1181 	struct rb_node *node;
1182 	ext4_lblk_t first_lclu, last_lclu;
1183 	bool left_delonly, right_delonly, count_pending;
1184 	struct extent_status *es;
1185 
1186 	if (sbi->s_cluster_ratio > 1) {
1187 		/* count any remaining partial cluster */
1188 		if (rc->partial)
1189 			rc->ndelonly++;
1190 
1191 		if (rc->ndelonly == 0)
1192 			return 0;
1193 
1194 		first_lclu = EXT4_B2C(sbi, rc->first_do_lblk);
1195 		last_lclu = EXT4_B2C(sbi, rc->last_do_lblk);
1196 
1197 		/*
1198 		 * decrease the delonly count by the number of clusters at the
1199 		 * ends of the range that still contain delonly blocks -
1200 		 * these clusters still need to be reserved
1201 		 */
1202 		left_delonly = right_delonly = false;
1203 
1204 		es = rc->left_es;
1205 		while (es && ext4_es_end(es) >=
1206 		       EXT4_LBLK_CMASK(sbi, rc->first_do_lblk)) {
1207 			if (ext4_es_is_delonly(es)) {
1208 				rc->ndelonly--;
1209 				left_delonly = true;
1210 				break;
1211 			}
1212 			node = rb_prev(&es->rb_node);
1213 			if (!node)
1214 				break;
1215 			es = rb_entry(node, struct extent_status, rb_node);
1216 		}
1217 		if (right_es && (!left_delonly || first_lclu != last_lclu)) {
1218 			if (end < ext4_es_end(right_es)) {
1219 				es = right_es;
1220 			} else {
1221 				node = rb_next(&right_es->rb_node);
1222 				es = node ? rb_entry(node, struct extent_status,
1223 						     rb_node) : NULL;
1224 			}
1225 			while (es && es->es_lblk <=
1226 			       EXT4_LBLK_CFILL(sbi, rc->last_do_lblk)) {
1227 				if (ext4_es_is_delonly(es)) {
1228 					rc->ndelonly--;
1229 					right_delonly = true;
1230 					break;
1231 				}
1232 				node = rb_next(&es->rb_node);
1233 				if (!node)
1234 					break;
1235 				es = rb_entry(node, struct extent_status,
1236 					      rb_node);
1237 			}
1238 		}
1239 
1240 		/*
1241 		 * Determine the block range that should be searched for
1242 		 * pending reservations, if any.  Clusters on the ends of the
1243 		 * original removed range containing delonly blocks are
1244 		 * excluded.  They've already been accounted for and it's not
1245 		 * possible to determine if an associated pending reservation
1246 		 * should be released with the information available in the
1247 		 * extents status tree.
1248 		 */
1249 		if (first_lclu == last_lclu) {
1250 			if (left_delonly | right_delonly)
1251 				count_pending = false;
1252 			else
1253 				count_pending = true;
1254 		} else {
1255 			if (left_delonly)
1256 				first_lclu++;
1257 			if (right_delonly)
1258 				last_lclu--;
1259 			if (first_lclu <= last_lclu)
1260 				count_pending = true;
1261 			else
1262 				count_pending = false;
1263 		}
1264 
1265 		/*
1266 		 * a pending reservation found between first_lclu and last_lclu
1267 		 * represents an allocated cluster that contained at least one
1268 		 * delonly block, so the delonly total must be reduced by one
1269 		 * for each pending reservation found and released
1270 		 */
1271 		if (count_pending) {
1272 			pr = __pr_tree_search(&tree->root, first_lclu);
1273 			while (pr && pr->lclu <= last_lclu) {
1274 				rc->ndelonly--;
1275 				node = rb_next(&pr->rb_node);
1276 				rb_erase(&pr->rb_node, &tree->root);
1277 				kmem_cache_free(ext4_pending_cachep, pr);
1278 				if (!node)
1279 					break;
1280 				pr = rb_entry(node, struct pending_reservation,
1281 					      rb_node);
1282 			}
1283 		}
1284 	}
1285 	return rc->ndelonly;
1286 }
1287 
1288 
1289 /*
1290  * __es_remove_extent - removes block range from extent status tree
1291  *
1292  * @inode - file containing range
1293  * @lblk - first block in range
1294  * @end - last block in range
1295  * @reserved - number of cluster reservations released
1296  *
1297  * If @reserved is not NULL and delayed allocation is enabled, counts
1298  * block/cluster reservations freed by removing range and if bigalloc
1299  * enabled cancels pending reservations as needed. Returns 0 on success,
1300  * error code on failure.
1301  */
__es_remove_extent(struct inode * inode,ext4_lblk_t lblk,ext4_lblk_t end,int * reserved)1302 static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
1303 			      ext4_lblk_t end, int *reserved)
1304 {
1305 	struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
1306 	struct rb_node *node;
1307 	struct extent_status *es;
1308 	struct extent_status orig_es;
1309 	ext4_lblk_t len1, len2;
1310 	ext4_fsblk_t block;
1311 	int err;
1312 	bool count_reserved = true;
1313 	struct rsvd_count rc;
1314 
1315 	if (reserved == NULL || !test_opt(inode->i_sb, DELALLOC))
1316 		count_reserved = false;
1317 retry:
1318 	err = 0;
1319 
1320 	es = __es_tree_search(&tree->root, lblk);
1321 	if (!es)
1322 		goto out;
1323 	if (es->es_lblk > end)
1324 		goto out;
1325 
1326 	/* Simply invalidate cache_es. */
1327 	tree->cache_es = NULL;
1328 	if (count_reserved)
1329 		init_rsvd(inode, lblk, es, &rc);
1330 
1331 	orig_es.es_lblk = es->es_lblk;
1332 	orig_es.es_len = es->es_len;
1333 	orig_es.es_pblk = es->es_pblk;
1334 
1335 	len1 = lblk > es->es_lblk ? lblk - es->es_lblk : 0;
1336 	len2 = ext4_es_end(es) > end ? ext4_es_end(es) - end : 0;
1337 	if (len1 > 0)
1338 		es->es_len = len1;
1339 	if (len2 > 0) {
1340 		if (len1 > 0) {
1341 			struct extent_status newes;
1342 
1343 			newes.es_lblk = end + 1;
1344 			newes.es_len = len2;
1345 			block = 0x7FDEADBEEFULL;
1346 			if (ext4_es_is_written(&orig_es) ||
1347 			    ext4_es_is_unwritten(&orig_es))
1348 				block = ext4_es_pblock(&orig_es) +
1349 					orig_es.es_len - len2;
1350 			ext4_es_store_pblock_status(&newes, block,
1351 						    ext4_es_status(&orig_es));
1352 			err = __es_insert_extent(inode, &newes);
1353 			if (err) {
1354 				es->es_lblk = orig_es.es_lblk;
1355 				es->es_len = orig_es.es_len;
1356 				if ((err == -ENOMEM) &&
1357 				    __es_shrink(EXT4_SB(inode->i_sb),
1358 							128, EXT4_I(inode)))
1359 					goto retry;
1360 				goto out;
1361 			}
1362 		} else {
1363 			es->es_lblk = end + 1;
1364 			es->es_len = len2;
1365 			if (ext4_es_is_written(es) ||
1366 			    ext4_es_is_unwritten(es)) {
1367 				block = orig_es.es_pblk + orig_es.es_len - len2;
1368 				ext4_es_store_pblock(es, block);
1369 			}
1370 		}
1371 		if (count_reserved)
1372 			count_rsvd(inode, lblk, orig_es.es_len - len1 - len2,
1373 				   &orig_es, &rc);
1374 		goto out_get_reserved;
1375 	}
1376 
1377 	if (len1 > 0) {
1378 		if (count_reserved)
1379 			count_rsvd(inode, lblk, orig_es.es_len - len1,
1380 				   &orig_es, &rc);
1381 		node = rb_next(&es->rb_node);
1382 		if (node)
1383 			es = rb_entry(node, struct extent_status, rb_node);
1384 		else
1385 			es = NULL;
1386 	}
1387 
1388 	while (es && ext4_es_end(es) <= end) {
1389 		if (count_reserved)
1390 			count_rsvd(inode, es->es_lblk, es->es_len, es, &rc);
1391 		node = rb_next(&es->rb_node);
1392 		rb_erase(&es->rb_node, &tree->root);
1393 		ext4_es_free_extent(inode, es);
1394 		if (!node) {
1395 			es = NULL;
1396 			break;
1397 		}
1398 		es = rb_entry(node, struct extent_status, rb_node);
1399 	}
1400 
1401 	if (es && es->es_lblk < end + 1) {
1402 		ext4_lblk_t orig_len = es->es_len;
1403 
1404 		len1 = ext4_es_end(es) - end;
1405 		if (count_reserved)
1406 			count_rsvd(inode, es->es_lblk, orig_len - len1,
1407 				   es, &rc);
1408 		es->es_lblk = end + 1;
1409 		es->es_len = len1;
1410 		if (ext4_es_is_written(es) || ext4_es_is_unwritten(es)) {
1411 			block = es->es_pblk + orig_len - len1;
1412 			ext4_es_store_pblock(es, block);
1413 		}
1414 	}
1415 
1416 out_get_reserved:
1417 	if (count_reserved)
1418 		*reserved = get_rsvd(inode, end, es, &rc);
1419 out:
1420 	return err;
1421 }
1422 
1423 /*
1424  * ext4_es_remove_extent - removes block range from extent status tree
1425  *
1426  * @inode - file containing range
1427  * @lblk - first block in range
1428  * @len - number of blocks to remove
1429  *
1430  * Reduces block/cluster reservation count and for bigalloc cancels pending
1431  * reservations as needed. Returns 0 on success, error code on failure.
1432  */
ext4_es_remove_extent(struct inode * inode,ext4_lblk_t lblk,ext4_lblk_t len)1433 int ext4_es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
1434 			  ext4_lblk_t len)
1435 {
1436 	ext4_lblk_t end;
1437 	int err = 0;
1438 	int reserved = 0;
1439 
1440 	if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY)
1441 		return 0;
1442 
1443 	trace_ext4_es_remove_extent(inode, lblk, len);
1444 	es_debug("remove [%u/%u) from extent status tree of inode %lu\n",
1445 		 lblk, len, inode->i_ino);
1446 
1447 	if (!len)
1448 		return err;
1449 
1450 	end = lblk + len - 1;
1451 	BUG_ON(end < lblk);
1452 
1453 	/*
1454 	 * ext4_clear_inode() depends on us taking i_es_lock unconditionally
1455 	 * so that we are sure __es_shrink() is done with the inode before it
1456 	 * is reclaimed.
1457 	 */
1458 	write_lock(&EXT4_I(inode)->i_es_lock);
1459 	err = __es_remove_extent(inode, lblk, end, &reserved);
1460 	write_unlock(&EXT4_I(inode)->i_es_lock);
1461 	ext4_es_print_tree(inode);
1462 	ext4_da_release_space(inode, reserved);
1463 	return err;
1464 }
1465 
__es_shrink(struct ext4_sb_info * sbi,int nr_to_scan,struct ext4_inode_info * locked_ei)1466 static int __es_shrink(struct ext4_sb_info *sbi, int nr_to_scan,
1467 		       struct ext4_inode_info *locked_ei)
1468 {
1469 	struct ext4_inode_info *ei;
1470 	struct ext4_es_stats *es_stats;
1471 	ktime_t start_time;
1472 	u64 scan_time;
1473 	int nr_to_walk;
1474 	int nr_shrunk = 0;
1475 	int retried = 0, nr_skipped = 0;
1476 
1477 	es_stats = &sbi->s_es_stats;
1478 	start_time = ktime_get();
1479 
1480 retry:
1481 	spin_lock(&sbi->s_es_lock);
1482 	nr_to_walk = sbi->s_es_nr_inode;
1483 	while (nr_to_walk-- > 0) {
1484 		if (list_empty(&sbi->s_es_list)) {
1485 			spin_unlock(&sbi->s_es_lock);
1486 			goto out;
1487 		}
1488 		ei = list_first_entry(&sbi->s_es_list, struct ext4_inode_info,
1489 				      i_es_list);
1490 		/* Move the inode to the tail */
1491 		list_move_tail(&ei->i_es_list, &sbi->s_es_list);
1492 
1493 		/*
1494 		 * Normally we try hard to avoid shrinking precached inodes,
1495 		 * but we will as a last resort.
1496 		 */
1497 		if (!retried && ext4_test_inode_state(&ei->vfs_inode,
1498 						EXT4_STATE_EXT_PRECACHED)) {
1499 			nr_skipped++;
1500 			continue;
1501 		}
1502 
1503 		if (ei == locked_ei || !write_trylock(&ei->i_es_lock)) {
1504 			nr_skipped++;
1505 			continue;
1506 		}
1507 		/*
1508 		 * Now we hold i_es_lock which protects us from inode reclaim
1509 		 * freeing inode under us
1510 		 */
1511 		spin_unlock(&sbi->s_es_lock);
1512 
1513 		nr_shrunk += es_reclaim_extents(ei, &nr_to_scan);
1514 		write_unlock(&ei->i_es_lock);
1515 
1516 		if (nr_to_scan <= 0)
1517 			goto out;
1518 		spin_lock(&sbi->s_es_lock);
1519 	}
1520 	spin_unlock(&sbi->s_es_lock);
1521 
1522 	/*
1523 	 * If we skipped any inodes, and we weren't able to make any
1524 	 * forward progress, try again to scan precached inodes.
1525 	 */
1526 	if ((nr_shrunk == 0) && nr_skipped && !retried) {
1527 		retried++;
1528 		goto retry;
1529 	}
1530 
1531 	if (locked_ei && nr_shrunk == 0)
1532 		nr_shrunk = es_reclaim_extents(locked_ei, &nr_to_scan);
1533 
1534 out:
1535 	scan_time = ktime_to_ns(ktime_sub(ktime_get(), start_time));
1536 	if (likely(es_stats->es_stats_scan_time))
1537 		es_stats->es_stats_scan_time = (scan_time +
1538 				es_stats->es_stats_scan_time*3) / 4;
1539 	else
1540 		es_stats->es_stats_scan_time = scan_time;
1541 	if (scan_time > es_stats->es_stats_max_scan_time)
1542 		es_stats->es_stats_max_scan_time = scan_time;
1543 	if (likely(es_stats->es_stats_shrunk))
1544 		es_stats->es_stats_shrunk = (nr_shrunk +
1545 				es_stats->es_stats_shrunk*3) / 4;
1546 	else
1547 		es_stats->es_stats_shrunk = nr_shrunk;
1548 
1549 	trace_ext4_es_shrink(sbi->s_sb, nr_shrunk, scan_time,
1550 			     nr_skipped, retried);
1551 	return nr_shrunk;
1552 }
1553 
ext4_es_count(struct shrinker * shrink,struct shrink_control * sc)1554 static unsigned long ext4_es_count(struct shrinker *shrink,
1555 				   struct shrink_control *sc)
1556 {
1557 	unsigned long nr;
1558 	struct ext4_sb_info *sbi;
1559 
1560 	sbi = container_of(shrink, struct ext4_sb_info, s_es_shrinker);
1561 	nr = percpu_counter_read_positive(&sbi->s_es_stats.es_stats_shk_cnt);
1562 	trace_ext4_es_shrink_count(sbi->s_sb, sc->nr_to_scan, nr);
1563 	return nr;
1564 }
1565 
ext4_es_scan(struct shrinker * shrink,struct shrink_control * sc)1566 static unsigned long ext4_es_scan(struct shrinker *shrink,
1567 				  struct shrink_control *sc)
1568 {
1569 	struct ext4_sb_info *sbi = container_of(shrink,
1570 					struct ext4_sb_info, s_es_shrinker);
1571 	int nr_to_scan = sc->nr_to_scan;
1572 	int ret, nr_shrunk;
1573 
1574 	ret = percpu_counter_read_positive(&sbi->s_es_stats.es_stats_shk_cnt);
1575 	trace_ext4_es_shrink_scan_enter(sbi->s_sb, nr_to_scan, ret);
1576 
1577 	nr_shrunk = __es_shrink(sbi, nr_to_scan, NULL);
1578 
1579 	ret = percpu_counter_read_positive(&sbi->s_es_stats.es_stats_shk_cnt);
1580 	trace_ext4_es_shrink_scan_exit(sbi->s_sb, nr_shrunk, ret);
1581 	return nr_shrunk;
1582 }
1583 
ext4_seq_es_shrinker_info_show(struct seq_file * seq,void * v)1584 int ext4_seq_es_shrinker_info_show(struct seq_file *seq, void *v)
1585 {
1586 	struct ext4_sb_info *sbi = EXT4_SB((struct super_block *) seq->private);
1587 	struct ext4_es_stats *es_stats = &sbi->s_es_stats;
1588 	struct ext4_inode_info *ei, *max = NULL;
1589 	unsigned int inode_cnt = 0;
1590 
1591 	if (v != SEQ_START_TOKEN)
1592 		return 0;
1593 
1594 	/* here we just find an inode that has the max nr. of objects */
1595 	spin_lock(&sbi->s_es_lock);
1596 	list_for_each_entry(ei, &sbi->s_es_list, i_es_list) {
1597 		inode_cnt++;
1598 		if (max && max->i_es_all_nr < ei->i_es_all_nr)
1599 			max = ei;
1600 		else if (!max)
1601 			max = ei;
1602 	}
1603 	spin_unlock(&sbi->s_es_lock);
1604 
1605 	seq_printf(seq, "stats:\n  %lld objects\n  %lld reclaimable objects\n",
1606 		   percpu_counter_sum_positive(&es_stats->es_stats_all_cnt),
1607 		   percpu_counter_sum_positive(&es_stats->es_stats_shk_cnt));
1608 	seq_printf(seq, "  %lld/%lld cache hits/misses\n",
1609 		   percpu_counter_sum_positive(&es_stats->es_stats_cache_hits),
1610 		   percpu_counter_sum_positive(&es_stats->es_stats_cache_misses));
1611 	if (inode_cnt)
1612 		seq_printf(seq, "  %d inodes on list\n", inode_cnt);
1613 
1614 	seq_printf(seq, "average:\n  %llu us scan time\n",
1615 	    div_u64(es_stats->es_stats_scan_time, 1000));
1616 	seq_printf(seq, "  %lu shrunk objects\n", es_stats->es_stats_shrunk);
1617 	if (inode_cnt)
1618 		seq_printf(seq,
1619 		    "maximum:\n  %lu inode (%u objects, %u reclaimable)\n"
1620 		    "  %llu us max scan time\n",
1621 		    max->vfs_inode.i_ino, max->i_es_all_nr, max->i_es_shk_nr,
1622 		    div_u64(es_stats->es_stats_max_scan_time, 1000));
1623 
1624 	return 0;
1625 }
1626 
ext4_es_register_shrinker(struct ext4_sb_info * sbi)1627 int ext4_es_register_shrinker(struct ext4_sb_info *sbi)
1628 {
1629 	int err;
1630 
1631 	/* Make sure we have enough bits for physical block number */
1632 	BUILD_BUG_ON(ES_SHIFT < 48);
1633 	INIT_LIST_HEAD(&sbi->s_es_list);
1634 	sbi->s_es_nr_inode = 0;
1635 	spin_lock_init(&sbi->s_es_lock);
1636 	sbi->s_es_stats.es_stats_shrunk = 0;
1637 	err = percpu_counter_init(&sbi->s_es_stats.es_stats_cache_hits, 0,
1638 				  GFP_KERNEL);
1639 	if (err)
1640 		return err;
1641 	err = percpu_counter_init(&sbi->s_es_stats.es_stats_cache_misses, 0,
1642 				  GFP_KERNEL);
1643 	if (err)
1644 		goto err1;
1645 	sbi->s_es_stats.es_stats_scan_time = 0;
1646 	sbi->s_es_stats.es_stats_max_scan_time = 0;
1647 	err = percpu_counter_init(&sbi->s_es_stats.es_stats_all_cnt, 0, GFP_KERNEL);
1648 	if (err)
1649 		goto err2;
1650 	err = percpu_counter_init(&sbi->s_es_stats.es_stats_shk_cnt, 0, GFP_KERNEL);
1651 	if (err)
1652 		goto err3;
1653 
1654 	sbi->s_es_shrinker.scan_objects = ext4_es_scan;
1655 	sbi->s_es_shrinker.count_objects = ext4_es_count;
1656 	sbi->s_es_shrinker.seeks = DEFAULT_SEEKS;
1657 	err = register_shrinker(&sbi->s_es_shrinker, "ext4-es:%s",
1658 				sbi->s_sb->s_id);
1659 	if (err)
1660 		goto err4;
1661 
1662 	return 0;
1663 err4:
1664 	percpu_counter_destroy(&sbi->s_es_stats.es_stats_shk_cnt);
1665 err3:
1666 	percpu_counter_destroy(&sbi->s_es_stats.es_stats_all_cnt);
1667 err2:
1668 	percpu_counter_destroy(&sbi->s_es_stats.es_stats_cache_misses);
1669 err1:
1670 	percpu_counter_destroy(&sbi->s_es_stats.es_stats_cache_hits);
1671 	return err;
1672 }
1673 
ext4_es_unregister_shrinker(struct ext4_sb_info * sbi)1674 void ext4_es_unregister_shrinker(struct ext4_sb_info *sbi)
1675 {
1676 	percpu_counter_destroy(&sbi->s_es_stats.es_stats_cache_hits);
1677 	percpu_counter_destroy(&sbi->s_es_stats.es_stats_cache_misses);
1678 	percpu_counter_destroy(&sbi->s_es_stats.es_stats_all_cnt);
1679 	percpu_counter_destroy(&sbi->s_es_stats.es_stats_shk_cnt);
1680 	unregister_shrinker(&sbi->s_es_shrinker);
1681 }
1682 
1683 /*
1684  * Shrink extents in given inode from ei->i_es_shrink_lblk till end. Scan at
1685  * most *nr_to_scan extents, update *nr_to_scan accordingly.
1686  *
1687  * Return 0 if we hit end of tree / interval, 1 if we exhausted nr_to_scan.
1688  * Increment *nr_shrunk by the number of reclaimed extents. Also update
1689  * ei->i_es_shrink_lblk to where we should continue scanning.
1690  */
es_do_reclaim_extents(struct ext4_inode_info * ei,ext4_lblk_t end,int * nr_to_scan,int * nr_shrunk)1691 static int es_do_reclaim_extents(struct ext4_inode_info *ei, ext4_lblk_t end,
1692 				 int *nr_to_scan, int *nr_shrunk)
1693 {
1694 	struct inode *inode = &ei->vfs_inode;
1695 	struct ext4_es_tree *tree = &ei->i_es_tree;
1696 	struct extent_status *es;
1697 	struct rb_node *node;
1698 
1699 	es = __es_tree_search(&tree->root, ei->i_es_shrink_lblk);
1700 	if (!es)
1701 		goto out_wrap;
1702 
1703 	while (*nr_to_scan > 0) {
1704 		if (es->es_lblk > end) {
1705 			ei->i_es_shrink_lblk = end + 1;
1706 			return 0;
1707 		}
1708 
1709 		(*nr_to_scan)--;
1710 		node = rb_next(&es->rb_node);
1711 		/*
1712 		 * We can't reclaim delayed extent from status tree because
1713 		 * fiemap, bigallic, and seek_data/hole need to use it.
1714 		 */
1715 		if (ext4_es_is_delayed(es))
1716 			goto next;
1717 		if (ext4_es_is_referenced(es)) {
1718 			ext4_es_clear_referenced(es);
1719 			goto next;
1720 		}
1721 
1722 		rb_erase(&es->rb_node, &tree->root);
1723 		ext4_es_free_extent(inode, es);
1724 		(*nr_shrunk)++;
1725 next:
1726 		if (!node)
1727 			goto out_wrap;
1728 		es = rb_entry(node, struct extent_status, rb_node);
1729 	}
1730 	ei->i_es_shrink_lblk = es->es_lblk;
1731 	return 1;
1732 out_wrap:
1733 	ei->i_es_shrink_lblk = 0;
1734 	return 0;
1735 }
1736 
es_reclaim_extents(struct ext4_inode_info * ei,int * nr_to_scan)1737 static int es_reclaim_extents(struct ext4_inode_info *ei, int *nr_to_scan)
1738 {
1739 	struct inode *inode = &ei->vfs_inode;
1740 	int nr_shrunk = 0;
1741 	ext4_lblk_t start = ei->i_es_shrink_lblk;
1742 	static DEFINE_RATELIMIT_STATE(_rs, DEFAULT_RATELIMIT_INTERVAL,
1743 				      DEFAULT_RATELIMIT_BURST);
1744 
1745 	if (ei->i_es_shk_nr == 0)
1746 		return 0;
1747 
1748 	if (ext4_test_inode_state(inode, EXT4_STATE_EXT_PRECACHED) &&
1749 	    __ratelimit(&_rs))
1750 		ext4_warning(inode->i_sb, "forced shrink of precached extents");
1751 
1752 	if (!es_do_reclaim_extents(ei, EXT_MAX_BLOCKS, nr_to_scan, &nr_shrunk) &&
1753 	    start != 0)
1754 		es_do_reclaim_extents(ei, start - 1, nr_to_scan, &nr_shrunk);
1755 
1756 	ei->i_es_tree.cache_es = NULL;
1757 	return nr_shrunk;
1758 }
1759 
1760 /*
1761  * Called to support EXT4_IOC_CLEAR_ES_CACHE.  We can only remove
1762  * discretionary entries from the extent status cache.  (Some entries
1763  * must be present for proper operations.)
1764  */
ext4_clear_inode_es(struct inode * inode)1765 void ext4_clear_inode_es(struct inode *inode)
1766 {
1767 	struct ext4_inode_info *ei = EXT4_I(inode);
1768 	struct extent_status *es;
1769 	struct ext4_es_tree *tree;
1770 	struct rb_node *node;
1771 
1772 	write_lock(&ei->i_es_lock);
1773 	tree = &EXT4_I(inode)->i_es_tree;
1774 	tree->cache_es = NULL;
1775 	node = rb_first(&tree->root);
1776 	while (node) {
1777 		es = rb_entry(node, struct extent_status, rb_node);
1778 		node = rb_next(node);
1779 		if (!ext4_es_is_delayed(es)) {
1780 			rb_erase(&es->rb_node, &tree->root);
1781 			ext4_es_free_extent(inode, es);
1782 		}
1783 	}
1784 	ext4_clear_inode_state(inode, EXT4_STATE_EXT_PRECACHED);
1785 	write_unlock(&ei->i_es_lock);
1786 }
1787 
1788 #ifdef ES_DEBUG__
ext4_print_pending_tree(struct inode * inode)1789 static void ext4_print_pending_tree(struct inode *inode)
1790 {
1791 	struct ext4_pending_tree *tree;
1792 	struct rb_node *node;
1793 	struct pending_reservation *pr;
1794 
1795 	printk(KERN_DEBUG "pending reservations for inode %lu:", inode->i_ino);
1796 	tree = &EXT4_I(inode)->i_pending_tree;
1797 	node = rb_first(&tree->root);
1798 	while (node) {
1799 		pr = rb_entry(node, struct pending_reservation, rb_node);
1800 		printk(KERN_DEBUG " %u", pr->lclu);
1801 		node = rb_next(node);
1802 	}
1803 	printk(KERN_DEBUG "\n");
1804 }
1805 #else
1806 #define ext4_print_pending_tree(inode)
1807 #endif
1808 
ext4_init_pending(void)1809 int __init ext4_init_pending(void)
1810 {
1811 	ext4_pending_cachep = kmem_cache_create("ext4_pending_reservation",
1812 					   sizeof(struct pending_reservation),
1813 					   0, (SLAB_RECLAIM_ACCOUNT), NULL);
1814 	if (ext4_pending_cachep == NULL)
1815 		return -ENOMEM;
1816 	return 0;
1817 }
1818 
ext4_exit_pending(void)1819 void ext4_exit_pending(void)
1820 {
1821 	kmem_cache_destroy(ext4_pending_cachep);
1822 }
1823 
ext4_init_pending_tree(struct ext4_pending_tree * tree)1824 void ext4_init_pending_tree(struct ext4_pending_tree *tree)
1825 {
1826 	tree->root = RB_ROOT;
1827 }
1828 
1829 /*
1830  * __get_pending - retrieve a pointer to a pending reservation
1831  *
1832  * @inode - file containing the pending cluster reservation
1833  * @lclu - logical cluster of interest
1834  *
1835  * Returns a pointer to a pending reservation if it's a member of
1836  * the set, and NULL if not.  Must be called holding i_es_lock.
1837  */
__get_pending(struct inode * inode,ext4_lblk_t lclu)1838 static struct pending_reservation *__get_pending(struct inode *inode,
1839 						 ext4_lblk_t lclu)
1840 {
1841 	struct ext4_pending_tree *tree;
1842 	struct rb_node *node;
1843 	struct pending_reservation *pr = NULL;
1844 
1845 	tree = &EXT4_I(inode)->i_pending_tree;
1846 	node = (&tree->root)->rb_node;
1847 
1848 	while (node) {
1849 		pr = rb_entry(node, struct pending_reservation, rb_node);
1850 		if (lclu < pr->lclu)
1851 			node = node->rb_left;
1852 		else if (lclu > pr->lclu)
1853 			node = node->rb_right;
1854 		else if (lclu == pr->lclu)
1855 			return pr;
1856 	}
1857 	return NULL;
1858 }
1859 
1860 /*
1861  * __insert_pending - adds a pending cluster reservation to the set of
1862  *                    pending reservations
1863  *
1864  * @inode - file containing the cluster
1865  * @lblk - logical block in the cluster to be added
1866  *
1867  * Returns 0 on successful insertion and -ENOMEM on failure.  If the
1868  * pending reservation is already in the set, returns successfully.
1869  */
__insert_pending(struct inode * inode,ext4_lblk_t lblk)1870 static int __insert_pending(struct inode *inode, ext4_lblk_t lblk)
1871 {
1872 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
1873 	struct ext4_pending_tree *tree = &EXT4_I(inode)->i_pending_tree;
1874 	struct rb_node **p = &tree->root.rb_node;
1875 	struct rb_node *parent = NULL;
1876 	struct pending_reservation *pr;
1877 	ext4_lblk_t lclu;
1878 	int ret = 0;
1879 
1880 	lclu = EXT4_B2C(sbi, lblk);
1881 	/* search to find parent for insertion */
1882 	while (*p) {
1883 		parent = *p;
1884 		pr = rb_entry(parent, struct pending_reservation, rb_node);
1885 
1886 		if (lclu < pr->lclu) {
1887 			p = &(*p)->rb_left;
1888 		} else if (lclu > pr->lclu) {
1889 			p = &(*p)->rb_right;
1890 		} else {
1891 			/* pending reservation already inserted */
1892 			goto out;
1893 		}
1894 	}
1895 
1896 	pr = kmem_cache_alloc(ext4_pending_cachep, GFP_ATOMIC);
1897 	if (pr == NULL) {
1898 		ret = -ENOMEM;
1899 		goto out;
1900 	}
1901 	pr->lclu = lclu;
1902 
1903 	rb_link_node(&pr->rb_node, parent, p);
1904 	rb_insert_color(&pr->rb_node, &tree->root);
1905 
1906 out:
1907 	return ret;
1908 }
1909 
1910 /*
1911  * __remove_pending - removes a pending cluster reservation from the set
1912  *                    of pending reservations
1913  *
1914  * @inode - file containing the cluster
1915  * @lblk - logical block in the pending cluster reservation to be removed
1916  *
1917  * Returns successfully if pending reservation is not a member of the set.
1918  */
__remove_pending(struct inode * inode,ext4_lblk_t lblk)1919 static void __remove_pending(struct inode *inode, ext4_lblk_t lblk)
1920 {
1921 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
1922 	struct pending_reservation *pr;
1923 	struct ext4_pending_tree *tree;
1924 
1925 	pr = __get_pending(inode, EXT4_B2C(sbi, lblk));
1926 	if (pr != NULL) {
1927 		tree = &EXT4_I(inode)->i_pending_tree;
1928 		rb_erase(&pr->rb_node, &tree->root);
1929 		kmem_cache_free(ext4_pending_cachep, pr);
1930 	}
1931 }
1932 
1933 /*
1934  * ext4_remove_pending - removes a pending cluster reservation from the set
1935  *                       of pending reservations
1936  *
1937  * @inode - file containing the cluster
1938  * @lblk - logical block in the pending cluster reservation to be removed
1939  *
1940  * Locking for external use of __remove_pending.
1941  */
ext4_remove_pending(struct inode * inode,ext4_lblk_t lblk)1942 void ext4_remove_pending(struct inode *inode, ext4_lblk_t lblk)
1943 {
1944 	struct ext4_inode_info *ei = EXT4_I(inode);
1945 
1946 	write_lock(&ei->i_es_lock);
1947 	__remove_pending(inode, lblk);
1948 	write_unlock(&ei->i_es_lock);
1949 }
1950 
1951 /*
1952  * ext4_is_pending - determine whether a cluster has a pending reservation
1953  *                   on it
1954  *
1955  * @inode - file containing the cluster
1956  * @lblk - logical block in the cluster
1957  *
1958  * Returns true if there's a pending reservation for the cluster in the
1959  * set of pending reservations, and false if not.
1960  */
ext4_is_pending(struct inode * inode,ext4_lblk_t lblk)1961 bool ext4_is_pending(struct inode *inode, ext4_lblk_t lblk)
1962 {
1963 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
1964 	struct ext4_inode_info *ei = EXT4_I(inode);
1965 	bool ret;
1966 
1967 	read_lock(&ei->i_es_lock);
1968 	ret = (bool)(__get_pending(inode, EXT4_B2C(sbi, lblk)) != NULL);
1969 	read_unlock(&ei->i_es_lock);
1970 
1971 	return ret;
1972 }
1973 
1974 /*
1975  * ext4_es_insert_delayed_block - adds a delayed block to the extents status
1976  *                                tree, adding a pending reservation where
1977  *                                needed
1978  *
1979  * @inode - file containing the newly added block
1980  * @lblk - logical block to be added
1981  * @allocated - indicates whether a physical cluster has been allocated for
1982  *              the logical cluster that contains the block
1983  *
1984  * Returns 0 on success, negative error code on failure.
1985  */
ext4_es_insert_delayed_block(struct inode * inode,ext4_lblk_t lblk,bool allocated)1986 int ext4_es_insert_delayed_block(struct inode *inode, ext4_lblk_t lblk,
1987 				 bool allocated)
1988 {
1989 	struct extent_status newes;
1990 	int err = 0;
1991 
1992 	if (EXT4_SB(inode->i_sb)->s_mount_state & EXT4_FC_REPLAY)
1993 		return 0;
1994 
1995 	es_debug("add [%u/1) delayed to extent status tree of inode %lu\n",
1996 		 lblk, inode->i_ino);
1997 
1998 	newes.es_lblk = lblk;
1999 	newes.es_len = 1;
2000 	ext4_es_store_pblock_status(&newes, ~0, EXTENT_STATUS_DELAYED);
2001 	trace_ext4_es_insert_delayed_block(inode, &newes, allocated);
2002 
2003 	ext4_es_insert_extent_check(inode, &newes);
2004 
2005 	write_lock(&EXT4_I(inode)->i_es_lock);
2006 
2007 	err = __es_remove_extent(inode, lblk, lblk, NULL);
2008 	if (err != 0)
2009 		goto error;
2010 retry:
2011 	err = __es_insert_extent(inode, &newes);
2012 	if (err == -ENOMEM && __es_shrink(EXT4_SB(inode->i_sb),
2013 					  128, EXT4_I(inode)))
2014 		goto retry;
2015 	if (err != 0)
2016 		goto error;
2017 
2018 	if (allocated)
2019 		__insert_pending(inode, lblk);
2020 
2021 error:
2022 	write_unlock(&EXT4_I(inode)->i_es_lock);
2023 
2024 	ext4_es_print_tree(inode);
2025 	ext4_print_pending_tree(inode);
2026 
2027 	return err;
2028 }
2029 
2030 /*
2031  * __es_delayed_clu - count number of clusters containing blocks that
2032  *                    are delayed only
2033  *
2034  * @inode - file containing block range
2035  * @start - logical block defining start of range
2036  * @end - logical block defining end of range
2037  *
2038  * Returns the number of clusters containing only delayed (not delayed
2039  * and unwritten) blocks in the range specified by @start and @end.  Any
2040  * cluster or part of a cluster within the range and containing a delayed
2041  * and not unwritten block within the range is counted as a whole cluster.
2042  */
__es_delayed_clu(struct inode * inode,ext4_lblk_t start,ext4_lblk_t end)2043 static unsigned int __es_delayed_clu(struct inode *inode, ext4_lblk_t start,
2044 				     ext4_lblk_t end)
2045 {
2046 	struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
2047 	struct extent_status *es;
2048 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2049 	struct rb_node *node;
2050 	ext4_lblk_t first_lclu, last_lclu;
2051 	unsigned long long last_counted_lclu;
2052 	unsigned int n = 0;
2053 
2054 	/* guaranteed to be unequal to any ext4_lblk_t value */
2055 	last_counted_lclu = ~0ULL;
2056 
2057 	es = __es_tree_search(&tree->root, start);
2058 
2059 	while (es && (es->es_lblk <= end)) {
2060 		if (ext4_es_is_delonly(es)) {
2061 			if (es->es_lblk <= start)
2062 				first_lclu = EXT4_B2C(sbi, start);
2063 			else
2064 				first_lclu = EXT4_B2C(sbi, es->es_lblk);
2065 
2066 			if (ext4_es_end(es) >= end)
2067 				last_lclu = EXT4_B2C(sbi, end);
2068 			else
2069 				last_lclu = EXT4_B2C(sbi, ext4_es_end(es));
2070 
2071 			if (first_lclu == last_counted_lclu)
2072 				n += last_lclu - first_lclu;
2073 			else
2074 				n += last_lclu - first_lclu + 1;
2075 			last_counted_lclu = last_lclu;
2076 		}
2077 		node = rb_next(&es->rb_node);
2078 		if (!node)
2079 			break;
2080 		es = rb_entry(node, struct extent_status, rb_node);
2081 	}
2082 
2083 	return n;
2084 }
2085 
2086 /*
2087  * ext4_es_delayed_clu - count number of clusters containing blocks that
2088  *                       are both delayed and unwritten
2089  *
2090  * @inode - file containing block range
2091  * @lblk - logical block defining start of range
2092  * @len - number of blocks in range
2093  *
2094  * Locking for external use of __es_delayed_clu().
2095  */
ext4_es_delayed_clu(struct inode * inode,ext4_lblk_t lblk,ext4_lblk_t len)2096 unsigned int ext4_es_delayed_clu(struct inode *inode, ext4_lblk_t lblk,
2097 				 ext4_lblk_t len)
2098 {
2099 	struct ext4_inode_info *ei = EXT4_I(inode);
2100 	ext4_lblk_t end;
2101 	unsigned int n;
2102 
2103 	if (len == 0)
2104 		return 0;
2105 
2106 	end = lblk + len - 1;
2107 	WARN_ON(end < lblk);
2108 
2109 	read_lock(&ei->i_es_lock);
2110 
2111 	n = __es_delayed_clu(inode, lblk, end);
2112 
2113 	read_unlock(&ei->i_es_lock);
2114 
2115 	return n;
2116 }
2117 
2118 /*
2119  * __revise_pending - makes, cancels, or leaves unchanged pending cluster
2120  *                    reservations for a specified block range depending
2121  *                    upon the presence or absence of delayed blocks
2122  *                    outside the range within clusters at the ends of the
2123  *                    range
2124  *
2125  * @inode - file containing the range
2126  * @lblk - logical block defining the start of range
2127  * @len  - length of range in blocks
2128  *
2129  * Used after a newly allocated extent is added to the extents status tree.
2130  * Requires that the extents in the range have either written or unwritten
2131  * status.  Must be called while holding i_es_lock.
2132  */
__revise_pending(struct inode * inode,ext4_lblk_t lblk,ext4_lblk_t len)2133 static void __revise_pending(struct inode *inode, ext4_lblk_t lblk,
2134 			     ext4_lblk_t len)
2135 {
2136 	struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2137 	ext4_lblk_t end = lblk + len - 1;
2138 	ext4_lblk_t first, last;
2139 	bool f_del = false, l_del = false;
2140 
2141 	if (len == 0)
2142 		return;
2143 
2144 	/*
2145 	 * Two cases - block range within single cluster and block range
2146 	 * spanning two or more clusters.  Note that a cluster belonging
2147 	 * to a range starting and/or ending on a cluster boundary is treated
2148 	 * as if it does not contain a delayed extent.  The new range may
2149 	 * have allocated space for previously delayed blocks out to the
2150 	 * cluster boundary, requiring that any pre-existing pending
2151 	 * reservation be canceled.  Because this code only looks at blocks
2152 	 * outside the range, it should revise pending reservations
2153 	 * correctly even if the extent represented by the range can't be
2154 	 * inserted in the extents status tree due to ENOSPC.
2155 	 */
2156 
2157 	if (EXT4_B2C(sbi, lblk) == EXT4_B2C(sbi, end)) {
2158 		first = EXT4_LBLK_CMASK(sbi, lblk);
2159 		if (first != lblk)
2160 			f_del = __es_scan_range(inode, &ext4_es_is_delonly,
2161 						first, lblk - 1);
2162 		if (f_del) {
2163 			__insert_pending(inode, first);
2164 		} else {
2165 			last = EXT4_LBLK_CMASK(sbi, end) +
2166 			       sbi->s_cluster_ratio - 1;
2167 			if (last != end)
2168 				l_del = __es_scan_range(inode,
2169 							&ext4_es_is_delonly,
2170 							end + 1, last);
2171 			if (l_del)
2172 				__insert_pending(inode, last);
2173 			else
2174 				__remove_pending(inode, last);
2175 		}
2176 	} else {
2177 		first = EXT4_LBLK_CMASK(sbi, lblk);
2178 		if (first != lblk)
2179 			f_del = __es_scan_range(inode, &ext4_es_is_delonly,
2180 						first, lblk - 1);
2181 		if (f_del)
2182 			__insert_pending(inode, first);
2183 		else
2184 			__remove_pending(inode, first);
2185 
2186 		last = EXT4_LBLK_CMASK(sbi, end) + sbi->s_cluster_ratio - 1;
2187 		if (last != end)
2188 			l_del = __es_scan_range(inode, &ext4_es_is_delonly,
2189 						end + 1, last);
2190 		if (l_del)
2191 			__insert_pending(inode, last);
2192 		else
2193 			__remove_pending(inode, last);
2194 	}
2195 }
2196