blob: 2b439afafe136d4668846fb761fa599c2f4ee984 [file] [log] [blame]
Greg Kroah-Hartmanb2441312017-11-01 15:07:57 +01001// SPDX-License-Identifier: GPL-2.0
Zheng Liu654598b2012-11-08 21:57:20 -05002/*
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 */
Zheng Liud3922a72013-07-01 08:12:37 -040013#include <linux/list_sort.h>
Zheng Liueb68d0e2014-09-01 22:26:49 -040014#include <linux/proc_fs.h>
15#include <linux/seq_file.h>
Zheng Liu654598b2012-11-08 21:57:20 -050016#include "ext4.h"
Zheng Liu654598b2012-11-08 21:57:20 -050017
Zheng Liu992e9fd2012-11-08 21:57:33 -050018#include <trace/events/ext4.h>
19
Zheng Liu654598b2012-11-08 21:57:20 -050020/*
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
Zheng Liu06b0c882013-02-18 00:26:51 -050027 * extent tree, whose goal is only track delayed extents in memory to
Zheng Liu654598b2012-11-08 21:57:20 -050028 * simplify the implementation of fiemap and bigalloc, and introduce
29 * lseek SEEK_DATA/SEEK_HOLE support. That is why it is still called
Zheng Liu06b0c882013-02-18 00:26:51 -050030 * delay extent tree at the first commit. But for better understand
31 * what it does, it has been rename to extent status tree.
Zheng Liu654598b2012-11-08 21:57:20 -050032 *
Zheng Liu06b0c882013-02-18 00:26:51 -050033 * 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
Zheng Liu654598b2012-11-08 21:57:20 -050037 * 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.
Zheng Liu06b0c882013-02-18 00:26:51 -050042 *
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.
Zheng Liu654598b2012-11-08 21:57:20 -050055 */
56
57/*
Zheng Liu06b0c882013-02-18 00:26:51 -050058 * Extent status tree implementation for ext4.
Zheng Liu654598b2012-11-08 21:57:20 -050059 *
60 *
61 * ==========================================================================
Zheng Liu06b0c882013-02-18 00:26:51 -050062 * Extent status tree tracks all extent status.
Zheng Liu654598b2012-11-08 21:57:20 -050063 *
Zheng Liu06b0c882013-02-18 00:26:51 -050064 * 1. Why we need to implement extent status tree?
Zheng Liu654598b2012-11-08 21:57:20 -050065 *
Zheng Liu06b0c882013-02-18 00:26:51 -050066 * Without extent status tree, ext4 identifies a delayed extent by looking
Zheng Liu654598b2012-11-08 21:57:20 -050067 * up page cache, this has several deficiencies - complicated, buggy,
68 * and inefficient code.
69 *
Zheng Liu06b0c882013-02-18 00:26:51 -050070 * 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.
Zheng Liu654598b2012-11-08 21:57:20 -050072 *
Zheng Liu06b0c882013-02-18 00:26:51 -050073 * Let us have a look at how they do without extent status tree.
Zheng Liu654598b2012-11-08 21:57:20 -050074 * -- 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 *
Zheng Liu654598b2012-11-08 21:57:20 -050085 * -- 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
Masahiro Yamada3f8b6fb2017-02-27 14:29:25 -080088 * time consuming.
Zheng Liu654598b2012-11-08 21:57:20 -050089 *
Zheng Liu06b0c882013-02-18 00:26:51 -050090 * With extent status tree implementation, FIEMAP, SEEK_HOLE/DATA,
Zheng Liu654598b2012-11-08 21:57:20 -050091 * 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
Zheng Liu06b0c882013-02-18 00:26:51 -050093 * not by searching the extent tree.
Zheng Liu654598b2012-11-08 21:57:20 -050094 *
95 *
96 * ==========================================================================
Zheng Liu06b0c882013-02-18 00:26:51 -050097 * 2. Ext4 extent status tree impelmentation
Zheng Liu654598b2012-11-08 21:57:20 -050098 *
Zheng Liu06b0c882013-02-18 00:26:51 -050099 * -- 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.
Zheng Liu654598b2012-11-08 21:57:20 -0500105 *
Zheng Liu06b0c882013-02-18 00:26:51 -0500106 * -- 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.
Zheng Liu654598b2012-11-08 21:57:20 -0500110 *
Zheng Liu06b0c882013-02-18 00:26:51 -0500111 * -- 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.
Zheng Liu654598b2012-11-08 21:57:20 -0500114 *
Zheng Liu06b0c882013-02-18 00:26:51 -0500115 * -- 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.
Zheng Liu654598b2012-11-08 21:57:20 -0500122 *
123 *
124 * ==========================================================================
Zheng Liu06b0c882013-02-18 00:26:51 -0500125 * 3. Performance analysis
126 *
Zheng Liu654598b2012-11-08 21:57:20 -0500127 * -- 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
Zheng Liu654598b2012-11-08 21:57:20 -0500138 *
Zheng Liu06b0c882013-02-18 00:26:51 -0500139 * -- Refactor delayed space reservation
Zheng Liu654598b2012-11-08 21:57:20 -0500140 *
141 * -- Extent-level locking
142 */
143
144static struct kmem_cache *ext4_es_cachep;
Eric Whitney1dc0aa42018-10-01 14:17:41 -0400145static struct kmem_cache *ext4_pending_cachep;
Zheng Liu654598b2012-11-08 21:57:20 -0500146
Zheng Liubdedbb72013-02-18 00:32:02 -0500147static int __es_insert_extent(struct inode *inode, struct extent_status *newes);
148static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
Zheng Liu06b0c882013-02-18 00:26:51 -0500149 ext4_lblk_t end);
Jan Karadd475922014-11-25 11:51:23 -0500150static int es_reclaim_extents(struct ext4_inode_info *ei, int *nr_to_scan);
Zheng Liuedaa53c2014-11-25 11:45:37 -0500151static int __es_shrink(struct ext4_sb_info *sbi, int nr_to_scan,
152 struct ext4_inode_info *locked_ei);
Eric Whitneyb6bf9172018-10-01 14:24:08 -0400153static void __revise_pending(struct inode *inode, ext4_lblk_t lblk,
154 ext4_lblk_t len);
Zheng Liu06b0c882013-02-18 00:26:51 -0500155
Zheng Liu654598b2012-11-08 21:57:20 -0500156int __init ext4_init_es(void)
157{
Theodore Ts'o24630772013-02-28 23:58:56 -0500158 ext4_es_cachep = kmem_cache_create("ext4_extent_status",
159 sizeof(struct extent_status),
160 0, (SLAB_RECLAIM_ACCOUNT), NULL);
Zheng Liu654598b2012-11-08 21:57:20 -0500161 if (ext4_es_cachep == NULL)
162 return -ENOMEM;
163 return 0;
164}
165
166void ext4_exit_es(void)
167{
Sean Fu21c580d2018-05-20 22:44:13 -0400168 kmem_cache_destroy(ext4_es_cachep);
Zheng Liu654598b2012-11-08 21:57:20 -0500169}
170
171void ext4_es_init_tree(struct ext4_es_tree *tree)
172{
173 tree->root = RB_ROOT;
174 tree->cache_es = NULL;
175}
176
177#ifdef ES_DEBUG__
178static 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);
Eric Whitneyce140cd2014-02-20 16:09:12 -0500189 printk(KERN_DEBUG " [%u/%u) %llu %x",
Zheng Liufdc02122013-02-18 00:26:51 -0500190 es->es_lblk, es->es_len,
191 ext4_es_pblock(es), ext4_es_status(es));
Zheng Liu654598b2012-11-08 21:57:20 -0500192 node = rb_next(node);
193 }
194 printk(KERN_DEBUG "\n");
195}
196#else
197#define ext4_es_print_tree(inode)
198#endif
199
Zheng Liu06b0c882013-02-18 00:26:51 -0500200static inline ext4_lblk_t ext4_es_end(struct extent_status *es)
Zheng Liu654598b2012-11-08 21:57:20 -0500201{
Zheng Liu06b0c882013-02-18 00:26:51 -0500202 BUG_ON(es->es_lblk + es->es_len < es->es_lblk);
203 return es->es_lblk + es->es_len - 1;
Zheng Liu654598b2012-11-08 21:57:20 -0500204}
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 */
210static struct extent_status *__es_tree_search(struct rb_root *root,
Zheng Liu06b0c882013-02-18 00:26:51 -0500211 ext4_lblk_t lblk)
Zheng Liu654598b2012-11-08 21:57:20 -0500212{
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);
Zheng Liu06b0c882013-02-18 00:26:51 -0500218 if (lblk < es->es_lblk)
Zheng Liu654598b2012-11-08 21:57:20 -0500219 node = node->rb_left;
Zheng Liu06b0c882013-02-18 00:26:51 -0500220 else if (lblk > ext4_es_end(es))
Zheng Liu654598b2012-11-08 21:57:20 -0500221 node = node->rb_right;
222 else
223 return es;
224 }
225
Zheng Liu06b0c882013-02-18 00:26:51 -0500226 if (es && lblk < es->es_lblk)
Zheng Liu654598b2012-11-08 21:57:20 -0500227 return es;
228
Zheng Liu06b0c882013-02-18 00:26:51 -0500229 if (es && lblk > ext4_es_end(es)) {
Zheng Liu654598b2012-11-08 21:57:20 -0500230 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/*
Eric Whitneyad431022018-10-01 14:10:39 -0400239 * 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
Zheng Liu654598b2012-11-08 21:57:20 -0500242 *
Eric Whitneyad431022018-10-01 14:10:39 -0400243 * @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.
Zheng Liu654598b2012-11-08 21:57:20 -0500255 */
Eric Whitneyad431022018-10-01 14:10:39 -0400256static 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)
Zheng Liu654598b2012-11-08 21:57:20 -0500260{
261 struct ext4_es_tree *tree = NULL;
262 struct extent_status *es1 = NULL;
263 struct rb_node *node;
Zheng Liu654598b2012-11-08 21:57:20 -0500264
Eric Whitneyad431022018-10-01 14:10:39 -0400265 WARN_ON(es == NULL);
266 WARN_ON(end < lblk);
Zheng Liu992e9fd2012-11-08 21:57:33 -0500267
Zheng Liu654598b2012-11-08 21:57:20 -0500268 tree = &EXT4_I(inode)->i_es_tree;
269
Eric Whitneyad431022018-10-01 14:10:39 -0400270 /* see if the extent has been cached */
Zheng Liube401362013-02-18 00:27:26 -0500271 es->es_lblk = es->es_len = es->es_pblk = 0;
Zheng Liu654598b2012-11-08 21:57:20 -0500272 if (tree->cache_es) {
273 es1 = tree->cache_es;
Zheng Liube401362013-02-18 00:27:26 -0500274 if (in_range(lblk, es1->es_lblk, es1->es_len)) {
Theodore Ts'o3be78c72013-08-16 21:22:41 -0400275 es_debug("%u cached by [%u/%u) %llu %x\n",
Zheng Liube401362013-02-18 00:27:26 -0500276 lblk, es1->es_lblk, es1->es_len,
Zheng Liufdc02122013-02-18 00:26:51 -0500277 ext4_es_pblock(es1), ext4_es_status(es1));
Zheng Liu654598b2012-11-08 21:57:20 -0500278 goto out;
279 }
280 }
281
Zheng Liube401362013-02-18 00:27:26 -0500282 es1 = __es_tree_search(&tree->root, lblk);
Zheng Liu654598b2012-11-08 21:57:20 -0500283
284out:
Eric Whitneyad431022018-10-01 14:10:39 -0400285 if (es1 && !matching_fn(es1)) {
Zheng Liube401362013-02-18 00:27:26 -0500286 while ((node = rb_next(&es1->rb_node)) != NULL) {
287 es1 = rb_entry(node, struct extent_status, rb_node);
Yan, Zhenge30b5dc2013-05-03 02:15:52 -0400288 if (es1->es_lblk > end) {
289 es1 = NULL;
290 break;
291 }
Eric Whitneyad431022018-10-01 14:10:39 -0400292 if (matching_fn(es1))
Zheng Liube401362013-02-18 00:27:26 -0500293 break;
294 }
295 }
296
Eric Whitneyad431022018-10-01 14:10:39 -0400297 if (es1 && matching_fn(es1)) {
Zheng Liu654598b2012-11-08 21:57:20 -0500298 tree->cache_es = es1;
Zheng Liu06b0c882013-02-18 00:26:51 -0500299 es->es_lblk = es1->es_lblk;
300 es->es_len = es1->es_len;
Zheng Liufdc02122013-02-18 00:26:51 -0500301 es->es_pblk = es1->es_pblk;
Zheng Liu654598b2012-11-08 21:57:20 -0500302 }
303
Eric Whitneyad431022018-10-01 14:10:39 -0400304}
305
306/*
307 * Locking for __es_find_extent_range() for external use
308 */
309void 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 trace_ext4_es_find_extent_range_enter(inode, lblk);
315
316 read_lock(&EXT4_I(inode)->i_es_lock);
317 __es_find_extent_range(inode, matching_fn, lblk, end, es);
Zheng Liu654598b2012-11-08 21:57:20 -0500318 read_unlock(&EXT4_I(inode)->i_es_lock);
Zheng Liu992e9fd2012-11-08 21:57:33 -0500319
Eric Whitneyad431022018-10-01 14:10:39 -0400320 trace_ext4_es_find_extent_range_exit(inode, es);
321}
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 */
338static 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 struct extent_status es;
343
344 __es_find_extent_range(inode, matching_fn, start, end, &es);
345 if (es.es_len == 0)
346 return false; /* no matching extent in the tree */
347 else if (es.es_lblk <= start &&
348 start < es.es_lblk + es.es_len)
349 return true;
350 else if (start <= es.es_lblk && es.es_lblk <= end)
351 return true;
352 else
353 return false;
354}
355/*
356 * Locking for __es_scan_range() for external use
357 */
358bool 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 bool ret;
363
364 read_lock(&EXT4_I(inode)->i_es_lock);
365 ret = __es_scan_range(inode, matching_fn, lblk, end);
366 read_unlock(&EXT4_I(inode)->i_es_lock);
367
368 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 */
385static bool __es_scan_clu(struct inode *inode,
386 int (*matching_fn)(struct extent_status *es),
387 ext4_lblk_t lblk)
388{
389 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
390 ext4_lblk_t lblk_start, lblk_end;
391
392 lblk_start = EXT4_LBLK_CMASK(sbi, lblk);
393 lblk_end = lblk_start + sbi->s_cluster_ratio - 1;
394
395 return __es_scan_range(inode, matching_fn, lblk_start, lblk_end);
396}
397
398/*
399 * Locking for __es_scan_clu() for external use
400 */
401bool ext4_es_scan_clu(struct inode *inode,
402 int (*matching_fn)(struct extent_status *es),
403 ext4_lblk_t lblk)
404{
405 bool ret;
406
407 read_lock(&EXT4_I(inode)->i_es_lock);
408 ret = __es_scan_clu(inode, matching_fn, lblk);
409 read_unlock(&EXT4_I(inode)->i_es_lock);
410
411 return ret;
Zheng Liu654598b2012-11-08 21:57:20 -0500412}
413
Jan Karab0dea4c2014-11-25 11:49:25 -0500414static void ext4_es_list_add(struct inode *inode)
Zheng Liuedaa53c2014-11-25 11:45:37 -0500415{
416 struct ext4_inode_info *ei = EXT4_I(inode);
417 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
418
419 if (!list_empty(&ei->i_es_list))
420 return;
421
422 spin_lock(&sbi->s_es_lock);
423 if (list_empty(&ei->i_es_list)) {
424 list_add_tail(&ei->i_es_list, &sbi->s_es_list);
425 sbi->s_es_nr_inode++;
426 }
427 spin_unlock(&sbi->s_es_lock);
428}
429
Jan Karab0dea4c2014-11-25 11:49:25 -0500430static void ext4_es_list_del(struct inode *inode)
Zheng Liuedaa53c2014-11-25 11:45:37 -0500431{
432 struct ext4_inode_info *ei = EXT4_I(inode);
433 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
434
435 spin_lock(&sbi->s_es_lock);
436 if (!list_empty(&ei->i_es_list)) {
437 list_del_init(&ei->i_es_list);
438 sbi->s_es_nr_inode--;
439 WARN_ON_ONCE(sbi->s_es_nr_inode < 0);
440 }
441 spin_unlock(&sbi->s_es_lock);
442}
443
Zheng Liu654598b2012-11-08 21:57:20 -0500444static struct extent_status *
Zheng Liubdedbb72013-02-18 00:32:02 -0500445ext4_es_alloc_extent(struct inode *inode, ext4_lblk_t lblk, ext4_lblk_t len,
446 ext4_fsblk_t pblk)
Zheng Liu654598b2012-11-08 21:57:20 -0500447{
448 struct extent_status *es;
449 es = kmem_cache_alloc(ext4_es_cachep, GFP_ATOMIC);
450 if (es == NULL)
451 return NULL;
Zheng Liu06b0c882013-02-18 00:26:51 -0500452 es->es_lblk = lblk;
453 es->es_len = len;
Zheng Liufdc02122013-02-18 00:26:51 -0500454 es->es_pblk = pblk;
Zheng Liu74cd15c2013-02-18 00:32:55 -0500455
456 /*
457 * We don't count delayed extent because we never try to reclaim them
458 */
Theodore Ts'o24630772013-02-28 23:58:56 -0500459 if (!ext4_es_is_delayed(es)) {
Jan Karab0dea4c2014-11-25 11:49:25 -0500460 if (!EXT4_I(inode)->i_es_shk_nr++)
461 ext4_es_list_add(inode);
Zheng Liueb68d0e2014-09-01 22:26:49 -0400462 percpu_counter_inc(&EXT4_SB(inode->i_sb)->
Zheng Liuedaa53c2014-11-25 11:45:37 -0500463 s_es_stats.es_stats_shk_cnt);
Theodore Ts'o24630772013-02-28 23:58:56 -0500464 }
Zheng Liu74cd15c2013-02-18 00:32:55 -0500465
Zheng Liueb68d0e2014-09-01 22:26:49 -0400466 EXT4_I(inode)->i_es_all_nr++;
467 percpu_counter_inc(&EXT4_SB(inode->i_sb)->s_es_stats.es_stats_all_cnt);
468
Zheng Liu654598b2012-11-08 21:57:20 -0500469 return es;
470}
471
Zheng Liubdedbb72013-02-18 00:32:02 -0500472static void ext4_es_free_extent(struct inode *inode, struct extent_status *es)
Zheng Liu654598b2012-11-08 21:57:20 -0500473{
Zheng Liueb68d0e2014-09-01 22:26:49 -0400474 EXT4_I(inode)->i_es_all_nr--;
475 percpu_counter_dec(&EXT4_SB(inode->i_sb)->s_es_stats.es_stats_all_cnt);
476
Zheng Liuedaa53c2014-11-25 11:45:37 -0500477 /* Decrease the shrink counter when this es is not delayed */
Zheng Liu74cd15c2013-02-18 00:32:55 -0500478 if (!ext4_es_is_delayed(es)) {
Zheng Liuedaa53c2014-11-25 11:45:37 -0500479 BUG_ON(EXT4_I(inode)->i_es_shk_nr == 0);
Jan Karab0dea4c2014-11-25 11:49:25 -0500480 if (!--EXT4_I(inode)->i_es_shk_nr)
481 ext4_es_list_del(inode);
Zheng Liueb68d0e2014-09-01 22:26:49 -0400482 percpu_counter_dec(&EXT4_SB(inode->i_sb)->
Zheng Liuedaa53c2014-11-25 11:45:37 -0500483 s_es_stats.es_stats_shk_cnt);
Zheng Liu74cd15c2013-02-18 00:32:55 -0500484 }
485
Zheng Liu654598b2012-11-08 21:57:20 -0500486 kmem_cache_free(ext4_es_cachep, es);
487}
488
Zheng Liu06b0c882013-02-18 00:26:51 -0500489/*
490 * Check whether or not two extents can be merged
491 * Condition:
492 * - logical block number is contiguous
Zheng Liufdc02122013-02-18 00:26:51 -0500493 * - physical block number is contiguous
494 * - status is equal
Zheng Liu06b0c882013-02-18 00:26:51 -0500495 */
496static int ext4_es_can_be_merged(struct extent_status *es1,
497 struct extent_status *es2)
498{
Jan Kara2be12de2014-11-25 11:55:24 -0500499 if (ext4_es_type(es1) != ext4_es_type(es2))
Zheng Liufdc02122013-02-18 00:26:51 -0500500 return 0;
501
Lukas Czerner0baaea62014-05-12 22:21:43 -0400502 if (((__u64) es1->es_len) + es2->es_len > EXT_MAX_BLOCKS) {
503 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 WARN_ON(1);
Zheng Liufdc02122013-02-18 00:26:51 -0500508 return 0;
Lukas Czerner0baaea62014-05-12 22:21:43 -0400509 }
Zheng Liufdc02122013-02-18 00:26:51 -0500510
Zheng Liubd384362013-03-10 20:48:59 -0400511 if (((__u64) es1->es_lblk) + es1->es_len != es2->es_lblk)
512 return 0;
513
514 if ((ext4_es_is_written(es1) || ext4_es_is_unwritten(es1)) &&
515 (ext4_es_pblock(es1) + es1->es_len == ext4_es_pblock(es2)))
516 return 1;
517
518 if (ext4_es_is_hole(es1))
519 return 1;
520
521 /* we need to check delayed extent is without unwritten status */
522 if (ext4_es_is_delayed(es1) && !ext4_es_is_unwritten(es1))
523 return 1;
524
525 return 0;
Zheng Liu06b0c882013-02-18 00:26:51 -0500526}
527
Zheng Liu654598b2012-11-08 21:57:20 -0500528static struct extent_status *
Zheng Liubdedbb72013-02-18 00:32:02 -0500529ext4_es_try_to_merge_left(struct inode *inode, struct extent_status *es)
Zheng Liu654598b2012-11-08 21:57:20 -0500530{
Zheng Liubdedbb72013-02-18 00:32:02 -0500531 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
Zheng Liu654598b2012-11-08 21:57:20 -0500532 struct extent_status *es1;
533 struct rb_node *node;
534
535 node = rb_prev(&es->rb_node);
536 if (!node)
537 return es;
538
539 es1 = rb_entry(node, struct extent_status, rb_node);
Zheng Liu06b0c882013-02-18 00:26:51 -0500540 if (ext4_es_can_be_merged(es1, es)) {
541 es1->es_len += es->es_len;
Jan Kara2be12de2014-11-25 11:55:24 -0500542 if (ext4_es_is_referenced(es))
543 ext4_es_set_referenced(es1);
Zheng Liu654598b2012-11-08 21:57:20 -0500544 rb_erase(&es->rb_node, &tree->root);
Zheng Liubdedbb72013-02-18 00:32:02 -0500545 ext4_es_free_extent(inode, es);
Zheng Liu654598b2012-11-08 21:57:20 -0500546 es = es1;
547 }
548
549 return es;
550}
551
552static struct extent_status *
Zheng Liubdedbb72013-02-18 00:32:02 -0500553ext4_es_try_to_merge_right(struct inode *inode, struct extent_status *es)
Zheng Liu654598b2012-11-08 21:57:20 -0500554{
Zheng Liubdedbb72013-02-18 00:32:02 -0500555 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
Zheng Liu654598b2012-11-08 21:57:20 -0500556 struct extent_status *es1;
557 struct rb_node *node;
558
559 node = rb_next(&es->rb_node);
560 if (!node)
561 return es;
562
563 es1 = rb_entry(node, struct extent_status, rb_node);
Zheng Liu06b0c882013-02-18 00:26:51 -0500564 if (ext4_es_can_be_merged(es, es1)) {
565 es->es_len += es1->es_len;
Jan Kara2be12de2014-11-25 11:55:24 -0500566 if (ext4_es_is_referenced(es1))
567 ext4_es_set_referenced(es);
Zheng Liu654598b2012-11-08 21:57:20 -0500568 rb_erase(node, &tree->root);
Zheng Liubdedbb72013-02-18 00:32:02 -0500569 ext4_es_free_extent(inode, es1);
Zheng Liu654598b2012-11-08 21:57:20 -0500570 }
571
572 return es;
573}
574
Dmitry Monakhov921f2662013-03-10 21:01:03 -0400575#ifdef ES_AGGRESSIVE_TEST
Zheng Liud7b2a002013-08-28 14:47:06 -0400576#include "ext4_extents.h" /* Needed when ES_AGGRESSIVE_TEST is defined */
577
Dmitry Monakhov921f2662013-03-10 21:01:03 -0400578static 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
Theodore Ts'oed8a1a72014-09-01 14:43:09 -0400588 path = ext4_find_extent(inode, es->es_lblk, NULL, EXT4_EX_NOCACHE);
Dmitry Monakhov921f2662013-03-10 21:01:03 -0400589 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
Lukas Czerner556615d2014-04-20 23:45:47 -0400601 ee_status = ext4_ext_is_unwritten(ex) ? 1 : 0;
Dmitry Monakhov921f2662013-03-10 21:01:03 -0400602 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)) {
Theodore Ts'obdafe422013-07-13 00:40:31 -0400610 pr_warn("ES insert assertion failed for "
Dmitry Monakhov921f2662013-03-10 21:01:03 -0400611 "inode: %lu we can find an extent "
612 "at block [%d/%d/%llu/%c], but we "
Eric Whitneyce140cd2014-02-20 16:09:12 -0500613 "want to add a delayed/hole extent "
614 "[%d/%d/%llu/%x]\n",
Dmitry Monakhov921f2662013-03-10 21:01:03 -0400615 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) {
Theodore Ts'obdafe422013-07-13 00:40:31 -0400629 pr_warn("ES insert assertion failed for inode: %lu "
Dmitry Monakhov921f2662013-03-10 21:01:03 -0400630 "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) {
Theodore Ts'obdafe422013-07-13 00:40:31 -0400639 pr_warn("ES insert assertion failed for inode: %lu "
Dmitry Monakhov921f2662013-03-10 21:01:03 -0400640 "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)) {
Theodore Ts'obdafe422013-07-13 00:40:31 -0400652 pr_warn("ES insert assertion failed for inode: %lu "
Dmitry Monakhov921f2662013-03-10 21:01:03 -0400653 "can't find an extent at block %d but we want "
Eric Whitneyce140cd2014-02-20 16:09:12 -0500654 "to add a written/unwritten extent "
655 "[%d/%d/%llu/%x]\n", inode->i_ino,
Dmitry Monakhov921f2662013-03-10 21:01:03 -0400656 es->es_lblk, es->es_lblk, es->es_len,
657 ext4_es_pblock(es), ext4_es_status(es));
658 }
659 }
660out:
Theodore Ts'ob7ea89a2014-09-01 14:39:09 -0400661 ext4_ext_drop_refs(path);
662 kfree(path);
Dmitry Monakhov921f2662013-03-10 21:01:03 -0400663}
664
665static 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 */
Theodore Ts'obdafe422013-07-13 00:40:31 -0400688 pr_warn("ES insert assertion failed for inode: %lu "
Dmitry Monakhov921f2662013-03-10 21:01:03 -0400689 "We can find blocks but we want to add a "
Eric Whitneyce140cd2014-02-20 16:09:12 -0500690 "delayed/hole extent [%d/%d/%llu/%x]\n",
Dmitry Monakhov921f2662013-03-10 21:01:03 -0400691 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) {
Theodore Ts'obdafe422013-07-13 00:40:31 -0400696 pr_warn("ES insert assertion failed for "
Dmitry Monakhov921f2662013-03-10 21:01:03 -0400697 "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)) {
Theodore Ts'obdafe422013-07-13 00:40:31 -0400702 pr_warn("ES insert assertion failed for "
Dmitry Monakhov921f2662013-03-10 21:01:03 -0400703 "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_ON(1);
715 }
716 } else if (retval == 0) {
717 if (ext4_es_is_written(es)) {
Theodore Ts'obdafe422013-07-13 00:40:31 -0400718 pr_warn("ES insert assertion failed for inode: %lu "
Dmitry Monakhov921f2662013-03-10 21:01:03 -0400719 "We can't find the block but we want to add "
Eric Whitneyce140cd2014-02-20 16:09:12 -0500720 "a written extent [%d/%d/%llu/%x]\n",
Dmitry Monakhov921f2662013-03-10 21:01:03 -0400721 inode->i_ino, es->es_lblk, es->es_len,
722 ext4_es_pblock(es), ext4_es_status(es));
723 return;
724 }
725 }
726}
727
728static 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
742static inline void ext4_es_insert_extent_check(struct inode *inode,
743 struct extent_status *es)
744{
745}
746#endif
747
Zheng Liubdedbb72013-02-18 00:32:02 -0500748static int __es_insert_extent(struct inode *inode, struct extent_status *newes)
Zheng Liu654598b2012-11-08 21:57:20 -0500749{
Zheng Liubdedbb72013-02-18 00:32:02 -0500750 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
Zheng Liu654598b2012-11-08 21:57:20 -0500751 struct rb_node **p = &tree->root.rb_node;
752 struct rb_node *parent = NULL;
753 struct extent_status *es;
Zheng Liu654598b2012-11-08 21:57:20 -0500754
755 while (*p) {
756 parent = *p;
757 es = rb_entry(parent, struct extent_status, rb_node);
758
Zheng Liu06b0c882013-02-18 00:26:51 -0500759 if (newes->es_lblk < es->es_lblk) {
760 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 es->es_lblk = newes->es_lblk;
766 es->es_len += newes->es_len;
Zheng Liufdc02122013-02-18 00:26:51 -0500767 if (ext4_es_is_written(es) ||
768 ext4_es_is_unwritten(es))
769 ext4_es_store_pblock(es,
770 newes->es_pblk);
Zheng Liubdedbb72013-02-18 00:32:02 -0500771 es = ext4_es_try_to_merge_left(inode, es);
Zheng Liu654598b2012-11-08 21:57:20 -0500772 goto out;
773 }
774 p = &(*p)->rb_left;
Zheng Liu06b0c882013-02-18 00:26:51 -0500775 } else if (newes->es_lblk > ext4_es_end(es)) {
776 if (ext4_es_can_be_merged(es, newes)) {
777 es->es_len += newes->es_len;
Zheng Liubdedbb72013-02-18 00:32:02 -0500778 es = ext4_es_try_to_merge_right(inode, es);
Zheng Liu654598b2012-11-08 21:57:20 -0500779 goto out;
780 }
781 p = &(*p)->rb_right;
782 } else {
Zheng Liu06b0c882013-02-18 00:26:51 -0500783 BUG_ON(1);
784 return -EINVAL;
Zheng Liu654598b2012-11-08 21:57:20 -0500785 }
786 }
787
Zheng Liubdedbb72013-02-18 00:32:02 -0500788 es = ext4_es_alloc_extent(inode, newes->es_lblk, newes->es_len,
Zheng Liufdc02122013-02-18 00:26:51 -0500789 newes->es_pblk);
Zheng Liu654598b2012-11-08 21:57:20 -0500790 if (!es)
791 return -ENOMEM;
792 rb_link_node(&es->rb_node, parent, p);
793 rb_insert_color(&es->rb_node, &tree->root);
794
795out:
796 tree->cache_es = es;
797 return 0;
798}
799
800/*
Theodore Ts'obdafe422013-07-13 00:40:31 -0400801 * ext4_es_insert_extent() adds information to an inode's extent
802 * status tree.
Zheng Liu654598b2012-11-08 21:57:20 -0500803 *
804 * Return 0 on success, error code on failure.
805 */
Zheng Liu06b0c882013-02-18 00:26:51 -0500806int ext4_es_insert_extent(struct inode *inode, ext4_lblk_t lblk,
Zheng Liufdc02122013-02-18 00:26:51 -0500807 ext4_lblk_t len, ext4_fsblk_t pblk,
Theodore Ts'o3be78c72013-08-16 21:22:41 -0400808 unsigned int status)
Zheng Liu654598b2012-11-08 21:57:20 -0500809{
Zheng Liu06b0c882013-02-18 00:26:51 -0500810 struct extent_status newes;
811 ext4_lblk_t end = lblk + len - 1;
Zheng Liu654598b2012-11-08 21:57:20 -0500812 int err = 0;
Eric Whitneyb6bf9172018-10-01 14:24:08 -0400813 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
Zheng Liu654598b2012-11-08 21:57:20 -0500814
Theodore Ts'o3be78c72013-08-16 21:22:41 -0400815 es_debug("add [%u/%u) %llu %x to extent status tree of inode %lu\n",
Zheng Liufdc02122013-02-18 00:26:51 -0500816 lblk, len, pblk, status, inode->i_ino);
Zheng Liu06b0c882013-02-18 00:26:51 -0500817
Eryu Guand4381472013-02-22 15:27:47 -0500818 if (!len)
819 return 0;
820
Zheng Liu06b0c882013-02-18 00:26:51 -0500821 BUG_ON(end < lblk);
822
Lukas Czernerd2dc3172015-05-02 21:36:55 -0400823 if ((status & EXTENT_STATUS_DELAYED) &&
824 (status & EXTENT_STATUS_WRITTEN)) {
825 ext4_warning(inode->i_sb, "Inserting extent [%u/%u] as "
826 " delayed and written which can potentially "
Jakub Wilk8d2ae1c2016-04-27 01:11:21 -0400827 " cause data loss.", lblk, len);
Lukas Czernerd2dc3172015-05-02 21:36:55 -0400828 WARN_ON(1);
829 }
830
Zheng Liu06b0c882013-02-18 00:26:51 -0500831 newes.es_lblk = lblk;
832 newes.es_len = len;
Theodore Ts'o9a6633b2014-02-19 20:15:15 -0500833 ext4_es_store_pblock_status(&newes, pblk, status);
Zheng Liufdc02122013-02-18 00:26:51 -0500834 trace_ext4_es_insert_extent(inode, &newes);
Zheng Liu654598b2012-11-08 21:57:20 -0500835
Dmitry Monakhov921f2662013-03-10 21:01:03 -0400836 ext4_es_insert_extent_check(inode, &newes);
837
Zheng Liu654598b2012-11-08 21:57:20 -0500838 write_lock(&EXT4_I(inode)->i_es_lock);
Zheng Liubdedbb72013-02-18 00:32:02 -0500839 err = __es_remove_extent(inode, lblk, end);
Zheng Liu06b0c882013-02-18 00:26:51 -0500840 if (err != 0)
841 goto error;
Theodore Ts'oe15f7422013-07-15 00:12:14 -0400842retry:
Zheng Liubdedbb72013-02-18 00:32:02 -0500843 err = __es_insert_extent(inode, &newes);
Zheng Liuedaa53c2014-11-25 11:45:37 -0500844 if (err == -ENOMEM && __es_shrink(EXT4_SB(inode->i_sb),
Jan Karadd475922014-11-25 11:51:23 -0500845 128, EXT4_I(inode)))
Theodore Ts'oe15f7422013-07-15 00:12:14 -0400846 goto retry;
847 if (err == -ENOMEM && !ext4_es_is_delayed(&newes))
848 err = 0;
Zheng Liu06b0c882013-02-18 00:26:51 -0500849
Eric Whitneyb6bf9172018-10-01 14:24:08 -0400850 if (sbi->s_cluster_ratio > 1 && test_opt(inode->i_sb, DELALLOC) &&
851 (status & EXTENT_STATUS_WRITTEN ||
852 status & EXTENT_STATUS_UNWRITTEN))
853 __revise_pending(inode, lblk, len);
854
Zheng Liu06b0c882013-02-18 00:26:51 -0500855error:
Zheng Liu654598b2012-11-08 21:57:20 -0500856 write_unlock(&EXT4_I(inode)->i_es_lock);
857
858 ext4_es_print_tree(inode);
859
860 return err;
861}
862
Zheng Liud100eef2013-02-18 00:29:59 -0500863/*
Theodore Ts'o107a7bd2013-08-16 21:23:41 -0400864 * 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 */
868void 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 struct extent_status *es;
873 struct extent_status newes;
874 ext4_lblk_t end = lblk + len - 1;
875
876 newes.es_lblk = lblk;
877 newes.es_len = len;
Theodore Ts'o9a6633b2014-02-19 20:15:15 -0500878 ext4_es_store_pblock_status(&newes, pblk, status);
Theodore Ts'o107a7bd2013-08-16 21:23:41 -0400879 trace_ext4_es_cache_extent(inode, &newes);
880
881 if (!len)
882 return;
883
884 BUG_ON(end < lblk);
885
886 write_lock(&EXT4_I(inode)->i_es_lock);
887
888 es = __es_tree_search(&EXT4_I(inode)->i_es_tree.root, lblk);
Theodore Ts'o7869a4a2013-08-16 22:05:14 -0400889 if (!es || es->es_lblk > end)
890 __es_insert_extent(inode, &newes);
Theodore Ts'o107a7bd2013-08-16 21:23:41 -0400891 write_unlock(&EXT4_I(inode)->i_es_lock);
892}
893
894/*
Zheng Liud100eef2013-02-18 00:29:59 -0500895 * 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 */
901int ext4_es_lookup_extent(struct inode *inode, ext4_lblk_t lblk,
902 struct extent_status *es)
903{
904 struct ext4_es_tree *tree;
Zheng Liueb68d0e2014-09-01 22:26:49 -0400905 struct ext4_es_stats *stats;
Zheng Liud100eef2013-02-18 00:29:59 -0500906 struct extent_status *es1 = NULL;
907 struct rb_node *node;
908 int found = 0;
909
910 trace_ext4_es_lookup_extent_enter(inode, lblk);
911 es_debug("lookup extent in block %u\n", lblk);
912
913 tree = &EXT4_I(inode)->i_es_tree;
914 read_lock(&EXT4_I(inode)->i_es_lock);
915
916 /* find extent in cache firstly */
917 es->es_lblk = es->es_len = es->es_pblk = 0;
918 if (tree->cache_es) {
919 es1 = tree->cache_es;
920 if (in_range(lblk, es1->es_lblk, es1->es_len)) {
921 es_debug("%u cached by [%u/%u)\n",
922 lblk, es1->es_lblk, es1->es_len);
923 found = 1;
924 goto out;
925 }
926 }
927
928 node = tree->root.rb_node;
929 while (node) {
930 es1 = rb_entry(node, struct extent_status, rb_node);
931 if (lblk < es1->es_lblk)
932 node = node->rb_left;
933 else if (lblk > ext4_es_end(es1))
934 node = node->rb_right;
935 else {
936 found = 1;
937 break;
938 }
939 }
940
941out:
Zheng Liueb68d0e2014-09-01 22:26:49 -0400942 stats = &EXT4_SB(inode->i_sb)->s_es_stats;
Zheng Liud100eef2013-02-18 00:29:59 -0500943 if (found) {
944 BUG_ON(!es1);
945 es->es_lblk = es1->es_lblk;
946 es->es_len = es1->es_len;
947 es->es_pblk = es1->es_pblk;
Jan Kara87d8a742016-03-09 22:26:55 -0500948 if (!ext4_es_is_referenced(es1))
949 ext4_es_set_referenced(es1);
Zheng Liueb68d0e2014-09-01 22:26:49 -0400950 stats->es_stats_cache_hits++;
951 } else {
952 stats->es_stats_cache_misses++;
Zheng Liud100eef2013-02-18 00:29:59 -0500953 }
954
955 read_unlock(&EXT4_I(inode)->i_es_lock);
956
957 trace_ext4_es_lookup_extent_exit(inode, es, found);
958 return found;
959}
960
Zheng Liubdedbb72013-02-18 00:32:02 -0500961static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
962 ext4_lblk_t end)
Zheng Liu654598b2012-11-08 21:57:20 -0500963{
Zheng Liubdedbb72013-02-18 00:32:02 -0500964 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
Zheng Liu654598b2012-11-08 21:57:20 -0500965 struct rb_node *node;
Zheng Liu654598b2012-11-08 21:57:20 -0500966 struct extent_status *es;
967 struct extent_status orig_es;
Zheng Liu06b0c882013-02-18 00:26:51 -0500968 ext4_lblk_t len1, len2;
Zheng Liufdc02122013-02-18 00:26:51 -0500969 ext4_fsblk_t block;
Theodore Ts'oe15f7422013-07-15 00:12:14 -0400970 int err;
Zheng Liu654598b2012-11-08 21:57:20 -0500971
Theodore Ts'oe15f7422013-07-15 00:12:14 -0400972retry:
973 err = 0;
Zheng Liu06b0c882013-02-18 00:26:51 -0500974 es = __es_tree_search(&tree->root, lblk);
Zheng Liu654598b2012-11-08 21:57:20 -0500975 if (!es)
976 goto out;
Zheng Liu06b0c882013-02-18 00:26:51 -0500977 if (es->es_lblk > end)
Zheng Liu654598b2012-11-08 21:57:20 -0500978 goto out;
979
980 /* Simply invalidate cache_es. */
981 tree->cache_es = NULL;
982
Zheng Liu06b0c882013-02-18 00:26:51 -0500983 orig_es.es_lblk = es->es_lblk;
984 orig_es.es_len = es->es_len;
Zheng Liufdc02122013-02-18 00:26:51 -0500985 orig_es.es_pblk = es->es_pblk;
986
Zheng Liu06b0c882013-02-18 00:26:51 -0500987 len1 = lblk > es->es_lblk ? lblk - es->es_lblk : 0;
988 len2 = ext4_es_end(es) > end ? ext4_es_end(es) - end : 0;
Zheng Liu654598b2012-11-08 21:57:20 -0500989 if (len1 > 0)
Zheng Liu06b0c882013-02-18 00:26:51 -0500990 es->es_len = len1;
Zheng Liu654598b2012-11-08 21:57:20 -0500991 if (len2 > 0) {
992 if (len1 > 0) {
Zheng Liu06b0c882013-02-18 00:26:51 -0500993 struct extent_status newes;
994
995 newes.es_lblk = end + 1;
996 newes.es_len = len2;
Chen Gang666525d2014-04-07 10:18:56 -0400997 block = 0x7FDEADBEEFULL;
Zheng Liufdc02122013-02-18 00:26:51 -0500998 if (ext4_es_is_written(&orig_es) ||
Theodore Ts'o9a6633b2014-02-19 20:15:15 -0500999 ext4_es_is_unwritten(&orig_es))
Zheng Liufdc02122013-02-18 00:26:51 -05001000 block = ext4_es_pblock(&orig_es) +
1001 orig_es.es_len - len2;
Theodore Ts'o9a6633b2014-02-19 20:15:15 -05001002 ext4_es_store_pblock_status(&newes, block,
1003 ext4_es_status(&orig_es));
Zheng Liubdedbb72013-02-18 00:32:02 -05001004 err = __es_insert_extent(inode, &newes);
Zheng Liu654598b2012-11-08 21:57:20 -05001005 if (err) {
Zheng Liu06b0c882013-02-18 00:26:51 -05001006 es->es_lblk = orig_es.es_lblk;
1007 es->es_len = orig_es.es_len;
Theodore Ts'oe15f7422013-07-15 00:12:14 -04001008 if ((err == -ENOMEM) &&
Zheng Liuedaa53c2014-11-25 11:45:37 -05001009 __es_shrink(EXT4_SB(inode->i_sb),
Jan Karadd475922014-11-25 11:51:23 -05001010 128, EXT4_I(inode)))
Theodore Ts'oe15f7422013-07-15 00:12:14 -04001011 goto retry;
Zheng Liu654598b2012-11-08 21:57:20 -05001012 goto out;
1013 }
1014 } else {
Zheng Liu06b0c882013-02-18 00:26:51 -05001015 es->es_lblk = end + 1;
1016 es->es_len = len2;
Zheng Liufdc02122013-02-18 00:26:51 -05001017 if (ext4_es_is_written(es) ||
1018 ext4_es_is_unwritten(es)) {
1019 block = orig_es.es_pblk + orig_es.es_len - len2;
1020 ext4_es_store_pblock(es, block);
1021 }
Zheng Liu654598b2012-11-08 21:57:20 -05001022 }
1023 goto out;
1024 }
1025
1026 if (len1 > 0) {
1027 node = rb_next(&es->rb_node);
1028 if (node)
1029 es = rb_entry(node, struct extent_status, rb_node);
1030 else
1031 es = NULL;
1032 }
1033
Zheng Liu06b0c882013-02-18 00:26:51 -05001034 while (es && ext4_es_end(es) <= end) {
Zheng Liu654598b2012-11-08 21:57:20 -05001035 node = rb_next(&es->rb_node);
1036 rb_erase(&es->rb_node, &tree->root);
Zheng Liubdedbb72013-02-18 00:32:02 -05001037 ext4_es_free_extent(inode, es);
Zheng Liu654598b2012-11-08 21:57:20 -05001038 if (!node) {
1039 es = NULL;
1040 break;
1041 }
1042 es = rb_entry(node, struct extent_status, rb_node);
1043 }
1044
Zheng Liu06b0c882013-02-18 00:26:51 -05001045 if (es && es->es_lblk < end + 1) {
Zheng Liufdc02122013-02-18 00:26:51 -05001046 ext4_lblk_t orig_len = es->es_len;
1047
Zheng Liu06b0c882013-02-18 00:26:51 -05001048 len1 = ext4_es_end(es) - end;
1049 es->es_lblk = end + 1;
1050 es->es_len = len1;
Zheng Liufdc02122013-02-18 00:26:51 -05001051 if (ext4_es_is_written(es) || ext4_es_is_unwritten(es)) {
1052 block = es->es_pblk + orig_len - len1;
1053 ext4_es_store_pblock(es, block);
1054 }
Zheng Liu654598b2012-11-08 21:57:20 -05001055 }
1056
1057out:
Zheng Liu06b0c882013-02-18 00:26:51 -05001058 return err;
1059}
1060
1061/*
1062 * ext4_es_remove_extent() removes a space from a extent status tree.
1063 *
1064 * Return 0 on success, error code on failure.
1065 */
1066int ext4_es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
1067 ext4_lblk_t len)
1068{
Zheng Liu06b0c882013-02-18 00:26:51 -05001069 ext4_lblk_t end;
1070 int err = 0;
1071
1072 trace_ext4_es_remove_extent(inode, lblk, len);
1073 es_debug("remove [%u/%u) from extent status tree of inode %lu\n",
1074 lblk, len, inode->i_ino);
1075
Eryu Guand4381472013-02-22 15:27:47 -05001076 if (!len)
1077 return err;
1078
Zheng Liu06b0c882013-02-18 00:26:51 -05001079 end = lblk + len - 1;
1080 BUG_ON(end < lblk);
1081
Zheng Liuedaa53c2014-11-25 11:45:37 -05001082 /*
1083 * ext4_clear_inode() depends on us taking i_es_lock unconditionally
1084 * so that we are sure __es_shrink() is done with the inode before it
1085 * is reclaimed.
1086 */
Zheng Liu06b0c882013-02-18 00:26:51 -05001087 write_lock(&EXT4_I(inode)->i_es_lock);
Zheng Liubdedbb72013-02-18 00:32:02 -05001088 err = __es_remove_extent(inode, lblk, end);
Zheng Liu654598b2012-11-08 21:57:20 -05001089 write_unlock(&EXT4_I(inode)->i_es_lock);
1090 ext4_es_print_tree(inode);
1091 return err;
1092}
Zheng Liu74cd15c2013-02-18 00:32:55 -05001093
Zheng Liuedaa53c2014-11-25 11:45:37 -05001094static int __es_shrink(struct ext4_sb_info *sbi, int nr_to_scan,
1095 struct ext4_inode_info *locked_ei)
Zheng Liu74cd15c2013-02-18 00:32:55 -05001096{
Zheng Liu74cd15c2013-02-18 00:32:55 -05001097 struct ext4_inode_info *ei;
Zheng Liueb68d0e2014-09-01 22:26:49 -04001098 struct ext4_es_stats *es_stats;
Zheng Liueb68d0e2014-09-01 22:26:49 -04001099 ktime_t start_time;
1100 u64 scan_time;
Zheng Liuedaa53c2014-11-25 11:45:37 -05001101 int nr_to_walk;
Dave Chinner1ab6c492013-08-28 10:18:09 +10001102 int nr_shrunk = 0;
Zheng Liuedaa53c2014-11-25 11:45:37 -05001103 int retried = 0, nr_skipped = 0;
Zheng Liu74cd15c2013-02-18 00:32:55 -05001104
Zheng Liueb68d0e2014-09-01 22:26:49 -04001105 es_stats = &sbi->s_es_stats;
1106 start_time = ktime_get();
Zheng Liud3922a72013-07-01 08:12:37 -04001107
Theodore Ts'o7869a4a2013-08-16 22:05:14 -04001108retry:
Zheng Liuedaa53c2014-11-25 11:45:37 -05001109 spin_lock(&sbi->s_es_lock);
1110 nr_to_walk = sbi->s_es_nr_inode;
1111 while (nr_to_walk-- > 0) {
Zheng Liuedaa53c2014-11-25 11:45:37 -05001112 if (list_empty(&sbi->s_es_list)) {
1113 spin_unlock(&sbi->s_es_lock);
1114 goto out;
1115 }
1116 ei = list_first_entry(&sbi->s_es_list, struct ext4_inode_info,
1117 i_es_list);
1118 /* Move the inode to the tail */
Jan Karadd475922014-11-25 11:51:23 -05001119 list_move_tail(&ei->i_es_list, &sbi->s_es_list);
Zheng Liu74cd15c2013-02-18 00:32:55 -05001120
Theodore Ts'o7869a4a2013-08-16 22:05:14 -04001121 /*
Zheng Liuedaa53c2014-11-25 11:45:37 -05001122 * Normally we try hard to avoid shrinking precached inodes,
1123 * but we will as a last resort.
Theodore Ts'o7869a4a2013-08-16 22:05:14 -04001124 */
Zheng Liuedaa53c2014-11-25 11:45:37 -05001125 if (!retried && ext4_test_inode_state(&ei->vfs_inode,
1126 EXT4_STATE_EXT_PRECACHED)) {
Theodore Ts'o7869a4a2013-08-16 22:05:14 -04001127 nr_skipped++;
Zheng Liu74cd15c2013-02-18 00:32:55 -05001128 continue;
1129 }
Zheng Liud3922a72013-07-01 08:12:37 -04001130
Zheng Liuedaa53c2014-11-25 11:45:37 -05001131 if (ei == locked_ei || !write_trylock(&ei->i_es_lock)) {
1132 nr_skipped++;
Zheng Liud3922a72013-07-01 08:12:37 -04001133 continue;
Zheng Liuedaa53c2014-11-25 11:45:37 -05001134 }
1135 /*
1136 * Now we hold i_es_lock which protects us from inode reclaim
1137 * freeing inode under us
1138 */
1139 spin_unlock(&sbi->s_es_lock);
Zheng Liu74cd15c2013-02-18 00:32:55 -05001140
Jan Karadd475922014-11-25 11:51:23 -05001141 nr_shrunk += es_reclaim_extents(ei, &nr_to_scan);
Zheng Liu74cd15c2013-02-18 00:32:55 -05001142 write_unlock(&ei->i_es_lock);
1143
Jan Karadd475922014-11-25 11:51:23 -05001144 if (nr_to_scan <= 0)
Zheng Liuedaa53c2014-11-25 11:45:37 -05001145 goto out;
1146 spin_lock(&sbi->s_es_lock);
1147 }
1148 spin_unlock(&sbi->s_es_lock);
Theodore Ts'o7869a4a2013-08-16 22:05:14 -04001149
1150 /*
1151 * If we skipped any inodes, and we weren't able to make any
Zheng Liuedaa53c2014-11-25 11:45:37 -05001152 * forward progress, try again to scan precached inodes.
Theodore Ts'o7869a4a2013-08-16 22:05:14 -04001153 */
1154 if ((nr_shrunk == 0) && nr_skipped && !retried) {
1155 retried++;
Theodore Ts'o7869a4a2013-08-16 22:05:14 -04001156 goto retry;
1157 }
1158
Theodore Ts'oe15f7422013-07-15 00:12:14 -04001159 if (locked_ei && nr_shrunk == 0)
Jan Karadd475922014-11-25 11:51:23 -05001160 nr_shrunk = es_reclaim_extents(locked_ei, &nr_to_scan);
Theodore Ts'oe15f7422013-07-15 00:12:14 -04001161
Zheng Liuedaa53c2014-11-25 11:45:37 -05001162out:
Zheng Liueb68d0e2014-09-01 22:26:49 -04001163 scan_time = ktime_to_ns(ktime_sub(ktime_get(), start_time));
1164 if (likely(es_stats->es_stats_scan_time))
1165 es_stats->es_stats_scan_time = (scan_time +
1166 es_stats->es_stats_scan_time*3) / 4;
1167 else
1168 es_stats->es_stats_scan_time = scan_time;
1169 if (scan_time > es_stats->es_stats_max_scan_time)
1170 es_stats->es_stats_max_scan_time = scan_time;
1171 if (likely(es_stats->es_stats_shrunk))
1172 es_stats->es_stats_shrunk = (nr_shrunk +
1173 es_stats->es_stats_shrunk*3) / 4;
1174 else
1175 es_stats->es_stats_shrunk = nr_shrunk;
1176
Zheng Liuedaa53c2014-11-25 11:45:37 -05001177 trace_ext4_es_shrink(sbi->s_sb, nr_shrunk, scan_time,
Zheng Liueb68d0e2014-09-01 22:26:49 -04001178 nr_skipped, retried);
Theodore Ts'oe15f7422013-07-15 00:12:14 -04001179 return nr_shrunk;
1180}
1181
Dave Chinner1ab6c492013-08-28 10:18:09 +10001182static unsigned long ext4_es_count(struct shrinker *shrink,
1183 struct shrink_control *sc)
1184{
1185 unsigned long nr;
1186 struct ext4_sb_info *sbi;
1187
1188 sbi = container_of(shrink, struct ext4_sb_info, s_es_shrinker);
Zheng Liuedaa53c2014-11-25 11:45:37 -05001189 nr = percpu_counter_read_positive(&sbi->s_es_stats.es_stats_shk_cnt);
Zheng Liue963bb12014-09-01 22:22:13 -04001190 trace_ext4_es_shrink_count(sbi->s_sb, sc->nr_to_scan, nr);
Dave Chinner1ab6c492013-08-28 10:18:09 +10001191 return nr;
1192}
1193
1194static unsigned long ext4_es_scan(struct shrinker *shrink,
1195 struct shrink_control *sc)
Theodore Ts'oe15f7422013-07-15 00:12:14 -04001196{
1197 struct ext4_sb_info *sbi = container_of(shrink,
1198 struct ext4_sb_info, s_es_shrinker);
1199 int nr_to_scan = sc->nr_to_scan;
1200 int ret, nr_shrunk;
1201
Zheng Liuedaa53c2014-11-25 11:45:37 -05001202 ret = percpu_counter_read_positive(&sbi->s_es_stats.es_stats_shk_cnt);
Zheng Liue963bb12014-09-01 22:22:13 -04001203 trace_ext4_es_shrink_scan_enter(sbi->s_sb, nr_to_scan, ret);
Theodore Ts'oe15f7422013-07-15 00:12:14 -04001204
1205 if (!nr_to_scan)
1206 return ret;
1207
Zheng Liuedaa53c2014-11-25 11:45:37 -05001208 nr_shrunk = __es_shrink(sbi, nr_to_scan, NULL);
Theodore Ts'oe15f7422013-07-15 00:12:14 -04001209
Zheng Liue963bb12014-09-01 22:22:13 -04001210 trace_ext4_es_shrink_scan_exit(sbi->s_sb, nr_shrunk, ret);
Dave Chinner1ab6c492013-08-28 10:18:09 +10001211 return nr_shrunk;
Zheng Liu74cd15c2013-02-18 00:32:55 -05001212}
1213
Theodore Ts'oebd173b2015-09-23 12:46:17 -04001214int ext4_seq_es_shrinker_info_show(struct seq_file *seq, void *v)
Zheng Liu74cd15c2013-02-18 00:32:55 -05001215{
Theodore Ts'oebd173b2015-09-23 12:46:17 -04001216 struct ext4_sb_info *sbi = EXT4_SB((struct super_block *) seq->private);
Zheng Liueb68d0e2014-09-01 22:26:49 -04001217 struct ext4_es_stats *es_stats = &sbi->s_es_stats;
1218 struct ext4_inode_info *ei, *max = NULL;
1219 unsigned int inode_cnt = 0;
1220
1221 if (v != SEQ_START_TOKEN)
1222 return 0;
1223
1224 /* here we just find an inode that has the max nr. of objects */
Zheng Liuedaa53c2014-11-25 11:45:37 -05001225 spin_lock(&sbi->s_es_lock);
1226 list_for_each_entry(ei, &sbi->s_es_list, i_es_list) {
Zheng Liueb68d0e2014-09-01 22:26:49 -04001227 inode_cnt++;
1228 if (max && max->i_es_all_nr < ei->i_es_all_nr)
1229 max = ei;
1230 else if (!max)
1231 max = ei;
1232 }
Zheng Liuedaa53c2014-11-25 11:45:37 -05001233 spin_unlock(&sbi->s_es_lock);
Zheng Liueb68d0e2014-09-01 22:26:49 -04001234
1235 seq_printf(seq, "stats:\n %lld objects\n %lld reclaimable objects\n",
1236 percpu_counter_sum_positive(&es_stats->es_stats_all_cnt),
Zheng Liuedaa53c2014-11-25 11:45:37 -05001237 percpu_counter_sum_positive(&es_stats->es_stats_shk_cnt));
Zheng Liueb68d0e2014-09-01 22:26:49 -04001238 seq_printf(seq, " %lu/%lu cache hits/misses\n",
1239 es_stats->es_stats_cache_hits,
1240 es_stats->es_stats_cache_misses);
Zheng Liueb68d0e2014-09-01 22:26:49 -04001241 if (inode_cnt)
Zheng Liuedaa53c2014-11-25 11:45:37 -05001242 seq_printf(seq, " %d inodes on list\n", inode_cnt);
Zheng Liueb68d0e2014-09-01 22:26:49 -04001243
1244 seq_printf(seq, "average:\n %llu us scan time\n",
1245 div_u64(es_stats->es_stats_scan_time, 1000));
1246 seq_printf(seq, " %lu shrunk objects\n", es_stats->es_stats_shrunk);
1247 if (inode_cnt)
1248 seq_printf(seq,
1249 "maximum:\n %lu inode (%u objects, %u reclaimable)\n"
1250 " %llu us max scan time\n",
Zheng Liuedaa53c2014-11-25 11:45:37 -05001251 max->vfs_inode.i_ino, max->i_es_all_nr, max->i_es_shk_nr,
Zheng Liueb68d0e2014-09-01 22:26:49 -04001252 div_u64(es_stats->es_stats_max_scan_time, 1000));
1253
1254 return 0;
1255}
1256
Zheng Liueb68d0e2014-09-01 22:26:49 -04001257int ext4_es_register_shrinker(struct ext4_sb_info *sbi)
1258{
1259 int err;
1260
Jan Kara624d0f12014-11-25 11:53:47 -05001261 /* Make sure we have enough bits for physical block number */
1262 BUILD_BUG_ON(ES_SHIFT < 48);
Zheng Liuedaa53c2014-11-25 11:45:37 -05001263 INIT_LIST_HEAD(&sbi->s_es_list);
1264 sbi->s_es_nr_inode = 0;
1265 spin_lock_init(&sbi->s_es_lock);
Zheng Liueb68d0e2014-09-01 22:26:49 -04001266 sbi->s_es_stats.es_stats_shrunk = 0;
1267 sbi->s_es_stats.es_stats_cache_hits = 0;
1268 sbi->s_es_stats.es_stats_cache_misses = 0;
1269 sbi->s_es_stats.es_stats_scan_time = 0;
1270 sbi->s_es_stats.es_stats_max_scan_time = 0;
Linus Torvaldsc2661b82014-10-20 09:50:11 -07001271 err = percpu_counter_init(&sbi->s_es_stats.es_stats_all_cnt, 0, GFP_KERNEL);
Zheng Liueb68d0e2014-09-01 22:26:49 -04001272 if (err)
1273 return err;
Zheng Liuedaa53c2014-11-25 11:45:37 -05001274 err = percpu_counter_init(&sbi->s_es_stats.es_stats_shk_cnt, 0, GFP_KERNEL);
Zheng Liueb68d0e2014-09-01 22:26:49 -04001275 if (err)
1276 goto err1;
1277
Dave Chinner1ab6c492013-08-28 10:18:09 +10001278 sbi->s_es_shrinker.scan_objects = ext4_es_scan;
1279 sbi->s_es_shrinker.count_objects = ext4_es_count;
Zheng Liu74cd15c2013-02-18 00:32:55 -05001280 sbi->s_es_shrinker.seeks = DEFAULT_SEEKS;
Zheng Liueb68d0e2014-09-01 22:26:49 -04001281 err = register_shrinker(&sbi->s_es_shrinker);
1282 if (err)
1283 goto err2;
1284
Zheng Liueb68d0e2014-09-01 22:26:49 -04001285 return 0;
1286
1287err2:
Zheng Liuedaa53c2014-11-25 11:45:37 -05001288 percpu_counter_destroy(&sbi->s_es_stats.es_stats_shk_cnt);
Zheng Liueb68d0e2014-09-01 22:26:49 -04001289err1:
1290 percpu_counter_destroy(&sbi->s_es_stats.es_stats_all_cnt);
1291 return err;
Zheng Liu74cd15c2013-02-18 00:32:55 -05001292}
1293
Zheng Liud3922a72013-07-01 08:12:37 -04001294void ext4_es_unregister_shrinker(struct ext4_sb_info *sbi)
Zheng Liu74cd15c2013-02-18 00:32:55 -05001295{
Zheng Liueb68d0e2014-09-01 22:26:49 -04001296 percpu_counter_destroy(&sbi->s_es_stats.es_stats_all_cnt);
Zheng Liuedaa53c2014-11-25 11:45:37 -05001297 percpu_counter_destroy(&sbi->s_es_stats.es_stats_shk_cnt);
Zheng Liud3922a72013-07-01 08:12:37 -04001298 unregister_shrinker(&sbi->s_es_shrinker);
Zheng Liu74cd15c2013-02-18 00:32:55 -05001299}
1300
Jan Karadd475922014-11-25 11:51:23 -05001301/*
1302 * Shrink extents in given inode from ei->i_es_shrink_lblk till end. Scan at
1303 * most *nr_to_scan extents, update *nr_to_scan accordingly.
1304 *
1305 * Return 0 if we hit end of tree / interval, 1 if we exhausted nr_to_scan.
1306 * Increment *nr_shrunk by the number of reclaimed extents. Also update
1307 * ei->i_es_shrink_lblk to where we should continue scanning.
1308 */
1309static int es_do_reclaim_extents(struct ext4_inode_info *ei, ext4_lblk_t end,
1310 int *nr_to_scan, int *nr_shrunk)
Zheng Liu74cd15c2013-02-18 00:32:55 -05001311{
1312 struct inode *inode = &ei->vfs_inode;
1313 struct ext4_es_tree *tree = &ei->i_es_tree;
Zheng Liu74cd15c2013-02-18 00:32:55 -05001314 struct extent_status *es;
Jan Karadd475922014-11-25 11:51:23 -05001315 struct rb_node *node;
1316
1317 es = __es_tree_search(&tree->root, ei->i_es_shrink_lblk);
1318 if (!es)
1319 goto out_wrap;
1320 node = &es->rb_node;
1321 while (*nr_to_scan > 0) {
1322 if (es->es_lblk > end) {
1323 ei->i_es_shrink_lblk = end + 1;
1324 return 0;
1325 }
1326
1327 (*nr_to_scan)--;
1328 node = rb_next(&es->rb_node);
1329 /*
1330 * We can't reclaim delayed extent from status tree because
1331 * fiemap, bigallic, and seek_data/hole need to use it.
1332 */
Jan Kara2be12de2014-11-25 11:55:24 -05001333 if (ext4_es_is_delayed(es))
1334 goto next;
1335 if (ext4_es_is_referenced(es)) {
1336 ext4_es_clear_referenced(es);
1337 goto next;
Jan Karadd475922014-11-25 11:51:23 -05001338 }
Jan Kara2be12de2014-11-25 11:55:24 -05001339
1340 rb_erase(&es->rb_node, &tree->root);
1341 ext4_es_free_extent(inode, es);
1342 (*nr_shrunk)++;
1343next:
Jan Karadd475922014-11-25 11:51:23 -05001344 if (!node)
1345 goto out_wrap;
1346 es = rb_entry(node, struct extent_status, rb_node);
1347 }
1348 ei->i_es_shrink_lblk = es->es_lblk;
1349 return 1;
1350out_wrap:
1351 ei->i_es_shrink_lblk = 0;
1352 return 0;
1353}
1354
1355static int es_reclaim_extents(struct ext4_inode_info *ei, int *nr_to_scan)
1356{
1357 struct inode *inode = &ei->vfs_inode;
1358 int nr_shrunk = 0;
1359 ext4_lblk_t start = ei->i_es_shrink_lblk;
Theodore Ts'o7869a4a2013-08-16 22:05:14 -04001360 static DEFINE_RATELIMIT_STATE(_rs, DEFAULT_RATELIMIT_INTERVAL,
1361 DEFAULT_RATELIMIT_BURST);
Zheng Liu74cd15c2013-02-18 00:32:55 -05001362
Zheng Liuedaa53c2014-11-25 11:45:37 -05001363 if (ei->i_es_shk_nr == 0)
Zheng Liu74cd15c2013-02-18 00:32:55 -05001364 return 0;
1365
Theodore Ts'o7869a4a2013-08-16 22:05:14 -04001366 if (ext4_test_inode_state(inode, EXT4_STATE_EXT_PRECACHED) &&
1367 __ratelimit(&_rs))
1368 ext4_warning(inode->i_sb, "forced shrink of precached extents");
1369
Jan Karadd475922014-11-25 11:51:23 -05001370 if (!es_do_reclaim_extents(ei, EXT_MAX_BLOCKS, nr_to_scan, &nr_shrunk) &&
1371 start != 0)
1372 es_do_reclaim_extents(ei, start - 1, nr_to_scan, &nr_shrunk);
1373
1374 ei->i_es_tree.cache_es = NULL;
Zheng Liu74cd15c2013-02-18 00:32:55 -05001375 return nr_shrunk;
1376}
Eric Whitney1dc0aa42018-10-01 14:17:41 -04001377
1378#ifdef ES_DEBUG__
1379static void ext4_print_pending_tree(struct inode *inode)
1380{
1381 struct ext4_pending_tree *tree;
1382 struct rb_node *node;
1383 struct pending_reservation *pr;
1384
1385 printk(KERN_DEBUG "pending reservations for inode %lu:", inode->i_ino);
1386 tree = &EXT4_I(inode)->i_pending_tree;
1387 node = rb_first(&tree->root);
1388 while (node) {
1389 pr = rb_entry(node, struct pending_reservation, rb_node);
1390 printk(KERN_DEBUG " %u", pr->lclu);
1391 node = rb_next(node);
1392 }
1393 printk(KERN_DEBUG "\n");
1394}
1395#else
1396#define ext4_print_pending_tree(inode)
1397#endif
1398
1399int __init ext4_init_pending(void)
1400{
1401 ext4_pending_cachep = kmem_cache_create("ext4_pending_reservation",
1402 sizeof(struct pending_reservation),
1403 0, (SLAB_RECLAIM_ACCOUNT), NULL);
1404 if (ext4_pending_cachep == NULL)
1405 return -ENOMEM;
1406 return 0;
1407}
1408
1409void ext4_exit_pending(void)
1410{
1411 kmem_cache_destroy(ext4_pending_cachep);
1412}
1413
1414void ext4_init_pending_tree(struct ext4_pending_tree *tree)
1415{
1416 tree->root = RB_ROOT;
1417}
1418
1419/*
1420 * __get_pending - retrieve a pointer to a pending reservation
1421 *
1422 * @inode - file containing the pending cluster reservation
1423 * @lclu - logical cluster of interest
1424 *
1425 * Returns a pointer to a pending reservation if it's a member of
1426 * the set, and NULL if not. Must be called holding i_es_lock.
1427 */
1428static struct pending_reservation *__get_pending(struct inode *inode,
1429 ext4_lblk_t lclu)
1430{
1431 struct ext4_pending_tree *tree;
1432 struct rb_node *node;
1433 struct pending_reservation *pr = NULL;
1434
1435 tree = &EXT4_I(inode)->i_pending_tree;
1436 node = (&tree->root)->rb_node;
1437
1438 while (node) {
1439 pr = rb_entry(node, struct pending_reservation, rb_node);
1440 if (lclu < pr->lclu)
1441 node = node->rb_left;
1442 else if (lclu > pr->lclu)
1443 node = node->rb_right;
1444 else if (lclu == pr->lclu)
1445 return pr;
1446 }
1447 return NULL;
1448}
1449
1450/*
1451 * __insert_pending - adds a pending cluster reservation to the set of
1452 * pending reservations
1453 *
1454 * @inode - file containing the cluster
1455 * @lblk - logical block in the cluster to be added
1456 *
1457 * Returns 0 on successful insertion and -ENOMEM on failure. If the
1458 * pending reservation is already in the set, returns successfully.
1459 */
1460static int __insert_pending(struct inode *inode, ext4_lblk_t lblk)
1461{
1462 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
1463 struct ext4_pending_tree *tree = &EXT4_I(inode)->i_pending_tree;
1464 struct rb_node **p = &tree->root.rb_node;
1465 struct rb_node *parent = NULL;
1466 struct pending_reservation *pr;
1467 ext4_lblk_t lclu;
1468 int ret = 0;
1469
1470 lclu = EXT4_B2C(sbi, lblk);
1471 /* search to find parent for insertion */
1472 while (*p) {
1473 parent = *p;
1474 pr = rb_entry(parent, struct pending_reservation, rb_node);
1475
1476 if (lclu < pr->lclu) {
1477 p = &(*p)->rb_left;
1478 } else if (lclu > pr->lclu) {
1479 p = &(*p)->rb_right;
1480 } else {
1481 /* pending reservation already inserted */
1482 goto out;
1483 }
1484 }
1485
1486 pr = kmem_cache_alloc(ext4_pending_cachep, GFP_ATOMIC);
1487 if (pr == NULL) {
1488 ret = -ENOMEM;
1489 goto out;
1490 }
1491 pr->lclu = lclu;
1492
1493 rb_link_node(&pr->rb_node, parent, p);
1494 rb_insert_color(&pr->rb_node, &tree->root);
1495
1496out:
1497 return ret;
1498}
1499
1500/*
1501 * __remove_pending - removes a pending cluster reservation from the set
1502 * of pending reservations
1503 *
1504 * @inode - file containing the cluster
1505 * @lblk - logical block in the pending cluster reservation to be removed
1506 *
1507 * Returns successfully if pending reservation is not a member of the set.
1508 */
1509static void __remove_pending(struct inode *inode, ext4_lblk_t lblk)
1510{
1511 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
1512 struct pending_reservation *pr;
1513 struct ext4_pending_tree *tree;
1514
1515 pr = __get_pending(inode, EXT4_B2C(sbi, lblk));
1516 if (pr != NULL) {
1517 tree = &EXT4_I(inode)->i_pending_tree;
1518 rb_erase(&pr->rb_node, &tree->root);
1519 kmem_cache_free(ext4_pending_cachep, pr);
1520 }
1521}
1522
1523/*
1524 * ext4_remove_pending - removes a pending cluster reservation from the set
1525 * of pending reservations
1526 *
1527 * @inode - file containing the cluster
1528 * @lblk - logical block in the pending cluster reservation to be removed
1529 *
1530 * Locking for external use of __remove_pending.
1531 */
1532void ext4_remove_pending(struct inode *inode, ext4_lblk_t lblk)
1533{
1534 struct ext4_inode_info *ei = EXT4_I(inode);
1535
1536 write_lock(&ei->i_es_lock);
1537 __remove_pending(inode, lblk);
1538 write_unlock(&ei->i_es_lock);
1539}
1540
1541/*
1542 * ext4_is_pending - determine whether a cluster has a pending reservation
1543 * on it
1544 *
1545 * @inode - file containing the cluster
1546 * @lblk - logical block in the cluster
1547 *
1548 * Returns true if there's a pending reservation for the cluster in the
1549 * set of pending reservations, and false if not.
1550 */
1551bool ext4_is_pending(struct inode *inode, ext4_lblk_t lblk)
1552{
1553 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
1554 struct ext4_inode_info *ei = EXT4_I(inode);
1555 bool ret;
1556
1557 read_lock(&ei->i_es_lock);
1558 ret = (bool)(__get_pending(inode, EXT4_B2C(sbi, lblk)) != NULL);
1559 read_unlock(&ei->i_es_lock);
1560
1561 return ret;
1562}
Eric Whitney0b02f4c2018-10-01 14:19:37 -04001563
1564/*
1565 * ext4_es_insert_delayed_block - adds a delayed block to the extents status
1566 * tree, adding a pending reservation where
1567 * needed
1568 *
1569 * @inode - file containing the newly added block
1570 * @lblk - logical block to be added
1571 * @allocated - indicates whether a physical cluster has been allocated for
1572 * the logical cluster that contains the block
1573 *
1574 * Returns 0 on success, negative error code on failure.
1575 */
1576int ext4_es_insert_delayed_block(struct inode *inode, ext4_lblk_t lblk,
1577 bool allocated)
1578{
1579 struct extent_status newes;
1580 int err = 0;
1581
1582 es_debug("add [%u/1) delayed to extent status tree of inode %lu\n",
1583 lblk, inode->i_ino);
1584
1585 newes.es_lblk = lblk;
1586 newes.es_len = 1;
1587 ext4_es_store_pblock_status(&newes, ~0, EXTENT_STATUS_DELAYED);
1588 trace_ext4_es_insert_delayed_block(inode, &newes, allocated);
1589
1590 ext4_es_insert_extent_check(inode, &newes);
1591
1592 write_lock(&EXT4_I(inode)->i_es_lock);
1593
1594 err = __es_remove_extent(inode, lblk, lblk);
1595 if (err != 0)
1596 goto error;
1597retry:
1598 err = __es_insert_extent(inode, &newes);
1599 if (err == -ENOMEM && __es_shrink(EXT4_SB(inode->i_sb),
1600 128, EXT4_I(inode)))
1601 goto retry;
1602 if (err != 0)
1603 goto error;
1604
1605 if (allocated)
1606 __insert_pending(inode, lblk);
1607
1608error:
1609 write_unlock(&EXT4_I(inode)->i_es_lock);
1610
1611 ext4_es_print_tree(inode);
1612 ext4_print_pending_tree(inode);
1613
1614 return err;
1615}
Eric Whitneyb6bf9172018-10-01 14:24:08 -04001616
1617/*
1618 * __es_delayed_clu - count number of clusters containing blocks that
1619 * are delayed only
1620 *
1621 * @inode - file containing block range
1622 * @start - logical block defining start of range
1623 * @end - logical block defining end of range
1624 *
1625 * Returns the number of clusters containing only delayed (not delayed
1626 * and unwritten) blocks in the range specified by @start and @end. Any
1627 * cluster or part of a cluster within the range and containing a delayed
1628 * and not unwritten block within the range is counted as a whole cluster.
1629 */
1630static unsigned int __es_delayed_clu(struct inode *inode, ext4_lblk_t start,
1631 ext4_lblk_t end)
1632{
1633 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
1634 struct extent_status *es;
1635 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
1636 struct rb_node *node;
1637 ext4_lblk_t first_lclu, last_lclu;
1638 unsigned long long last_counted_lclu;
1639 unsigned int n = 0;
1640
1641 /* guaranteed to be unequal to any ext4_lblk_t value */
1642 last_counted_lclu = ~0ULL;
1643
1644 es = __es_tree_search(&tree->root, start);
1645
1646 while (es && (es->es_lblk <= end)) {
1647 if (ext4_es_is_delonly(es)) {
1648 if (es->es_lblk <= start)
1649 first_lclu = EXT4_B2C(sbi, start);
1650 else
1651 first_lclu = EXT4_B2C(sbi, es->es_lblk);
1652
1653 if (ext4_es_end(es) >= end)
1654 last_lclu = EXT4_B2C(sbi, end);
1655 else
1656 last_lclu = EXT4_B2C(sbi, ext4_es_end(es));
1657
1658 if (first_lclu == last_counted_lclu)
1659 n += last_lclu - first_lclu;
1660 else
1661 n += last_lclu - first_lclu + 1;
1662 last_counted_lclu = last_lclu;
1663 }
1664 node = rb_next(&es->rb_node);
1665 if (!node)
1666 break;
1667 es = rb_entry(node, struct extent_status, rb_node);
1668 }
1669
1670 return n;
1671}
1672
1673/*
1674 * ext4_es_delayed_clu - count number of clusters containing blocks that
1675 * are both delayed and unwritten
1676 *
1677 * @inode - file containing block range
1678 * @lblk - logical block defining start of range
1679 * @len - number of blocks in range
1680 *
1681 * Locking for external use of __es_delayed_clu().
1682 */
1683unsigned int ext4_es_delayed_clu(struct inode *inode, ext4_lblk_t lblk,
1684 ext4_lblk_t len)
1685{
1686 struct ext4_inode_info *ei = EXT4_I(inode);
1687 ext4_lblk_t end;
1688 unsigned int n;
1689
1690 if (len == 0)
1691 return 0;
1692
1693 end = lblk + len - 1;
1694 WARN_ON(end < lblk);
1695
1696 read_lock(&ei->i_es_lock);
1697
1698 n = __es_delayed_clu(inode, lblk, end);
1699
1700 read_unlock(&ei->i_es_lock);
1701
1702 return n;
1703}
1704
1705/*
1706 * __revise_pending - makes, cancels, or leaves unchanged pending cluster
1707 * reservations for a specified block range depending
1708 * upon the presence or absence of delayed blocks
1709 * outside the range within clusters at the ends of the
1710 * range
1711 *
1712 * @inode - file containing the range
1713 * @lblk - logical block defining the start of range
1714 * @len - length of range in blocks
1715 *
1716 * Used after a newly allocated extent is added to the extents status tree.
1717 * Requires that the extents in the range have either written or unwritten
1718 * status. Must be called while holding i_es_lock.
1719 */
1720static void __revise_pending(struct inode *inode, ext4_lblk_t lblk,
1721 ext4_lblk_t len)
1722{
1723 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
1724 ext4_lblk_t end = lblk + len - 1;
1725 ext4_lblk_t first, last;
1726 bool f_del = false, l_del = false;
1727
1728 if (len == 0)
1729 return;
1730
1731 /*
1732 * Two cases - block range within single cluster and block range
1733 * spanning two or more clusters. Note that a cluster belonging
1734 * to a range starting and/or ending on a cluster boundary is treated
1735 * as if it does not contain a delayed extent. The new range may
1736 * have allocated space for previously delayed blocks out to the
1737 * cluster boundary, requiring that any pre-existing pending
1738 * reservation be canceled. Because this code only looks at blocks
1739 * outside the range, it should revise pending reservations
1740 * correctly even if the extent represented by the range can't be
1741 * inserted in the extents status tree due to ENOSPC.
1742 */
1743
1744 if (EXT4_B2C(sbi, lblk) == EXT4_B2C(sbi, end)) {
1745 first = EXT4_LBLK_CMASK(sbi, lblk);
1746 if (first != lblk)
1747 f_del = __es_scan_range(inode, &ext4_es_is_delonly,
1748 first, lblk - 1);
1749 if (f_del) {
1750 __insert_pending(inode, first);
1751 } else {
1752 last = EXT4_LBLK_CMASK(sbi, end) +
1753 sbi->s_cluster_ratio - 1;
1754 if (last != end)
1755 l_del = __es_scan_range(inode,
1756 &ext4_es_is_delonly,
1757 end + 1, last);
1758 if (l_del)
1759 __insert_pending(inode, last);
1760 else
1761 __remove_pending(inode, last);
1762 }
1763 } else {
1764 first = EXT4_LBLK_CMASK(sbi, lblk);
1765 if (first != lblk)
1766 f_del = __es_scan_range(inode, &ext4_es_is_delonly,
1767 first, lblk - 1);
1768 if (f_del)
1769 __insert_pending(inode, first);
1770 else
1771 __remove_pending(inode, first);
1772
1773 last = EXT4_LBLK_CMASK(sbi, end) + sbi->s_cluster_ratio - 1;
1774 if (last != end)
1775 l_del = __es_scan_range(inode, &ext4_es_is_delonly,
1776 end + 1, last);
1777 if (l_del)
1778 __insert_pending(inode, last);
1779 else
1780 __remove_pending(inode, last);
1781 }
1782}
Eric Whitneyf4567672018-10-01 14:33:24 -04001783
1784/*
1785 * ext4_es_remove_blks - remove block range from extents status tree and
1786 * reduce reservation count or cancel pending
1787 * reservation as needed
1788 *
1789 * @inode - file containing range
1790 * @lblk - first block in range
1791 * @len - number of blocks to remove
1792 *
1793 */
1794void ext4_es_remove_blks(struct inode *inode, ext4_lblk_t lblk,
1795 ext4_lblk_t len)
1796{
1797 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
1798 unsigned int clu_size, reserved = 0;
1799 ext4_lblk_t last_lclu, first, length, remainder, last;
1800 bool delonly;
1801 int err = 0;
1802 struct pending_reservation *pr;
1803 struct ext4_pending_tree *tree;
1804
1805 /*
1806 * Process cluster by cluster for bigalloc - there may be up to
1807 * two clusters in a 4k page with a 1k block size and two blocks
1808 * per cluster. Also necessary for systems with larger page sizes
1809 * and potentially larger block sizes.
1810 */
1811 clu_size = sbi->s_cluster_ratio;
1812 last_lclu = EXT4_B2C(sbi, lblk + len - 1);
1813
1814 write_lock(&EXT4_I(inode)->i_es_lock);
1815
1816 for (first = lblk, remainder = len;
1817 remainder > 0;
1818 first += length, remainder -= length) {
1819
1820 if (EXT4_B2C(sbi, first) == last_lclu)
1821 length = remainder;
1822 else
1823 length = clu_size - EXT4_LBLK_COFF(sbi, first);
1824
1825 /*
1826 * The BH_Delay flag, which triggers calls to this function,
1827 * and the contents of the extents status tree can be
1828 * inconsistent due to writepages activity. So, note whether
1829 * the blocks to be removed actually belong to an extent with
1830 * delayed only status.
1831 */
1832 delonly = __es_scan_clu(inode, &ext4_es_is_delonly, first);
1833
1834 /*
1835 * because of the writepages effect, written and unwritten
1836 * blocks could be removed here
1837 */
1838 last = first + length - 1;
1839 err = __es_remove_extent(inode, first, last);
1840 if (err)
1841 ext4_warning(inode->i_sb,
1842 "%s: couldn't remove page (err = %d)",
1843 __func__, err);
1844
1845 /* non-bigalloc case: simply count the cluster for release */
1846 if (sbi->s_cluster_ratio == 1 && delonly) {
1847 reserved++;
1848 continue;
1849 }
1850
1851 /*
1852 * bigalloc case: if all delayed allocated only blocks have
1853 * just been removed from a cluster, either cancel a pending
1854 * reservation if it exists or count a cluster for release
1855 */
1856 if (delonly &&
1857 !__es_scan_clu(inode, &ext4_es_is_delonly, first)) {
1858 pr = __get_pending(inode, EXT4_B2C(sbi, first));
1859 if (pr != NULL) {
1860 tree = &EXT4_I(inode)->i_pending_tree;
1861 rb_erase(&pr->rb_node, &tree->root);
1862 kmem_cache_free(ext4_pending_cachep, pr);
1863 } else {
1864 reserved++;
1865 }
1866 }
1867 }
1868
1869 write_unlock(&EXT4_I(inode)->i_es_lock);
1870
1871 ext4_da_release_space(inode, reserved);
1872}