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