Branch data Line data Source code
1 : : /*
2 : : * fs/ext4/extents_status.c
3 : : *
4 : : * Written by Yongqiang Yang <xiaoqiangnk@gmail.com>
5 : : * Modified by
6 : : * Allison Henderson <achender@linux.vnet.ibm.com>
7 : : * Hugh Dickins <hughd@google.com>
8 : : * Zheng Liu <wenqing.lz@taobao.com>
9 : : *
10 : : * Ext4 extents status tree core functions.
11 : : */
12 : : #include <linux/rbtree.h>
13 : : #include <linux/list_sort.h>
14 : : #include "ext4.h"
15 : : #include "extents_status.h"
16 : :
17 : : #include <trace/events/ext4.h>
18 : :
19 : : /*
20 : : * According to previous discussion in Ext4 Developer Workshop, we
21 : : * will introduce a new structure called io tree to track all extent
22 : : * status in order to solve some problems that we have met
23 : : * (e.g. Reservation space warning), and provide extent-level locking.
24 : : * Delay extent tree is the first step to achieve this goal. It is
25 : : * original built by Yongqiang Yang. At that time it is called delay
26 : : * extent tree, whose goal is only track delayed extents in memory to
27 : : * simplify the implementation of fiemap and bigalloc, and introduce
28 : : * lseek SEEK_DATA/SEEK_HOLE support. That is why it is still called
29 : : * delay extent tree at the first commit. But for better understand
30 : : * what it does, it has been rename to extent status tree.
31 : : *
32 : : * Step1:
33 : : * Currently the first step has been done. All delayed extents are
34 : : * tracked in the tree. It maintains the delayed extent when a delayed
35 : : * allocation is issued, and the delayed extent is written out or
36 : : * invalidated. Therefore the implementation of fiemap and bigalloc
37 : : * are simplified, and SEEK_DATA/SEEK_HOLE are introduced.
38 : : *
39 : : * The following comment describes the implemenmtation of extent
40 : : * status tree and future works.
41 : : *
42 : : * Step2:
43 : : * In this step all extent status are tracked by extent status tree.
44 : : * Thus, we can first try to lookup a block mapping in this tree before
45 : : * finding it in extent tree. Hence, single extent cache can be removed
46 : : * because extent status tree can do a better job. Extents in status
47 : : * tree are loaded on-demand. Therefore, the extent status tree may not
48 : : * contain all of the extents in a file. Meanwhile we define a shrinker
49 : : * to reclaim memory from extent status tree because fragmented extent
50 : : * tree will make status tree cost too much memory. written/unwritten/-
51 : : * hole extents in the tree will be reclaimed by this shrinker when we
52 : : * are under high memory pressure. Delayed extents will not be
53 : : * reclimed because fiemap, bigalloc, and seek_data/hole need it.
54 : : */
55 : :
56 : : /*
57 : : * Extent status tree implementation for ext4.
58 : : *
59 : : *
60 : : * ==========================================================================
61 : : * Extent status tree tracks all extent status.
62 : : *
63 : : * 1. Why we need to implement extent status tree?
64 : : *
65 : : * Without extent status tree, ext4 identifies a delayed extent by looking
66 : : * up page cache, this has several deficiencies - complicated, buggy,
67 : : * and inefficient code.
68 : : *
69 : : * FIEMAP, SEEK_HOLE/DATA, bigalloc, and writeout all need to know if a
70 : : * block or a range of blocks are belonged to a delayed extent.
71 : : *
72 : : * Let us have a look at how they do without extent status tree.
73 : : * -- FIEMAP
74 : : * FIEMAP looks up page cache to identify delayed allocations from holes.
75 : : *
76 : : * -- SEEK_HOLE/DATA
77 : : * SEEK_HOLE/DATA has the same problem as FIEMAP.
78 : : *
79 : : * -- bigalloc
80 : : * bigalloc looks up page cache to figure out if a block is
81 : : * already under delayed allocation or not to determine whether
82 : : * quota reserving is needed for the cluster.
83 : : *
84 : : * -- writeout
85 : : * Writeout looks up whole page cache to see if a buffer is
86 : : * mapped, If there are not very many delayed buffers, then it is
87 : : * time comsuming.
88 : : *
89 : : * With extent status tree implementation, FIEMAP, SEEK_HOLE/DATA,
90 : : * bigalloc and writeout can figure out if a block or a range of
91 : : * blocks is under delayed allocation(belonged to a delayed extent) or
92 : : * not by searching the extent tree.
93 : : *
94 : : *
95 : : * ==========================================================================
96 : : * 2. Ext4 extent status tree impelmentation
97 : : *
98 : : * -- extent
99 : : * A extent is a range of blocks which are contiguous logically and
100 : : * physically. Unlike extent in extent tree, this extent in ext4 is
101 : : * a in-memory struct, there is no corresponding on-disk data. There
102 : : * is no limit on length of extent, so an extent can contain as many
103 : : * blocks as they are contiguous logically and physically.
104 : : *
105 : : * -- extent status tree
106 : : * Every inode has an extent status tree and all allocation blocks
107 : : * are added to the tree with different status. The extent in the
108 : : * tree are ordered by logical block no.
109 : : *
110 : : * -- operations on a extent status tree
111 : : * There are three important operations on a delayed extent tree: find
112 : : * next extent, adding a extent(a range of blocks) and removing a extent.
113 : : *
114 : : * -- race on a extent status tree
115 : : * Extent status tree is protected by inode->i_es_lock.
116 : : *
117 : : * -- memory consumption
118 : : * Fragmented extent tree will make extent status tree cost too much
119 : : * memory. Hence, we will reclaim written/unwritten/hole extents from
120 : : * the tree under a heavy memory pressure.
121 : : *
122 : : *
123 : : * ==========================================================================
124 : : * 3. Performance analysis
125 : : *
126 : : * -- overhead
127 : : * 1. There is a cache extent for write access, so if writes are
128 : : * not very random, adding space operaions are in O(1) time.
129 : : *
130 : : * -- gain
131 : : * 2. Code is much simpler, more readable, more maintainable and
132 : : * more efficient.
133 : : *
134 : : *
135 : : * ==========================================================================
136 : : * 4. TODO list
137 : : *
138 : : * -- Refactor delayed space reservation
139 : : *
140 : : * -- Extent-level locking
141 : : */
142 : :
143 : : static struct kmem_cache *ext4_es_cachep;
144 : :
145 : : static int __es_insert_extent(struct inode *inode, struct extent_status *newes);
146 : : static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
147 : : ext4_lblk_t end);
148 : : static int __es_try_to_reclaim_extents(struct ext4_inode_info *ei,
149 : : int nr_to_scan);
150 : : static int __ext4_es_shrink(struct ext4_sb_info *sbi, int nr_to_scan,
151 : : struct ext4_inode_info *locked_ei);
152 : :
153 : 0 : int __init ext4_init_es(void)
154 : : {
155 : 0 : ext4_es_cachep = kmem_cache_create("ext4_extent_status",
156 : : sizeof(struct extent_status),
157 : : 0, (SLAB_RECLAIM_ACCOUNT), NULL);
158 [ # # ]: 0 : if (ext4_es_cachep == NULL)
159 : : return -ENOMEM;
160 : 0 : return 0;
161 : : }
162 : :
163 : 0 : void ext4_exit_es(void)
164 : : {
165 [ # # ]: 0 : if (ext4_es_cachep)
166 : 0 : kmem_cache_destroy(ext4_es_cachep);
167 : 0 : }
168 : :
169 : 0 : void ext4_es_init_tree(struct ext4_es_tree *tree)
170 : : {
171 : 470986 : tree->root = RB_ROOT;
172 : 470986 : tree->cache_es = NULL;
173 : 470986 : }
174 : :
175 : : #ifdef ES_DEBUG__
176 : : static void ext4_es_print_tree(struct inode *inode)
177 : : {
178 : : struct ext4_es_tree *tree;
179 : : struct rb_node *node;
180 : :
181 : : printk(KERN_DEBUG "status extents for inode %lu:", inode->i_ino);
182 : : tree = &EXT4_I(inode)->i_es_tree;
183 : : node = rb_first(&tree->root);
184 : : while (node) {
185 : : struct extent_status *es;
186 : : es = rb_entry(node, struct extent_status, rb_node);
187 : : printk(KERN_DEBUG " [%u/%u) %llu %llx",
188 : : es->es_lblk, es->es_len,
189 : : ext4_es_pblock(es), ext4_es_status(es));
190 : : node = rb_next(node);
191 : : }
192 : : printk(KERN_DEBUG "\n");
193 : : }
194 : : #else
195 : : #define ext4_es_print_tree(inode)
196 : : #endif
197 : :
198 : : static inline ext4_lblk_t ext4_es_end(struct extent_status *es)
199 : : {
200 [ - + ][ - + ]: 27467328 : BUG_ON(es->es_lblk + es->es_len < es->es_lblk);
[ - + ][ # # ]
[ + ][ - + ]
[ + ][ - + ]
201 : 22377916 : return es->es_lblk + es->es_len - 1;
202 : : }
203 : :
204 : : /*
205 : : * search through the tree for an delayed extent with a given offset. If
206 : : * it can't be found, try to find next extent.
207 : : */
208 : 0 : static struct extent_status *__es_tree_search(struct rb_root *root,
209 : : ext4_lblk_t lblk)
210 : : {
211 : 4071165 : struct rb_node *node = root->rb_node;
212 : 9716250 : struct extent_status *es = NULL;
213 : :
214 [ + + ]: 11046574 : while (node) {
215 : : es = rb_entry(node, struct extent_status, rb_node);
216 [ + + ]: 8541232 : if (lblk < es->es_lblk)
217 : 615222 : node = node->rb_left;
218 [ + + ]: 7927705 : else if (lblk > ext4_es_end(es))
219 : 6975409 : node = node->rb_right;
220 : : else
221 : : return es;
222 : : }
223 : :
224 [ + + ][ + + ]: 2505342 : if (es && lblk < es->es_lblk)
225 : : return es;
226 : :
227 [ + + ][ + + ]: 4211759 : if (es && lblk > ext4_es_end(es)) {
228 : 1790237 : node = rb_next(&es->rb_node);
229 [ + + ]: 1790239 : return node ? rb_entry(node, struct extent_status, rb_node) :
230 : : NULL;
231 : : }
232 : :
233 : : return NULL;
234 : : }
235 : :
236 : : /*
237 : : * ext4_es_find_delayed_extent_range: find the 1st delayed extent covering
238 : : * @es->lblk if it exists, otherwise, the next extent after @es->lblk.
239 : : *
240 : : * @inode: the inode which owns delayed extents
241 : : * @lblk: the offset where we start to search
242 : : * @end: the offset where we stop to search
243 : : * @es: delayed extent that we found
244 : : */
245 : 0 : void ext4_es_find_delayed_extent_range(struct inode *inode,
246 : : ext4_lblk_t lblk, ext4_lblk_t end,
247 : : struct extent_status *es)
248 : : {
249 : : struct ext4_es_tree *tree = NULL;
250 : 216151 : struct extent_status *es1 = NULL;
251 : : struct rb_node *node;
252 : :
253 [ - + ]: 210813 : BUG_ON(es == NULL);
254 [ - + ]: 210813 : BUG_ON(end < lblk);
255 : : trace_ext4_es_find_delayed_extent_range_enter(inode, lblk);
256 : :
257 : 210813 : read_lock(&EXT4_I(inode)->i_es_lock);
258 : : tree = &EXT4_I(inode)->i_es_tree;
259 : :
260 : : /* find extent in cache firstly */
261 : 210824 : es->es_lblk = es->es_len = es->es_pblk = 0;
262 [ + + ]: 210824 : if (tree->cache_es) {
263 : : es1 = tree->cache_es;
264 [ + + ][ + + ]: 156488 : if (in_range(lblk, es1->es_lblk, es1->es_len)) {
265 : : es_debug("%u cached by [%u/%u) %llu %x\n",
266 : : lblk, es1->es_lblk, es1->es_len,
267 : : ext4_es_pblock(es1), ext4_es_status(es1));
268 : : goto out;
269 : : }
270 : : }
271 : :
272 : 209329 : es1 = __es_tree_search(&tree->root, lblk);
273 : :
274 : : out:
275 [ + + ][ + + ]: 210826 : if (es1 && !ext4_es_is_delayed(es1)) {
276 [ + + ]: 94036 : while ((node = rb_next(&es1->rb_node)) != NULL) {
277 : : es1 = rb_entry(node, struct extent_status, rb_node);
278 [ + + ]: 22242 : if (es1->es_lblk > end) {
279 : : es1 = NULL;
280 : : break;
281 : : }
282 [ + + ]: 103064 : if (ext4_es_is_delayed(es1))
283 : : break;
284 : : }
285 : : }
286 : :
287 [ + + ][ + + ]: 210826 : if (es1 && ext4_es_is_delayed(es1)) {
288 : 25168 : tree->cache_es = es1;
289 : 25168 : es->es_lblk = es1->es_lblk;
290 : 25168 : es->es_len = es1->es_len;
291 : 25168 : es->es_pblk = es1->es_pblk;
292 : : }
293 : :
294 : : read_unlock(&EXT4_I(inode)->i_es_lock);
295 : :
296 : : trace_ext4_es_find_delayed_extent_range_exit(inode, es);
297 : 210822 : }
298 : :
299 : : static struct extent_status *
300 : 0 : ext4_es_alloc_extent(struct inode *inode, ext4_lblk_t lblk, ext4_lblk_t len,
301 : : ext4_fsblk_t pblk)
302 : : {
303 : : struct extent_status *es;
304 : 379151 : es = kmem_cache_alloc(ext4_es_cachep, GFP_ATOMIC);
305 [ + + ]: 379207 : if (es == NULL)
306 : : return NULL;
307 : 379191 : es->es_lblk = lblk;
308 : 379191 : es->es_len = len;
309 : 379191 : es->es_pblk = pblk;
310 : :
311 : : /*
312 : : * We don't count delayed extent because we never try to reclaim them
313 : : */
314 [ + + ]: 379191 : if (!ext4_es_is_delayed(es)) {
315 : 196719 : EXT4_I(inode)->i_es_lru_nr++;
316 : 196719 : percpu_counter_inc(&EXT4_SB(inode->i_sb)->s_extent_cache_cnt);
317 : : }
318 : :
319 : 379196 : return es;
320 : : }
321 : :
322 : 0 : static void ext4_es_free_extent(struct inode *inode, struct extent_status *es)
323 : : {
324 : : /* Decrease the lru counter when this es is not delayed */
325 [ + + ]: 384573 : if (!ext4_es_is_delayed(es)) {
326 [ - + ]: 202473 : BUG_ON(EXT4_I(inode)->i_es_lru_nr == 0);
327 : 202473 : EXT4_I(inode)->i_es_lru_nr--;
328 : 202473 : percpu_counter_dec(&EXT4_SB(inode->i_sb)->s_extent_cache_cnt);
329 : : }
330 : :
331 : 384593 : kmem_cache_free(ext4_es_cachep, es);
332 : 384598 : }
333 : :
334 : : /*
335 : : * Check whether or not two extents can be merged
336 : : * Condition:
337 : : * - logical block number is contiguous
338 : : * - physical block number is contiguous
339 : : * - status is equal
340 : : */
341 : 0 : static int ext4_es_can_be_merged(struct extent_status *es1,
342 : 5964733 : struct extent_status *es2)
343 : : {
344 [ + + ]: 5964733 : if (ext4_es_status(es1) != ext4_es_status(es2))
345 : : return 0;
346 : :
347 [ + + ]: 4162875 : if (((__u64) es1->es_len) + es2->es_len > 0xFFFFFFFFULL)
348 : : return 0;
349 : :
350 [ + + ]: 4162865 : if (((__u64) es1->es_lblk) + es1->es_len != es2->es_lblk)
351 : : return 0;
352 : :
353 [ + + ][ + ]: 1818532 : if ((ext4_es_is_written(es1) || ext4_es_is_unwritten(es1)) &&
[ + ]
354 : 140689 : (ext4_es_pblock(es1) + es1->es_len == ext4_es_pblock(es2)))
355 : : return 1;
356 : :
357 [ + + ]: 1687553 : if (ext4_es_is_hole(es1))
358 : : return 1;
359 : :
360 : : /* we need to check delayed extent is without unwritten status */
361 [ + + ][ + + ]: 1687552 : if (ext4_es_is_delayed(es1) && !ext4_es_is_unwritten(es1))
362 : : return 1;
363 : :
364 : 9710 : return 0;
365 : : }
366 : :
367 : : static struct extent_status *
368 : 0 : ext4_es_try_to_merge_left(struct inode *inode, struct extent_status *es)
369 : : {
370 : : struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
371 : : struct extent_status *es1;
372 : : struct rb_node *node;
373 : :
374 : 18673 : node = rb_prev(&es->rb_node);
375 [ + + ]: 18673 : if (!node)
376 : : return es;
377 : :
378 : : es1 = rb_entry(node, struct extent_status, rb_node);
379 [ + + ]: 18154 : if (ext4_es_can_be_merged(es1, es)) {
380 : 11107 : es1->es_len += es->es_len;
381 : 11107 : rb_erase(&es->rb_node, &tree->root);
382 : 11107 : ext4_es_free_extent(inode, es);
383 : : es = es1;
384 : : }
385 : :
386 : 18154 : return es;
387 : : }
388 : :
389 : : static struct extent_status *
390 : 0 : ext4_es_try_to_merge_right(struct inode *inode, struct extent_status *es)
391 : : {
392 : : struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
393 : : struct extent_status *es1;
394 : : struct rb_node *node;
395 : :
396 : 1771202 : node = rb_next(&es->rb_node);
397 [ + + ]: 1771206 : if (!node)
398 : : return es;
399 : :
400 : : es1 = rb_entry(node, struct extent_status, rb_node);
401 [ + + ]: 180411 : if (ext4_es_can_be_merged(es, es1)) {
402 : 7854 : es->es_len += es1->es_len;
403 : 7854 : rb_erase(node, &tree->root);
404 : 7854 : ext4_es_free_extent(inode, es1);
405 : : }
406 : :
407 : : return es;
408 : : }
409 : :
410 : : #ifdef ES_AGGRESSIVE_TEST
411 : : #include "ext4_extents.h" /* Needed when ES_AGGRESSIVE_TEST is defined */
412 : :
413 : : static void ext4_es_insert_extent_ext_check(struct inode *inode,
414 : : struct extent_status *es)
415 : : {
416 : : struct ext4_ext_path *path = NULL;
417 : : struct ext4_extent *ex;
418 : : ext4_lblk_t ee_block;
419 : : ext4_fsblk_t ee_start;
420 : : unsigned short ee_len;
421 : : int depth, ee_status, es_status;
422 : :
423 : : path = ext4_ext_find_extent(inode, es->es_lblk, NULL, EXT4_EX_NOCACHE);
424 : : if (IS_ERR(path))
425 : : return;
426 : :
427 : : depth = ext_depth(inode);
428 : : ex = path[depth].p_ext;
429 : :
430 : : if (ex) {
431 : :
432 : : ee_block = le32_to_cpu(ex->ee_block);
433 : : ee_start = ext4_ext_pblock(ex);
434 : : ee_len = ext4_ext_get_actual_len(ex);
435 : :
436 : : ee_status = ext4_ext_is_uninitialized(ex) ? 1 : 0;
437 : : es_status = ext4_es_is_unwritten(es) ? 1 : 0;
438 : :
439 : : /*
440 : : * Make sure ex and es are not overlap when we try to insert
441 : : * a delayed/hole extent.
442 : : */
443 : : if (!ext4_es_is_written(es) && !ext4_es_is_unwritten(es)) {
444 : : if (in_range(es->es_lblk, ee_block, ee_len)) {
445 : : pr_warn("ES insert assertion failed for "
446 : : "inode: %lu we can find an extent "
447 : : "at block [%d/%d/%llu/%c], but we "
448 : : "want to add an delayed/hole extent "
449 : : "[%d/%d/%llu/%llx]\n",
450 : : inode->i_ino, ee_block, ee_len,
451 : : ee_start, ee_status ? 'u' : 'w',
452 : : es->es_lblk, es->es_len,
453 : : ext4_es_pblock(es), ext4_es_status(es));
454 : : }
455 : : goto out;
456 : : }
457 : :
458 : : /*
459 : : * We don't check ee_block == es->es_lblk, etc. because es
460 : : * might be a part of whole extent, vice versa.
461 : : */
462 : : if (es->es_lblk < ee_block ||
463 : : ext4_es_pblock(es) != ee_start + es->es_lblk - ee_block) {
464 : : pr_warn("ES insert assertion failed for inode: %lu "
465 : : "ex_status [%d/%d/%llu/%c] != "
466 : : "es_status [%d/%d/%llu/%c]\n", inode->i_ino,
467 : : ee_block, ee_len, ee_start,
468 : : ee_status ? 'u' : 'w', es->es_lblk, es->es_len,
469 : : ext4_es_pblock(es), es_status ? 'u' : 'w');
470 : : goto out;
471 : : }
472 : :
473 : : if (ee_status ^ es_status) {
474 : : pr_warn("ES insert assertion failed for inode: %lu "
475 : : "ex_status [%d/%d/%llu/%c] != "
476 : : "es_status [%d/%d/%llu/%c]\n", inode->i_ino,
477 : : ee_block, ee_len, ee_start,
478 : : ee_status ? 'u' : 'w', es->es_lblk, es->es_len,
479 : : ext4_es_pblock(es), es_status ? 'u' : 'w');
480 : : }
481 : : } else {
482 : : /*
483 : : * We can't find an extent on disk. So we need to make sure
484 : : * that we don't want to add an written/unwritten extent.
485 : : */
486 : : if (!ext4_es_is_delayed(es) && !ext4_es_is_hole(es)) {
487 : : pr_warn("ES insert assertion failed for inode: %lu "
488 : : "can't find an extent at block %d but we want "
489 : : "to add an written/unwritten extent "
490 : : "[%d/%d/%llu/%llx]\n", inode->i_ino,
491 : : es->es_lblk, es->es_lblk, es->es_len,
492 : : ext4_es_pblock(es), ext4_es_status(es));
493 : : }
494 : : }
495 : : out:
496 : : if (path) {
497 : : ext4_ext_drop_refs(path);
498 : : kfree(path);
499 : : }
500 : : }
501 : :
502 : : static void ext4_es_insert_extent_ind_check(struct inode *inode,
503 : : struct extent_status *es)
504 : : {
505 : : struct ext4_map_blocks map;
506 : : int retval;
507 : :
508 : : /*
509 : : * Here we call ext4_ind_map_blocks to lookup a block mapping because
510 : : * 'Indirect' structure is defined in indirect.c. So we couldn't
511 : : * access direct/indirect tree from outside. It is too dirty to define
512 : : * this function in indirect.c file.
513 : : */
514 : :
515 : : map.m_lblk = es->es_lblk;
516 : : map.m_len = es->es_len;
517 : :
518 : : retval = ext4_ind_map_blocks(NULL, inode, &map, 0);
519 : : if (retval > 0) {
520 : : if (ext4_es_is_delayed(es) || ext4_es_is_hole(es)) {
521 : : /*
522 : : * We want to add a delayed/hole extent but this
523 : : * block has been allocated.
524 : : */
525 : : pr_warn("ES insert assertion failed for inode: %lu "
526 : : "We can find blocks but we want to add a "
527 : : "delayed/hole extent [%d/%d/%llu/%llx]\n",
528 : : inode->i_ino, es->es_lblk, es->es_len,
529 : : ext4_es_pblock(es), ext4_es_status(es));
530 : : return;
531 : : } else if (ext4_es_is_written(es)) {
532 : : if (retval != es->es_len) {
533 : : pr_warn("ES insert assertion failed for "
534 : : "inode: %lu retval %d != es_len %d\n",
535 : : inode->i_ino, retval, es->es_len);
536 : : return;
537 : : }
538 : : if (map.m_pblk != ext4_es_pblock(es)) {
539 : : pr_warn("ES insert assertion failed for "
540 : : "inode: %lu m_pblk %llu != "
541 : : "es_pblk %llu\n",
542 : : inode->i_ino, map.m_pblk,
543 : : ext4_es_pblock(es));
544 : : return;
545 : : }
546 : : } else {
547 : : /*
548 : : * We don't need to check unwritten extent because
549 : : * indirect-based file doesn't have it.
550 : : */
551 : : BUG_ON(1);
552 : : }
553 : : } else if (retval == 0) {
554 : : if (ext4_es_is_written(es)) {
555 : : pr_warn("ES insert assertion failed for inode: %lu "
556 : : "We can't find the block but we want to add "
557 : : "an written extent [%d/%d/%llu/%llx]\n",
558 : : inode->i_ino, es->es_lblk, es->es_len,
559 : : ext4_es_pblock(es), ext4_es_status(es));
560 : : return;
561 : : }
562 : : }
563 : : }
564 : :
565 : : static inline void ext4_es_insert_extent_check(struct inode *inode,
566 : : struct extent_status *es)
567 : : {
568 : : /*
569 : : * We don't need to worry about the race condition because
570 : : * caller takes i_data_sem locking.
571 : : */
572 : : BUG_ON(!rwsem_is_locked(&EXT4_I(inode)->i_data_sem));
573 : : if (ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
574 : : ext4_es_insert_extent_ext_check(inode, es);
575 : : else
576 : : ext4_es_insert_extent_ind_check(inode, es);
577 : : }
578 : : #else
579 : : static inline void ext4_es_insert_extent_check(struct inode *inode,
580 : : struct extent_status *es)
581 : : {
582 : : }
583 : : #endif
584 : :
585 : 0 : static int __es_insert_extent(struct inode *inode, struct extent_status *newes)
586 : : {
587 : : struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
588 : 2168842 : struct rb_node **p = &tree->root.rb_node;
589 : : struct rb_node *parent = NULL;
590 : 5063594 : struct extent_status *es;
591 : :
592 [ + + ]: 6144688 : while (*p) {
593 : : parent = *p;
594 : : es = rb_entry(parent, struct extent_status, rb_node);
595 : :
596 [ + + ]: 5765615 : if (newes->es_lblk < es->es_lblk) {
597 [ + + ]: 720694 : if (ext4_es_can_be_merged(newes, es)) {
598 : : /*
599 : : * Here we can modify es_lblk directly
600 : : * because it isn't overlapped.
601 : : */
602 : 18673 : es->es_lblk = newes->es_lblk;
603 : 18673 : es->es_len += newes->es_len;
604 [ + + ][ - + ]: 18673 : if (ext4_es_is_written(es) ||
605 : : ext4_es_is_unwritten(es))
606 : 3561 : ext4_es_store_pblock(es,
607 : : newes->es_pblk);
608 : 18673 : es = ext4_es_try_to_merge_left(inode, es);
609 : 18673 : goto out;
610 : : }
611 : 702266 : p = &(*p)->rb_left;
612 [ + - ]: 5044921 : } else if (newes->es_lblk > ext4_es_end(es)) {
613 [ + + ]: 5044921 : if (ext4_es_can_be_merged(es, newes)) {
614 : 1771191 : es->es_len += newes->es_len;
615 : 1771191 : es = ext4_es_try_to_merge_right(inode, es);
616 : 1771203 : goto out;
617 : : }
618 : 3273580 : p = &(*p)->rb_right;
619 : : } else {
620 : 3975846 : BUG_ON(1);
621 : : return -EINVAL;
622 : : }
623 : : }
624 : :
625 : 379073 : es = ext4_es_alloc_extent(inode, newes->es_lblk, newes->es_len,
626 : : newes->es_pblk);
627 [ + + ]: 379130 : if (!es)
628 : : return -ENOMEM;
629 : 379125 : rb_link_node(&es->rb_node, parent, p);
630 : 379125 : rb_insert_color(&es->rb_node, &tree->root);
631 : :
632 : : out:
633 : 2169035 : tree->cache_es = es;
634 : 2169035 : return 0;
635 : : }
636 : :
637 : : /*
638 : : * ext4_es_insert_extent() adds information to an inode's extent
639 : : * status tree.
640 : : *
641 : : * Return 0 on success, error code on failure.
642 : : */
643 : 0 : int ext4_es_insert_extent(struct inode *inode, ext4_lblk_t lblk,
644 : : ext4_lblk_t len, ext4_fsblk_t pblk,
645 : : unsigned int status)
646 : : {
647 : : struct extent_status newes;
648 : 2111622 : ext4_lblk_t end = lblk + len - 1;
649 : : int err = 0;
650 : :
651 : : es_debug("add [%u/%u) %llu %x to extent status tree of inode %lu\n",
652 : : lblk, len, pblk, status, inode->i_ino);
653 : :
654 [ + + ]: 2111622 : if (!len)
655 : : return 0;
656 : :
657 [ - + ]: 2111344 : BUG_ON(end < lblk);
658 : :
659 : 2111344 : newes.es_lblk = lblk;
660 : 2111344 : newes.es_len = len;
661 : : ext4_es_store_pblock(&newes, pblk);
662 : : ext4_es_store_status(&newes, status);
663 : : trace_ext4_es_insert_extent(inode, &newes);
664 : :
665 : : ext4_es_insert_extent_check(inode, &newes);
666 : :
667 : 2111344 : write_lock(&EXT4_I(inode)->i_es_lock);
668 : 2111644 : err = __es_remove_extent(inode, lblk, end);
669 [ + ]: 2111651 : if (err != 0)
670 : : goto error;
671 : : retry:
672 : 2111710 : err = __es_insert_extent(inode, &newes);
673 [ - + ][ # # ]: 2111682 : if (err == -ENOMEM && __ext4_es_shrink(EXT4_SB(inode->i_sb), 1,
674 : 0 : EXT4_I(inode)))
675 : : goto retry;
676 [ - + ][ # # ]: 2111652 : if (err == -ENOMEM && !ext4_es_is_delayed(&newes))
677 : : err = 0;
678 : :
679 : : error:
680 : : write_unlock(&EXT4_I(inode)->i_es_lock);
681 : :
682 : : ext4_es_print_tree(inode);
683 : :
684 : 2111700 : return err;
685 : : }
686 : :
687 : : /*
688 : : * ext4_es_cache_extent() inserts information into the extent status
689 : : * tree if and only if there isn't information about the range in
690 : : * question already.
691 : : */
692 : 0 : void ext4_es_cache_extent(struct inode *inode, ext4_lblk_t lblk,
693 : : ext4_lblk_t len, ext4_fsblk_t pblk,
694 : : unsigned int status)
695 : : {
696 : : struct extent_status *es;
697 : : struct extent_status newes;
698 : 187 : ext4_lblk_t end = lblk + len - 1;
699 : :
700 : 187 : newes.es_lblk = lblk;
701 : 187 : newes.es_len = len;
702 : : ext4_es_store_pblock(&newes, pblk);
703 : : ext4_es_store_status(&newes, status);
704 : : trace_ext4_es_cache_extent(inode, &newes);
705 : :
706 [ + - ]: 374 : if (!len)
707 : 0 : return;
708 : :
709 [ - + ]: 187 : BUG_ON(end < lblk);
710 : :
711 : 187 : write_lock(&EXT4_I(inode)->i_es_lock);
712 : :
713 : 187 : es = __es_tree_search(&EXT4_I(inode)->i_es_tree.root, lblk);
714 [ + + ][ + + ]: 187 : if (!es || es->es_lblk > end)
715 : 79 : __es_insert_extent(inode, &newes);
716 : : write_unlock(&EXT4_I(inode)->i_es_lock);
717 : : }
718 : :
719 : : /*
720 : : * ext4_es_lookup_extent() looks up an extent in extent status tree.
721 : : *
722 : : * ext4_es_lookup_extent is called by ext4_map_blocks/ext4_da_map_blocks.
723 : : *
724 : : * Return: 1 on found, 0 on not
725 : : */
726 : 0 : int ext4_es_lookup_extent(struct inode *inode, ext4_lblk_t lblk,
727 : : struct extent_status *es)
728 : : {
729 : : struct ext4_es_tree *tree;
730 : 5665487 : struct extent_status *es1 = NULL;
731 : : struct rb_node *node;
732 : : int found = 0;
733 : :
734 : : trace_ext4_es_lookup_extent_enter(inode, lblk);
735 : : es_debug("lookup extent in block %u\n", lblk);
736 : :
737 : : tree = &EXT4_I(inode)->i_es_tree;
738 : 4375402 : read_lock(&EXT4_I(inode)->i_es_lock);
739 : :
740 : : /* find extent in cache firstly */
741 : 4375481 : es->es_lblk = es->es_len = es->es_pblk = 0;
742 [ + + ]: 4375481 : if (tree->cache_es) {
743 : : es1 = tree->cache_es;
744 [ + + ][ + + ]: 4231482 : if (in_range(lblk, es1->es_lblk, es1->es_len)) {
745 : : es_debug("%u cached by [%u/%u)\n",
746 : : lblk, es1->es_lblk, es1->es_len);
747 : : found = 1;
748 : : goto out;
749 : : }
750 : : }
751 : :
752 : 2338017 : node = tree->root.rb_node;
753 [ + + ]: 8401924 : while (node) {
754 : : es1 = rb_entry(node, struct extent_status, rb_node);
755 [ + + ]: 6419051 : if (lblk < es1->es_lblk)
756 : 753564 : node = node->rb_left;
757 [ + + ]: 5667753 : else if (lblk > ext4_es_end(es1))
758 : 6063907 : node = node->rb_right;
759 : : else {
760 : : found = 1;
761 : : break;
762 : : }
763 : : }
764 : :
765 : : out:
766 [ + + ]: 4377747 : if (found) {
767 [ - + ]: 2395295 : BUG_ON(!es1);
768 : 2395295 : es->es_lblk = es1->es_lblk;
769 : 2395295 : es->es_len = es1->es_len;
770 : 2395295 : es->es_pblk = es1->es_pblk;
771 : : }
772 : :
773 : : read_unlock(&EXT4_I(inode)->i_es_lock);
774 : :
775 : : trace_ext4_es_lookup_extent_exit(inode, es, found);
776 : 4375576 : return found;
777 : : }
778 : :
779 : 3863823 : static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
780 : : ext4_lblk_t end)
781 : : {
782 : : struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
783 : : struct rb_node *node;
784 : 462175 : struct extent_status *es;
785 : : struct extent_status orig_es;
786 : : ext4_lblk_t len1, len2;
787 : : ext4_fsblk_t block;
788 : : int err;
789 : :
790 : : retry:
791 : : err = 0;
792 : 3863823 : es = __es_tree_search(&tree->root, lblk);
793 [ + + ]: 3863835 : if (!es)
794 : : goto out;
795 [ + ]: 1633336 : if (es->es_lblk > end)
796 : : goto out;
797 : :
798 : : /* Simply invalidate cache_es. */
799 : 5348945 : tree->cache_es = NULL;
800 : :
801 : 5348945 : orig_es.es_lblk = es->es_lblk;
802 : 5348945 : orig_es.es_len = es->es_len;
803 : 5348945 : orig_es.es_pblk = es->es_pblk;
804 : :
805 [ + + ]: 5348945 : len1 = lblk > es->es_lblk ? lblk - es->es_lblk : 0;
806 [ + + ]: 2714672 : len2 = ext4_es_end(es) > end ? ext4_es_end(es) - end : 0;
807 [ + + ]: 1485122 : if (len1 > 0)
808 : 77323 : es->es_len = len1;
809 [ + + ]: 1485122 : if (len2 > 0) {
810 [ + + ]: 1229540 : if (len1 > 0) {
811 : : struct extent_status newes;
812 : :
813 : 57174 : newes.es_lblk = end + 1;
814 : 57174 : newes.es_len = len2;
815 [ + ][ + + ]: 57174 : if (ext4_es_is_written(&orig_es) ||
816 : : ext4_es_is_unwritten(&orig_es)) {
817 : 0 : block = ext4_es_pblock(&orig_es) +
818 : 0 : orig_es.es_len - len2;
819 : : ext4_es_store_pblock(&newes, block);
820 : : }
821 : : ext4_es_store_status(&newes, ext4_es_status(&orig_es));
822 : 57174 : err = __es_insert_extent(inode, &newes);
823 [ - + ]: 57293 : if (err) {
824 : 0 : es->es_lblk = orig_es.es_lblk;
825 : 0 : es->es_len = orig_es.es_len;
826 [ # # # # ]: 57293 : if ((err == -ENOMEM) &&
827 : 0 : __ext4_es_shrink(EXT4_SB(inode->i_sb), 1,
828 : 0 : EXT4_I(inode)))
829 : : goto retry;
830 : 0 : goto out;
831 : : }
832 : : } else {
833 : 1172366 : es->es_lblk = end + 1;
834 : 1172366 : es->es_len = len2;
835 [ + + ][ - + ]: 1172366 : if (ext4_es_is_written(es) ||
836 : : ext4_es_is_unwritten(es)) {
837 : 1 : block = orig_es.es_pblk + orig_es.es_len - len2;
838 : : ext4_es_store_pblock(es, block);
839 : : }
840 : : }
841 : : goto out;
842 : : }
843 : :
844 [ + + ]: 255582 : if (len1 > 0) {
845 : 19996 : node = rb_next(&es->rb_node);
846 [ + + ]: 255582 : if (node)
847 : : es = rb_entry(node, struct extent_status, rb_node);
848 : : else
849 : : es = NULL;
850 : : }
851 : :
852 [ + + ][ + + ]: 933069 : while (es && ext4_es_end(es) <= end) {
853 : 352044 : node = rb_next(&es->rb_node);
854 : 352108 : rb_erase(&es->rb_node, &tree->root);
855 : 352089 : ext4_es_free_extent(inode, es);
856 [ + + ]: 352117 : if (!node) {
857 : : es = NULL;
858 : : break;
859 : : }
860 : : es = rb_entry(node, struct extent_status, rb_node);
861 : : }
862 : :
863 [ + + ][ - + ]: 255655 : if (es && es->es_lblk < end + 1) {
864 : 0 : ext4_lblk_t orig_len = es->es_len;
865 : :
866 : 0 : len1 = ext4_es_end(es) - end;
867 : 0 : es->es_lblk = end + 1;
868 : 0 : es->es_len = len1;
869 [ # # ][ # # ]: 0 : if (ext4_es_is_written(es) || ext4_es_is_unwritten(es)) {
870 : 0 : block = es->es_pblk + orig_len - len1;
871 : : ext4_es_store_pblock(es, block);
872 : : }
873 : : }
874 : :
875 : : out:
876 : 204 : return err;
877 : : }
878 : :
879 : : /*
880 : : * ext4_es_remove_extent() removes a space from a extent status tree.
881 : : *
882 : : * Return 0 on success, error code on failure.
883 : : */
884 : 0 : int ext4_es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
885 : : ext4_lblk_t len)
886 : : {
887 : : ext4_lblk_t end;
888 : : int err = 0;
889 : :
890 : : trace_ext4_es_remove_extent(inode, lblk, len);
891 : : es_debug("remove [%u/%u) from extent status tree of inode %lu\n",
892 : : lblk, len, inode->i_ino);
893 : :
894 [ + - ]: 3504342 : if (!len)
895 : : return err;
896 : :
897 : 1752171 : end = lblk + len - 1;
898 [ - + ]: 1752171 : BUG_ON(end < lblk);
899 : :
900 : 1752171 : write_lock(&EXT4_I(inode)->i_es_lock);
901 : 1752172 : err = __es_remove_extent(inode, lblk, end);
902 : : write_unlock(&EXT4_I(inode)->i_es_lock);
903 : : ext4_es_print_tree(inode);
904 : 1752172 : return err;
905 : : }
906 : :
907 : 0 : static int ext4_inode_touch_time_cmp(void *priv, struct list_head *a,
908 : : struct list_head *b)
909 : : {
910 : : struct ext4_inode_info *eia, *eib;
911 : : eia = list_entry(a, struct ext4_inode_info, i_es_lru);
912 : : eib = list_entry(b, struct ext4_inode_info, i_es_lru);
913 : :
914 [ - + ][ # # ]: 13458515 : if (ext4_test_inode_state(&eia->vfs_inode, EXT4_STATE_EXT_PRECACHED) &&
915 : : !ext4_test_inode_state(&eib->vfs_inode, EXT4_STATE_EXT_PRECACHED))
916 : : return 1;
917 [ + - ][ + - ]: 26917030 : if (!ext4_test_inode_state(&eia->vfs_inode, EXT4_STATE_EXT_PRECACHED) &&
918 : : ext4_test_inode_state(&eib->vfs_inode, EXT4_STATE_EXT_PRECACHED))
919 : : return -1;
920 [ + + ]: 13458515 : if (eia->i_touch_when == eib->i_touch_when)
921 : : return 0;
922 [ + + ]: 10322215 : if (time_after(eia->i_touch_when, eib->i_touch_when))
923 : : return 1;
924 : : else
925 : : return -1;
926 : : }
927 : :
928 : 0 : static int __ext4_es_shrink(struct ext4_sb_info *sbi, int nr_to_scan,
929 : : struct ext4_inode_info *locked_ei)
930 : : {
931 : : struct ext4_inode_info *ei;
932 : : struct list_head *cur, *tmp;
933 : 73535 : LIST_HEAD(skipped);
934 : : int nr_shrunk = 0;
935 : : int retried = 0, skip_precached = 1, nr_skipped = 0;
936 : :
937 : : spin_lock(&sbi->s_es_lru_lock);
938 : :
939 : : retry:
940 [ + + ]: 7613311 : list_for_each_safe(cur, tmp, &sbi->s_es_lru) {
941 : : int shrunk;
942 : :
943 : : /*
944 : : * If we have already reclaimed all extents from extent
945 : : * status tree, just stop the loop immediately.
946 : : */
947 [ + - ]: 7466466 : if (percpu_counter_read_positive(&sbi->s_extent_cache_cnt) == 0)
948 : : break;
949 : :
950 : 7466466 : ei = list_entry(cur, struct ext4_inode_info, i_es_lru);
951 : :
952 : : /*
953 : : * Skip the inode that is newer than the last_sorted
954 : : * time. Normally we try hard to avoid shrinking
955 : : * precached inodes, but we will as a last resort.
956 : : */
957 [ + + ][ + - ]: 7466466 : if ((sbi->s_es_last_sorted < ei->i_touch_when) ||
958 [ - + ]: 13375 : (skip_precached && ext4_test_inode_state(&ei->vfs_inode,
959 : : EXT4_STATE_EXT_PRECACHED))) {
960 : 7453091 : nr_skipped++;
961 : : list_move_tail(cur, &skipped);
962 : 7453091 : continue;
963 : : }
964 : :
965 [ + + ][ - + ]: 13375 : if (ei->i_es_lru_nr == 0 || ei == locked_ei)
966 : 6 : continue;
967 : :
968 : 13369 : write_lock(&ei->i_es_lock);
969 : 13369 : shrunk = __es_try_to_reclaim_extents(ei, nr_to_scan);
970 [ + + ]: 13369 : if (ei->i_es_lru_nr == 0)
971 : 13366 : list_del_init(&ei->i_es_lru);
972 : : write_unlock(&ei->i_es_lock);
973 : :
974 : 13369 : nr_shrunk += shrunk;
975 : 13369 : nr_to_scan -= shrunk;
976 [ + + ]: 13369 : if (nr_to_scan == 0)
977 : : break;
978 : : }
979 : :
980 : : /* Move the newer inodes into the tail of the LRU list. */
981 : : list_splice_tail(&skipped, &sbi->s_es_lru);
982 : : INIT_LIST_HEAD(&skipped);
983 : :
984 : : /*
985 : : * If we skipped any inodes, and we weren't able to make any
986 : : * forward progress, sort the list and try again.
987 : : */
988 [ + ][ + + ]: 146950 : if ((nr_shrunk == 0) && nr_skipped && !retried) {
989 : 73415 : retried++;
990 : 73415 : list_sort(NULL, &sbi->s_es_lru, ext4_inode_touch_time_cmp);
991 : 73415 : sbi->s_es_last_sorted = jiffies;
992 : 73415 : ei = list_first_entry(&sbi->s_es_lru, struct ext4_inode_info,
993 : : i_es_lru);
994 : : /*
995 : : * If there are no non-precached inodes left on the
996 : : * list, start releasing precached extents.
997 : : */
998 [ + - ]: 73415 : if (ext4_test_inode_state(&ei->vfs_inode,
999 : : EXT4_STATE_EXT_PRECACHED))
1000 : : skip_precached = 0;
1001 : : goto retry;
1002 : : }
1003 : :
1004 : : spin_unlock(&sbi->s_es_lru_lock);
1005 : :
1006 [ - + ]: 73535 : if (locked_ei && nr_shrunk == 0)
1007 : 0 : nr_shrunk = __es_try_to_reclaim_extents(locked_ei, nr_to_scan);
1008 : :
1009 : 73535 : return nr_shrunk;
1010 : : }
1011 : :
1012 : 0 : static unsigned long ext4_es_count(struct shrinker *shrink,
1013 : : struct shrink_control *sc)
1014 : : {
1015 : : unsigned long nr;
1016 : : struct ext4_sb_info *sbi;
1017 : :
1018 : : sbi = container_of(shrink, struct ext4_sb_info, s_es_shrinker);
1019 : 1480161 : nr = percpu_counter_read_positive(&sbi->s_extent_cache_cnt);
1020 : 740081 : trace_ext4_es_shrink_enter(sbi->s_sb, sc->nr_to_scan, nr);
1021 : 1 : return nr;
1022 : : }
1023 : :
1024 : 0 : static unsigned long ext4_es_scan(struct shrinker *shrink,
1025 : : struct shrink_control *sc)
1026 : : {
1027 : 73535 : struct ext4_sb_info *sbi = container_of(shrink,
1028 : : struct ext4_sb_info, s_es_shrinker);
1029 : 73535 : int nr_to_scan = sc->nr_to_scan;
1030 : : int ret, nr_shrunk;
1031 : :
1032 : 147070 : ret = percpu_counter_read_positive(&sbi->s_extent_cache_cnt);
1033 : 73535 : trace_ext4_es_shrink_enter(sbi->s_sb, nr_to_scan, ret);
1034 : :
1035 [ - + ]: 73535 : if (!nr_to_scan)
1036 : 0 : return ret;
1037 : :
1038 : 73535 : nr_shrunk = __ext4_es_shrink(sbi, nr_to_scan, NULL);
1039 : :
1040 : 73535 : trace_ext4_es_shrink_exit(sbi->s_sb, nr_shrunk, ret);
1041 : 73535 : return nr_shrunk;
1042 : : }
1043 : :
1044 : 0 : void ext4_es_register_shrinker(struct ext4_sb_info *sbi)
1045 : : {
1046 : 0 : INIT_LIST_HEAD(&sbi->s_es_lru);
1047 : 0 : spin_lock_init(&sbi->s_es_lru_lock);
1048 : 0 : sbi->s_es_last_sorted = 0;
1049 : 0 : sbi->s_es_shrinker.scan_objects = ext4_es_scan;
1050 : 0 : sbi->s_es_shrinker.count_objects = ext4_es_count;
1051 : 0 : sbi->s_es_shrinker.seeks = DEFAULT_SEEKS;
1052 : 0 : register_shrinker(&sbi->s_es_shrinker);
1053 : 0 : }
1054 : :
1055 : 0 : void ext4_es_unregister_shrinker(struct ext4_sb_info *sbi)
1056 : : {
1057 : 0 : unregister_shrinker(&sbi->s_es_shrinker);
1058 : 0 : }
1059 : :
1060 : 0 : void ext4_es_lru_add(struct inode *inode)
1061 : : {
1062 : : struct ext4_inode_info *ei = EXT4_I(inode);
1063 : 4592981 : struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
1064 : :
1065 : 4592981 : ei->i_touch_when = jiffies;
1066 : :
1067 [ + + ]: 4592981 : if (!list_empty(&ei->i_es_lru))
1068 : 4592982 : return;
1069 : :
1070 : : spin_lock(&sbi->s_es_lru_lock);
1071 [ + - ]: 97187 : if (list_empty(&ei->i_es_lru))
1072 : 97187 : list_add_tail(&ei->i_es_lru, &sbi->s_es_lru);
1073 : : spin_unlock(&sbi->s_es_lru_lock);
1074 : : }
1075 : :
1076 : 0 : void ext4_es_lru_del(struct inode *inode)
1077 : : {
1078 : : struct ext4_inode_info *ei = EXT4_I(inode);
1079 : 476193 : struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
1080 : :
1081 : : spin_lock(&sbi->s_es_lru_lock);
1082 [ + + ]: 476193 : if (!list_empty(&ei->i_es_lru))
1083 : : list_del_init(&ei->i_es_lru);
1084 : : spin_unlock(&sbi->s_es_lru_lock);
1085 : 476193 : }
1086 : :
1087 : 0 : static int __es_try_to_reclaim_extents(struct ext4_inode_info *ei,
1088 : : int nr_to_scan)
1089 : : {
1090 : 13369 : struct inode *inode = &ei->vfs_inode;
1091 : : struct ext4_es_tree *tree = &ei->i_es_tree;
1092 : : struct rb_node *node;
1093 : 13518 : struct extent_status *es;
1094 : : unsigned long nr_shrunk = 0;
1095 : : static DEFINE_RATELIMIT_STATE(_rs, DEFAULT_RATELIMIT_INTERVAL,
1096 : : DEFAULT_RATELIMIT_BURST);
1097 : :
1098 [ + - ]: 13369 : if (ei->i_es_lru_nr == 0)
1099 : : return 0;
1100 : :
1101 [ - + # # ]: 13369 : if (ext4_test_inode_state(inode, EXT4_STATE_EXT_PRECACHED) &&
1102 : 0 : __ratelimit(&_rs))
1103 : 0 : ext4_warning(inode->i_sb, "forced shrink of precached extents");
1104 : :
1105 : 13369 : node = rb_first(&tree->root);
1106 [ + + ]: 40151 : while (node != NULL) {
1107 : : es = rb_entry(node, struct extent_status, rb_node);
1108 : 13518 : node = rb_next(&es->rb_node);
1109 : : /*
1110 : : * We can't reclaim delayed extent from status tree because
1111 : : * fiemap, bigallic, and seek_data/hole need to use it.
1112 : : */
1113 [ + - ]: 13518 : if (!ext4_es_is_delayed(es)) {
1114 : 13518 : rb_erase(&es->rb_node, &tree->root);
1115 : 13518 : ext4_es_free_extent(inode, es);
1116 : 13518 : nr_shrunk++;
1117 [ + + ]: 13518 : if (--nr_to_scan == 0)
1118 : : break;
1119 : : }
1120 : : }
1121 : 13369 : tree->cache_es = NULL;
1122 : 13369 : return nr_shrunk;
1123 : : }
|
