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