blob: fe3337a85edeaecd6135333759173d8c6fbc0e78 [file] [log] [blame]
Zheng Liu654598b2012-11-08 21:57:20 -05001/*
2 * fs/ext4/extents_status.c
3 *
4 * Written by Yongqiang Yang <xiaoqiangnk@gmail.com>
5 * Modified by
6 * Allison Henderson <achender@linux.vnet.ibm.com>
7 * Hugh Dickins <hughd@google.com>
8 * Zheng Liu <wenqing.lz@taobao.com>
9 *
10 * Ext4 extents status tree core functions.
11 */
12#include <linux/rbtree.h>
13#include "ext4.h"
14#include "extents_status.h"
15#include "ext4_extents.h"
16
Zheng Liu992e9fd2012-11-08 21:57:33 -050017#include <trace/events/ext4.h>
18
Zheng Liu654598b2012-11-08 21:57:20 -050019/*
20 * According to previous discussion in Ext4 Developer Workshop, we
21 * will introduce a new structure called io tree to track all extent
22 * status in order to solve some problems that we have met
23 * (e.g. Reservation space warning), and provide extent-level locking.
24 * Delay extent tree is the first step to achieve this goal. It is
25 * original built by Yongqiang Yang. At that time it is called delay
Zheng Liu06b0c882013-02-18 00:26:51 -050026 * extent tree, whose goal is only track delayed extents in memory to
Zheng Liu654598b2012-11-08 21:57:20 -050027 * simplify the implementation of fiemap and bigalloc, and introduce
28 * lseek SEEK_DATA/SEEK_HOLE support. That is why it is still called
Zheng Liu06b0c882013-02-18 00:26:51 -050029 * delay extent tree at the first commit. But for better understand
30 * what it does, it has been rename to extent status tree.
Zheng Liu654598b2012-11-08 21:57:20 -050031 *
Zheng Liu06b0c882013-02-18 00:26:51 -050032 * Step1:
33 * Currently the first step has been done. All delayed extents are
34 * tracked in the tree. It maintains the delayed extent when a delayed
35 * allocation is issued, and the delayed extent is written out or
Zheng Liu654598b2012-11-08 21:57:20 -050036 * invalidated. Therefore the implementation of fiemap and bigalloc
37 * are simplified, and SEEK_DATA/SEEK_HOLE are introduced.
38 *
39 * The following comment describes the implemenmtation of extent
40 * status tree and future works.
Zheng Liu06b0c882013-02-18 00:26:51 -050041 *
42 * Step2:
43 * In this step all extent status are tracked by extent status tree.
44 * Thus, we can first try to lookup a block mapping in this tree before
45 * finding it in extent tree. Hence, single extent cache can be removed
46 * because extent status tree can do a better job. Extents in status
47 * tree are loaded on-demand. Therefore, the extent status tree may not
48 * contain all of the extents in a file. Meanwhile we define a shrinker
49 * to reclaim memory from extent status tree because fragmented extent
50 * tree will make status tree cost too much memory. written/unwritten/-
51 * hole extents in the tree will be reclaimed by this shrinker when we
52 * are under high memory pressure. Delayed extents will not be
53 * reclimed because fiemap, bigalloc, and seek_data/hole need it.
Zheng Liu654598b2012-11-08 21:57:20 -050054 */
55
56/*
Zheng Liu06b0c882013-02-18 00:26:51 -050057 * Extent status tree implementation for ext4.
Zheng Liu654598b2012-11-08 21:57:20 -050058 *
59 *
60 * ==========================================================================
Zheng Liu06b0c882013-02-18 00:26:51 -050061 * Extent status tree tracks all extent status.
Zheng Liu654598b2012-11-08 21:57:20 -050062 *
Zheng Liu06b0c882013-02-18 00:26:51 -050063 * 1. Why we need to implement extent status tree?
Zheng Liu654598b2012-11-08 21:57:20 -050064 *
Zheng Liu06b0c882013-02-18 00:26:51 -050065 * Without extent status tree, ext4 identifies a delayed extent by looking
Zheng Liu654598b2012-11-08 21:57:20 -050066 * up page cache, this has several deficiencies - complicated, buggy,
67 * and inefficient code.
68 *
Zheng Liu06b0c882013-02-18 00:26:51 -050069 * FIEMAP, SEEK_HOLE/DATA, bigalloc, and writeout all need to know if a
70 * block or a range of blocks are belonged to a delayed extent.
Zheng Liu654598b2012-11-08 21:57:20 -050071 *
Zheng Liu06b0c882013-02-18 00:26:51 -050072 * Let us have a look at how they do without extent status tree.
Zheng Liu654598b2012-11-08 21:57:20 -050073 * -- FIEMAP
74 * FIEMAP looks up page cache to identify delayed allocations from holes.
75 *
76 * -- SEEK_HOLE/DATA
77 * SEEK_HOLE/DATA has the same problem as FIEMAP.
78 *
79 * -- bigalloc
80 * bigalloc looks up page cache to figure out if a block is
81 * already under delayed allocation or not to determine whether
82 * quota reserving is needed for the cluster.
83 *
Zheng Liu654598b2012-11-08 21:57:20 -050084 * -- writeout
85 * Writeout looks up whole page cache to see if a buffer is
86 * mapped, If there are not very many delayed buffers, then it is
87 * time comsuming.
88 *
Zheng Liu06b0c882013-02-18 00:26:51 -050089 * With extent status tree implementation, FIEMAP, SEEK_HOLE/DATA,
Zheng Liu654598b2012-11-08 21:57:20 -050090 * bigalloc and writeout can figure out if a block or a range of
91 * blocks is under delayed allocation(belonged to a delayed extent) or
Zheng Liu06b0c882013-02-18 00:26:51 -050092 * not by searching the extent tree.
Zheng Liu654598b2012-11-08 21:57:20 -050093 *
94 *
95 * ==========================================================================
Zheng Liu06b0c882013-02-18 00:26:51 -050096 * 2. Ext4 extent status tree impelmentation
Zheng Liu654598b2012-11-08 21:57:20 -050097 *
Zheng Liu06b0c882013-02-18 00:26:51 -050098 * -- extent
99 * A extent is a range of blocks which are contiguous logically and
100 * physically. Unlike extent in extent tree, this extent in ext4 is
101 * a in-memory struct, there is no corresponding on-disk data. There
102 * is no limit on length of extent, so an extent can contain as many
103 * blocks as they are contiguous logically and physically.
Zheng Liu654598b2012-11-08 21:57:20 -0500104 *
Zheng Liu06b0c882013-02-18 00:26:51 -0500105 * -- extent status tree
106 * Every inode has an extent status tree and all allocation blocks
107 * are added to the tree with different status. The extent in the
108 * tree are ordered by logical block no.
Zheng Liu654598b2012-11-08 21:57:20 -0500109 *
Zheng Liu06b0c882013-02-18 00:26:51 -0500110 * -- operations on a extent status tree
111 * There are three important operations on a delayed extent tree: find
112 * next extent, adding a extent(a range of blocks) and removing a extent.
Zheng Liu654598b2012-11-08 21:57:20 -0500113 *
Zheng Liu06b0c882013-02-18 00:26:51 -0500114 * -- race on a extent status tree
115 * Extent status tree is protected by inode->i_es_lock.
116 *
117 * -- memory consumption
118 * Fragmented extent tree will make extent status tree cost too much
119 * memory. Hence, we will reclaim written/unwritten/hole extents from
120 * the tree under a heavy memory pressure.
Zheng Liu654598b2012-11-08 21:57:20 -0500121 *
122 *
123 * ==========================================================================
Zheng Liu06b0c882013-02-18 00:26:51 -0500124 * 3. Performance analysis
125 *
Zheng Liu654598b2012-11-08 21:57:20 -0500126 * -- overhead
127 * 1. There is a cache extent for write access, so if writes are
128 * not very random, adding space operaions are in O(1) time.
129 *
130 * -- gain
131 * 2. Code is much simpler, more readable, more maintainable and
132 * more efficient.
133 *
134 *
135 * ==========================================================================
136 * 4. TODO list
Zheng Liu654598b2012-11-08 21:57:20 -0500137 *
Zheng Liu06b0c882013-02-18 00:26:51 -0500138 * -- Refactor delayed space reservation
Zheng Liu654598b2012-11-08 21:57:20 -0500139 *
140 * -- Extent-level locking
141 */
142
143static struct kmem_cache *ext4_es_cachep;
144
Zheng Liubdedbb72013-02-18 00:32:02 -0500145static int __es_insert_extent(struct inode *inode, struct extent_status *newes);
146static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
Zheng Liu06b0c882013-02-18 00:26:51 -0500147 ext4_lblk_t end);
Zheng Liu74cd15c2013-02-18 00:32:55 -0500148static int __es_try_to_reclaim_extents(struct ext4_inode_info *ei,
149 int nr_to_scan);
Zheng Liu06b0c882013-02-18 00:26:51 -0500150
Zheng Liu654598b2012-11-08 21:57:20 -0500151int __init ext4_init_es(void)
152{
Theodore Ts'o24630772013-02-28 23:58:56 -0500153 ext4_es_cachep = kmem_cache_create("ext4_extent_status",
154 sizeof(struct extent_status),
155 0, (SLAB_RECLAIM_ACCOUNT), NULL);
Zheng Liu654598b2012-11-08 21:57:20 -0500156 if (ext4_es_cachep == NULL)
157 return -ENOMEM;
158 return 0;
159}
160
161void ext4_exit_es(void)
162{
163 if (ext4_es_cachep)
164 kmem_cache_destroy(ext4_es_cachep);
165}
166
167void ext4_es_init_tree(struct ext4_es_tree *tree)
168{
169 tree->root = RB_ROOT;
170 tree->cache_es = NULL;
171}
172
173#ifdef ES_DEBUG__
174static void ext4_es_print_tree(struct inode *inode)
175{
176 struct ext4_es_tree *tree;
177 struct rb_node *node;
178
179 printk(KERN_DEBUG "status extents for inode %lu:", inode->i_ino);
180 tree = &EXT4_I(inode)->i_es_tree;
181 node = rb_first(&tree->root);
182 while (node) {
183 struct extent_status *es;
184 es = rb_entry(node, struct extent_status, rb_node);
Zheng Liufdc02122013-02-18 00:26:51 -0500185 printk(KERN_DEBUG " [%u/%u) %llu %llx",
186 es->es_lblk, es->es_len,
187 ext4_es_pblock(es), ext4_es_status(es));
Zheng Liu654598b2012-11-08 21:57:20 -0500188 node = rb_next(node);
189 }
190 printk(KERN_DEBUG "\n");
191}
192#else
193#define ext4_es_print_tree(inode)
194#endif
195
Zheng Liu06b0c882013-02-18 00:26:51 -0500196static inline ext4_lblk_t ext4_es_end(struct extent_status *es)
Zheng Liu654598b2012-11-08 21:57:20 -0500197{
Zheng Liu06b0c882013-02-18 00:26:51 -0500198 BUG_ON(es->es_lblk + es->es_len < es->es_lblk);
199 return es->es_lblk + es->es_len - 1;
Zheng Liu654598b2012-11-08 21:57:20 -0500200}
201
202/*
203 * search through the tree for an delayed extent with a given offset. If
204 * it can't be found, try to find next extent.
205 */
206static struct extent_status *__es_tree_search(struct rb_root *root,
Zheng Liu06b0c882013-02-18 00:26:51 -0500207 ext4_lblk_t lblk)
Zheng Liu654598b2012-11-08 21:57:20 -0500208{
209 struct rb_node *node = root->rb_node;
210 struct extent_status *es = NULL;
211
212 while (node) {
213 es = rb_entry(node, struct extent_status, rb_node);
Zheng Liu06b0c882013-02-18 00:26:51 -0500214 if (lblk < es->es_lblk)
Zheng Liu654598b2012-11-08 21:57:20 -0500215 node = node->rb_left;
Zheng Liu06b0c882013-02-18 00:26:51 -0500216 else if (lblk > ext4_es_end(es))
Zheng Liu654598b2012-11-08 21:57:20 -0500217 node = node->rb_right;
218 else
219 return es;
220 }
221
Zheng Liu06b0c882013-02-18 00:26:51 -0500222 if (es && lblk < es->es_lblk)
Zheng Liu654598b2012-11-08 21:57:20 -0500223 return es;
224
Zheng Liu06b0c882013-02-18 00:26:51 -0500225 if (es && lblk > ext4_es_end(es)) {
Zheng Liu654598b2012-11-08 21:57:20 -0500226 node = rb_next(&es->rb_node);
227 return node ? rb_entry(node, struct extent_status, rb_node) :
228 NULL;
229 }
230
231 return NULL;
232}
233
234/*
Zheng Liube401362013-02-18 00:27:26 -0500235 * ext4_es_find_delayed_extent: find the 1st delayed extent covering @es->lblk
Zheng Liu06b0c882013-02-18 00:26:51 -0500236 * if it exists, otherwise, the next extent after @es->lblk.
Zheng Liu654598b2012-11-08 21:57:20 -0500237 *
238 * @inode: the inode which owns delayed extents
Zheng Liube401362013-02-18 00:27:26 -0500239 * @lblk: the offset where we start to search
Zheng Liu654598b2012-11-08 21:57:20 -0500240 * @es: delayed extent that we found
Zheng Liu654598b2012-11-08 21:57:20 -0500241 */
Zheng Liube401362013-02-18 00:27:26 -0500242void ext4_es_find_delayed_extent(struct inode *inode, ext4_lblk_t lblk,
243 struct extent_status *es)
Zheng Liu654598b2012-11-08 21:57:20 -0500244{
245 struct ext4_es_tree *tree = NULL;
246 struct extent_status *es1 = NULL;
247 struct rb_node *node;
Zheng Liu654598b2012-11-08 21:57:20 -0500248
Zheng Liube401362013-02-18 00:27:26 -0500249 BUG_ON(es == NULL);
250 trace_ext4_es_find_delayed_extent_enter(inode, lblk);
Zheng Liu992e9fd2012-11-08 21:57:33 -0500251
Zheng Liu654598b2012-11-08 21:57:20 -0500252 read_lock(&EXT4_I(inode)->i_es_lock);
253 tree = &EXT4_I(inode)->i_es_tree;
254
Zheng Liufdc02122013-02-18 00:26:51 -0500255 /* find extent in cache firstly */
Zheng Liube401362013-02-18 00:27:26 -0500256 es->es_lblk = es->es_len = es->es_pblk = 0;
Zheng Liu654598b2012-11-08 21:57:20 -0500257 if (tree->cache_es) {
258 es1 = tree->cache_es;
Zheng Liube401362013-02-18 00:27:26 -0500259 if (in_range(lblk, es1->es_lblk, es1->es_len)) {
Zheng Liufdc02122013-02-18 00:26:51 -0500260 es_debug("%u cached by [%u/%u) %llu %llx\n",
Zheng Liube401362013-02-18 00:27:26 -0500261 lblk, es1->es_lblk, es1->es_len,
Zheng Liufdc02122013-02-18 00:26:51 -0500262 ext4_es_pblock(es1), ext4_es_status(es1));
Zheng Liu654598b2012-11-08 21:57:20 -0500263 goto out;
264 }
265 }
266
Zheng Liube401362013-02-18 00:27:26 -0500267 es1 = __es_tree_search(&tree->root, lblk);
Zheng Liu654598b2012-11-08 21:57:20 -0500268
269out:
Zheng Liube401362013-02-18 00:27:26 -0500270 if (es1 && !ext4_es_is_delayed(es1)) {
271 while ((node = rb_next(&es1->rb_node)) != NULL) {
272 es1 = rb_entry(node, struct extent_status, rb_node);
273 if (ext4_es_is_delayed(es1))
274 break;
275 }
276 }
277
278 if (es1 && ext4_es_is_delayed(es1)) {
Zheng Liu654598b2012-11-08 21:57:20 -0500279 tree->cache_es = es1;
Zheng Liu06b0c882013-02-18 00:26:51 -0500280 es->es_lblk = es1->es_lblk;
281 es->es_len = es1->es_len;
Zheng Liufdc02122013-02-18 00:26:51 -0500282 es->es_pblk = es1->es_pblk;
Zheng Liu654598b2012-11-08 21:57:20 -0500283 }
284
285 read_unlock(&EXT4_I(inode)->i_es_lock);
Zheng Liu992e9fd2012-11-08 21:57:33 -0500286
Zheng Liu74cd15c2013-02-18 00:32:55 -0500287 ext4_es_lru_add(inode);
Zheng Liube401362013-02-18 00:27:26 -0500288 trace_ext4_es_find_delayed_extent_exit(inode, es);
Zheng Liu654598b2012-11-08 21:57:20 -0500289}
290
291static struct extent_status *
Zheng Liubdedbb72013-02-18 00:32:02 -0500292ext4_es_alloc_extent(struct inode *inode, ext4_lblk_t lblk, ext4_lblk_t len,
293 ext4_fsblk_t pblk)
Zheng Liu654598b2012-11-08 21:57:20 -0500294{
295 struct extent_status *es;
296 es = kmem_cache_alloc(ext4_es_cachep, GFP_ATOMIC);
297 if (es == NULL)
298 return NULL;
Zheng Liu06b0c882013-02-18 00:26:51 -0500299 es->es_lblk = lblk;
300 es->es_len = len;
Zheng Liufdc02122013-02-18 00:26:51 -0500301 es->es_pblk = pblk;
Zheng Liu74cd15c2013-02-18 00:32:55 -0500302
303 /*
304 * We don't count delayed extent because we never try to reclaim them
305 */
Theodore Ts'o24630772013-02-28 23:58:56 -0500306 if (!ext4_es_is_delayed(es)) {
Zheng Liu74cd15c2013-02-18 00:32:55 -0500307 EXT4_I(inode)->i_es_lru_nr++;
Theodore Ts'o1ac64662013-03-02 10:27:46 -0500308 percpu_counter_inc(&EXT4_SB(inode->i_sb)->s_extent_cache_cnt);
Theodore Ts'o24630772013-02-28 23:58:56 -0500309 }
Zheng Liu74cd15c2013-02-18 00:32:55 -0500310
Zheng Liu654598b2012-11-08 21:57:20 -0500311 return es;
312}
313
Zheng Liubdedbb72013-02-18 00:32:02 -0500314static void ext4_es_free_extent(struct inode *inode, struct extent_status *es)
Zheng Liu654598b2012-11-08 21:57:20 -0500315{
Zheng Liu74cd15c2013-02-18 00:32:55 -0500316 /* Decrease the lru counter when this es is not delayed */
317 if (!ext4_es_is_delayed(es)) {
318 BUG_ON(EXT4_I(inode)->i_es_lru_nr == 0);
319 EXT4_I(inode)->i_es_lru_nr--;
Theodore Ts'o1ac64662013-03-02 10:27:46 -0500320 percpu_counter_dec(&EXT4_SB(inode->i_sb)->s_extent_cache_cnt);
Zheng Liu74cd15c2013-02-18 00:32:55 -0500321 }
322
Zheng Liu654598b2012-11-08 21:57:20 -0500323 kmem_cache_free(ext4_es_cachep, es);
324}
325
Zheng Liu06b0c882013-02-18 00:26:51 -0500326/*
327 * Check whether or not two extents can be merged
328 * Condition:
329 * - logical block number is contiguous
Zheng Liufdc02122013-02-18 00:26:51 -0500330 * - physical block number is contiguous
331 * - status is equal
Zheng Liu06b0c882013-02-18 00:26:51 -0500332 */
333static int ext4_es_can_be_merged(struct extent_status *es1,
334 struct extent_status *es2)
335{
Zheng Liufdc02122013-02-18 00:26:51 -0500336 if (ext4_es_status(es1) != ext4_es_status(es2))
337 return 0;
338
Zheng Liubd384362013-03-10 20:48:59 -0400339 if (((__u64) es1->es_len) + es2->es_len > 0xFFFFFFFFULL)
Zheng Liufdc02122013-02-18 00:26:51 -0500340 return 0;
341
Zheng Liubd384362013-03-10 20:48:59 -0400342 if (((__u64) es1->es_lblk) + es1->es_len != es2->es_lblk)
343 return 0;
344
345 if ((ext4_es_is_written(es1) || ext4_es_is_unwritten(es1)) &&
346 (ext4_es_pblock(es1) + es1->es_len == ext4_es_pblock(es2)))
347 return 1;
348
349 if (ext4_es_is_hole(es1))
350 return 1;
351
352 /* we need to check delayed extent is without unwritten status */
353 if (ext4_es_is_delayed(es1) && !ext4_es_is_unwritten(es1))
354 return 1;
355
356 return 0;
Zheng Liu06b0c882013-02-18 00:26:51 -0500357}
358
Zheng Liu654598b2012-11-08 21:57:20 -0500359static struct extent_status *
Zheng Liubdedbb72013-02-18 00:32:02 -0500360ext4_es_try_to_merge_left(struct inode *inode, struct extent_status *es)
Zheng Liu654598b2012-11-08 21:57:20 -0500361{
Zheng Liubdedbb72013-02-18 00:32:02 -0500362 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
Zheng Liu654598b2012-11-08 21:57:20 -0500363 struct extent_status *es1;
364 struct rb_node *node;
365
366 node = rb_prev(&es->rb_node);
367 if (!node)
368 return es;
369
370 es1 = rb_entry(node, struct extent_status, rb_node);
Zheng Liu06b0c882013-02-18 00:26:51 -0500371 if (ext4_es_can_be_merged(es1, es)) {
372 es1->es_len += es->es_len;
Zheng Liu654598b2012-11-08 21:57:20 -0500373 rb_erase(&es->rb_node, &tree->root);
Zheng Liubdedbb72013-02-18 00:32:02 -0500374 ext4_es_free_extent(inode, es);
Zheng Liu654598b2012-11-08 21:57:20 -0500375 es = es1;
376 }
377
378 return es;
379}
380
381static struct extent_status *
Zheng Liubdedbb72013-02-18 00:32:02 -0500382ext4_es_try_to_merge_right(struct inode *inode, struct extent_status *es)
Zheng Liu654598b2012-11-08 21:57:20 -0500383{
Zheng Liubdedbb72013-02-18 00:32:02 -0500384 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
Zheng Liu654598b2012-11-08 21:57:20 -0500385 struct extent_status *es1;
386 struct rb_node *node;
387
388 node = rb_next(&es->rb_node);
389 if (!node)
390 return es;
391
392 es1 = rb_entry(node, struct extent_status, rb_node);
Zheng Liu06b0c882013-02-18 00:26:51 -0500393 if (ext4_es_can_be_merged(es, es1)) {
394 es->es_len += es1->es_len;
Zheng Liu654598b2012-11-08 21:57:20 -0500395 rb_erase(node, &tree->root);
Zheng Liubdedbb72013-02-18 00:32:02 -0500396 ext4_es_free_extent(inode, es1);
Zheng Liu654598b2012-11-08 21:57:20 -0500397 }
398
399 return es;
400}
401
Dmitry Monakhov921f2662013-03-10 21:01:03 -0400402#ifdef ES_AGGRESSIVE_TEST
403static void ext4_es_insert_extent_ext_check(struct inode *inode,
404 struct extent_status *es)
405{
406 struct ext4_ext_path *path = NULL;
407 struct ext4_extent *ex;
408 ext4_lblk_t ee_block;
409 ext4_fsblk_t ee_start;
410 unsigned short ee_len;
411 int depth, ee_status, es_status;
412
413 path = ext4_ext_find_extent(inode, es->es_lblk, NULL);
414 if (IS_ERR(path))
415 return;
416
417 depth = ext_depth(inode);
418 ex = path[depth].p_ext;
419
420 if (ex) {
421
422 ee_block = le32_to_cpu(ex->ee_block);
423 ee_start = ext4_ext_pblock(ex);
424 ee_len = ext4_ext_get_actual_len(ex);
425
426 ee_status = ext4_ext_is_uninitialized(ex) ? 1 : 0;
427 es_status = ext4_es_is_unwritten(es) ? 1 : 0;
428
429 /*
430 * Make sure ex and es are not overlap when we try to insert
431 * a delayed/hole extent.
432 */
433 if (!ext4_es_is_written(es) && !ext4_es_is_unwritten(es)) {
434 if (in_range(es->es_lblk, ee_block, ee_len)) {
435 pr_warn("ES insert assertation failed for "
436 "inode: %lu we can find an extent "
437 "at block [%d/%d/%llu/%c], but we "
438 "want to add an delayed/hole extent "
439 "[%d/%d/%llu/%llx]\n",
440 inode->i_ino, ee_block, ee_len,
441 ee_start, ee_status ? 'u' : 'w',
442 es->es_lblk, es->es_len,
443 ext4_es_pblock(es), ext4_es_status(es));
444 }
445 goto out;
446 }
447
448 /*
449 * We don't check ee_block == es->es_lblk, etc. because es
450 * might be a part of whole extent, vice versa.
451 */
452 if (es->es_lblk < ee_block ||
453 ext4_es_pblock(es) != ee_start + es->es_lblk - ee_block) {
454 pr_warn("ES insert assertation failed for inode: %lu "
455 "ex_status [%d/%d/%llu/%c] != "
456 "es_status [%d/%d/%llu/%c]\n", inode->i_ino,
457 ee_block, ee_len, ee_start,
458 ee_status ? 'u' : 'w', es->es_lblk, es->es_len,
459 ext4_es_pblock(es), es_status ? 'u' : 'w');
460 goto out;
461 }
462
463 if (ee_status ^ es_status) {
464 pr_warn("ES insert assertation failed for inode: %lu "
465 "ex_status [%d/%d/%llu/%c] != "
466 "es_status [%d/%d/%llu/%c]\n", inode->i_ino,
467 ee_block, ee_len, ee_start,
468 ee_status ? 'u' : 'w', es->es_lblk, es->es_len,
469 ext4_es_pblock(es), es_status ? 'u' : 'w');
470 }
471 } else {
472 /*
473 * We can't find an extent on disk. So we need to make sure
474 * that we don't want to add an written/unwritten extent.
475 */
476 if (!ext4_es_is_delayed(es) && !ext4_es_is_hole(es)) {
477 pr_warn("ES insert assertation failed for inode: %lu "
478 "can't find an extent at block %d but we want "
479 "to add an written/unwritten extent "
480 "[%d/%d/%llu/%llx]\n", inode->i_ino,
481 es->es_lblk, es->es_lblk, es->es_len,
482 ext4_es_pblock(es), ext4_es_status(es));
483 }
484 }
485out:
486 if (path) {
487 ext4_ext_drop_refs(path);
488 kfree(path);
489 }
490}
491
492static void ext4_es_insert_extent_ind_check(struct inode *inode,
493 struct extent_status *es)
494{
495 struct ext4_map_blocks map;
496 int retval;
497
498 /*
499 * Here we call ext4_ind_map_blocks to lookup a block mapping because
500 * 'Indirect' structure is defined in indirect.c. So we couldn't
501 * access direct/indirect tree from outside. It is too dirty to define
502 * this function in indirect.c file.
503 */
504
505 map.m_lblk = es->es_lblk;
506 map.m_len = es->es_len;
507
508 retval = ext4_ind_map_blocks(NULL, inode, &map, 0);
509 if (retval > 0) {
510 if (ext4_es_is_delayed(es) || ext4_es_is_hole(es)) {
511 /*
512 * We want to add a delayed/hole extent but this
513 * block has been allocated.
514 */
515 pr_warn("ES insert assertation failed for inode: %lu "
516 "We can find blocks but we want to add a "
517 "delayed/hole extent [%d/%d/%llu/%llx]\n",
518 inode->i_ino, es->es_lblk, es->es_len,
519 ext4_es_pblock(es), ext4_es_status(es));
520 return;
521 } else if (ext4_es_is_written(es)) {
522 if (retval != es->es_len) {
523 pr_warn("ES insert assertation failed for "
524 "inode: %lu retval %d != es_len %d\n",
525 inode->i_ino, retval, es->es_len);
526 return;
527 }
528 if (map.m_pblk != ext4_es_pblock(es)) {
529 pr_warn("ES insert assertation failed for "
530 "inode: %lu m_pblk %llu != "
531 "es_pblk %llu\n",
532 inode->i_ino, map.m_pblk,
533 ext4_es_pblock(es));
534 return;
535 }
536 } else {
537 /*
538 * We don't need to check unwritten extent because
539 * indirect-based file doesn't have it.
540 */
541 BUG_ON(1);
542 }
543 } else if (retval == 0) {
544 if (ext4_es_is_written(es)) {
545 pr_warn("ES insert assertation failed for inode: %lu "
546 "We can't find the block but we want to add "
547 "an written extent [%d/%d/%llu/%llx]\n",
548 inode->i_ino, es->es_lblk, es->es_len,
549 ext4_es_pblock(es), ext4_es_status(es));
550 return;
551 }
552 }
553}
554
555static inline void ext4_es_insert_extent_check(struct inode *inode,
556 struct extent_status *es)
557{
558 /*
559 * We don't need to worry about the race condition because
560 * caller takes i_data_sem locking.
561 */
562 BUG_ON(!rwsem_is_locked(&EXT4_I(inode)->i_data_sem));
563 if (ext4_test_inode_flag(inode, EXT4_INODE_EXTENTS))
564 ext4_es_insert_extent_ext_check(inode, es);
565 else
566 ext4_es_insert_extent_ind_check(inode, es);
567}
568#else
569static inline void ext4_es_insert_extent_check(struct inode *inode,
570 struct extent_status *es)
571{
572}
573#endif
574
Zheng Liubdedbb72013-02-18 00:32:02 -0500575static int __es_insert_extent(struct inode *inode, struct extent_status *newes)
Zheng Liu654598b2012-11-08 21:57:20 -0500576{
Zheng Liubdedbb72013-02-18 00:32:02 -0500577 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
Zheng Liu654598b2012-11-08 21:57:20 -0500578 struct rb_node **p = &tree->root.rb_node;
579 struct rb_node *parent = NULL;
580 struct extent_status *es;
Zheng Liu654598b2012-11-08 21:57:20 -0500581
582 while (*p) {
583 parent = *p;
584 es = rb_entry(parent, struct extent_status, rb_node);
585
Zheng Liu06b0c882013-02-18 00:26:51 -0500586 if (newes->es_lblk < es->es_lblk) {
587 if (ext4_es_can_be_merged(newes, es)) {
588 /*
589 * Here we can modify es_lblk directly
590 * because it isn't overlapped.
591 */
592 es->es_lblk = newes->es_lblk;
593 es->es_len += newes->es_len;
Zheng Liufdc02122013-02-18 00:26:51 -0500594 if (ext4_es_is_written(es) ||
595 ext4_es_is_unwritten(es))
596 ext4_es_store_pblock(es,
597 newes->es_pblk);
Zheng Liubdedbb72013-02-18 00:32:02 -0500598 es = ext4_es_try_to_merge_left(inode, es);
Zheng Liu654598b2012-11-08 21:57:20 -0500599 goto out;
600 }
601 p = &(*p)->rb_left;
Zheng Liu06b0c882013-02-18 00:26:51 -0500602 } else if (newes->es_lblk > ext4_es_end(es)) {
603 if (ext4_es_can_be_merged(es, newes)) {
604 es->es_len += newes->es_len;
Zheng Liubdedbb72013-02-18 00:32:02 -0500605 es = ext4_es_try_to_merge_right(inode, es);
Zheng Liu654598b2012-11-08 21:57:20 -0500606 goto out;
607 }
608 p = &(*p)->rb_right;
609 } else {
Zheng Liu06b0c882013-02-18 00:26:51 -0500610 BUG_ON(1);
611 return -EINVAL;
Zheng Liu654598b2012-11-08 21:57:20 -0500612 }
613 }
614
Zheng Liubdedbb72013-02-18 00:32:02 -0500615 es = ext4_es_alloc_extent(inode, newes->es_lblk, newes->es_len,
Zheng Liufdc02122013-02-18 00:26:51 -0500616 newes->es_pblk);
Zheng Liu654598b2012-11-08 21:57:20 -0500617 if (!es)
618 return -ENOMEM;
619 rb_link_node(&es->rb_node, parent, p);
620 rb_insert_color(&es->rb_node, &tree->root);
621
622out:
623 tree->cache_es = es;
624 return 0;
625}
626
627/*
Zheng Liu06b0c882013-02-18 00:26:51 -0500628 * ext4_es_insert_extent() adds a space to a extent status tree.
Zheng Liu654598b2012-11-08 21:57:20 -0500629 *
630 * ext4_es_insert_extent is called by ext4_da_write_begin and
631 * ext4_es_remove_extent.
632 *
633 * Return 0 on success, error code on failure.
634 */
Zheng Liu06b0c882013-02-18 00:26:51 -0500635int ext4_es_insert_extent(struct inode *inode, ext4_lblk_t lblk,
Zheng Liufdc02122013-02-18 00:26:51 -0500636 ext4_lblk_t len, ext4_fsblk_t pblk,
637 unsigned long long status)
Zheng Liu654598b2012-11-08 21:57:20 -0500638{
Zheng Liu06b0c882013-02-18 00:26:51 -0500639 struct extent_status newes;
640 ext4_lblk_t end = lblk + len - 1;
Zheng Liu654598b2012-11-08 21:57:20 -0500641 int err = 0;
642
Zheng Liufdc02122013-02-18 00:26:51 -0500643 es_debug("add [%u/%u) %llu %llx to extent status tree of inode %lu\n",
644 lblk, len, pblk, status, inode->i_ino);
Zheng Liu06b0c882013-02-18 00:26:51 -0500645
Eryu Guand4381472013-02-22 15:27:47 -0500646 if (!len)
647 return 0;
648
Zheng Liu06b0c882013-02-18 00:26:51 -0500649 BUG_ON(end < lblk);
650
651 newes.es_lblk = lblk;
652 newes.es_len = len;
Zheng Liufdc02122013-02-18 00:26:51 -0500653 ext4_es_store_pblock(&newes, pblk);
654 ext4_es_store_status(&newes, status);
655 trace_ext4_es_insert_extent(inode, &newes);
Zheng Liu654598b2012-11-08 21:57:20 -0500656
Dmitry Monakhov921f2662013-03-10 21:01:03 -0400657 ext4_es_insert_extent_check(inode, &newes);
658
Zheng Liu654598b2012-11-08 21:57:20 -0500659 write_lock(&EXT4_I(inode)->i_es_lock);
Zheng Liubdedbb72013-02-18 00:32:02 -0500660 err = __es_remove_extent(inode, lblk, end);
Zheng Liu06b0c882013-02-18 00:26:51 -0500661 if (err != 0)
662 goto error;
Zheng Liubdedbb72013-02-18 00:32:02 -0500663 err = __es_insert_extent(inode, &newes);
Zheng Liu06b0c882013-02-18 00:26:51 -0500664
665error:
Zheng Liu654598b2012-11-08 21:57:20 -0500666 write_unlock(&EXT4_I(inode)->i_es_lock);
667
Zheng Liu74cd15c2013-02-18 00:32:55 -0500668 ext4_es_lru_add(inode);
Zheng Liu654598b2012-11-08 21:57:20 -0500669 ext4_es_print_tree(inode);
670
671 return err;
672}
673
Zheng Liud100eef2013-02-18 00:29:59 -0500674/*
675 * ext4_es_lookup_extent() looks up an extent in extent status tree.
676 *
677 * ext4_es_lookup_extent is called by ext4_map_blocks/ext4_da_map_blocks.
678 *
679 * Return: 1 on found, 0 on not
680 */
681int ext4_es_lookup_extent(struct inode *inode, ext4_lblk_t lblk,
682 struct extent_status *es)
683{
684 struct ext4_es_tree *tree;
685 struct extent_status *es1 = NULL;
686 struct rb_node *node;
687 int found = 0;
688
689 trace_ext4_es_lookup_extent_enter(inode, lblk);
690 es_debug("lookup extent in block %u\n", lblk);
691
692 tree = &EXT4_I(inode)->i_es_tree;
693 read_lock(&EXT4_I(inode)->i_es_lock);
694
695 /* find extent in cache firstly */
696 es->es_lblk = es->es_len = es->es_pblk = 0;
697 if (tree->cache_es) {
698 es1 = tree->cache_es;
699 if (in_range(lblk, es1->es_lblk, es1->es_len)) {
700 es_debug("%u cached by [%u/%u)\n",
701 lblk, es1->es_lblk, es1->es_len);
702 found = 1;
703 goto out;
704 }
705 }
706
707 node = tree->root.rb_node;
708 while (node) {
709 es1 = rb_entry(node, struct extent_status, rb_node);
710 if (lblk < es1->es_lblk)
711 node = node->rb_left;
712 else if (lblk > ext4_es_end(es1))
713 node = node->rb_right;
714 else {
715 found = 1;
716 break;
717 }
718 }
719
720out:
721 if (found) {
722 BUG_ON(!es1);
723 es->es_lblk = es1->es_lblk;
724 es->es_len = es1->es_len;
725 es->es_pblk = es1->es_pblk;
726 }
727
728 read_unlock(&EXT4_I(inode)->i_es_lock);
729
Zheng Liu74cd15c2013-02-18 00:32:55 -0500730 ext4_es_lru_add(inode);
Zheng Liud100eef2013-02-18 00:29:59 -0500731 trace_ext4_es_lookup_extent_exit(inode, es, found);
732 return found;
733}
734
Zheng Liubdedbb72013-02-18 00:32:02 -0500735static int __es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
736 ext4_lblk_t end)
Zheng Liu654598b2012-11-08 21:57:20 -0500737{
Zheng Liubdedbb72013-02-18 00:32:02 -0500738 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
Zheng Liu654598b2012-11-08 21:57:20 -0500739 struct rb_node *node;
Zheng Liu654598b2012-11-08 21:57:20 -0500740 struct extent_status *es;
741 struct extent_status orig_es;
Zheng Liu06b0c882013-02-18 00:26:51 -0500742 ext4_lblk_t len1, len2;
Zheng Liufdc02122013-02-18 00:26:51 -0500743 ext4_fsblk_t block;
Zheng Liu654598b2012-11-08 21:57:20 -0500744 int err = 0;
745
Zheng Liu06b0c882013-02-18 00:26:51 -0500746 es = __es_tree_search(&tree->root, lblk);
Zheng Liu654598b2012-11-08 21:57:20 -0500747 if (!es)
748 goto out;
Zheng Liu06b0c882013-02-18 00:26:51 -0500749 if (es->es_lblk > end)
Zheng Liu654598b2012-11-08 21:57:20 -0500750 goto out;
751
752 /* Simply invalidate cache_es. */
753 tree->cache_es = NULL;
754
Zheng Liu06b0c882013-02-18 00:26:51 -0500755 orig_es.es_lblk = es->es_lblk;
756 orig_es.es_len = es->es_len;
Zheng Liufdc02122013-02-18 00:26:51 -0500757 orig_es.es_pblk = es->es_pblk;
758
Zheng Liu06b0c882013-02-18 00:26:51 -0500759 len1 = lblk > es->es_lblk ? lblk - es->es_lblk : 0;
760 len2 = ext4_es_end(es) > end ? ext4_es_end(es) - end : 0;
Zheng Liu654598b2012-11-08 21:57:20 -0500761 if (len1 > 0)
Zheng Liu06b0c882013-02-18 00:26:51 -0500762 es->es_len = len1;
Zheng Liu654598b2012-11-08 21:57:20 -0500763 if (len2 > 0) {
764 if (len1 > 0) {
Zheng Liu06b0c882013-02-18 00:26:51 -0500765 struct extent_status newes;
766
767 newes.es_lblk = end + 1;
768 newes.es_len = len2;
Zheng Liufdc02122013-02-18 00:26:51 -0500769 if (ext4_es_is_written(&orig_es) ||
770 ext4_es_is_unwritten(&orig_es)) {
771 block = ext4_es_pblock(&orig_es) +
772 orig_es.es_len - len2;
773 ext4_es_store_pblock(&newes, block);
774 }
775 ext4_es_store_status(&newes, ext4_es_status(&orig_es));
Zheng Liubdedbb72013-02-18 00:32:02 -0500776 err = __es_insert_extent(inode, &newes);
Zheng Liu654598b2012-11-08 21:57:20 -0500777 if (err) {
Zheng Liu06b0c882013-02-18 00:26:51 -0500778 es->es_lblk = orig_es.es_lblk;
779 es->es_len = orig_es.es_len;
Zheng Liu654598b2012-11-08 21:57:20 -0500780 goto out;
781 }
782 } else {
Zheng Liu06b0c882013-02-18 00:26:51 -0500783 es->es_lblk = end + 1;
784 es->es_len = len2;
Zheng Liufdc02122013-02-18 00:26:51 -0500785 if (ext4_es_is_written(es) ||
786 ext4_es_is_unwritten(es)) {
787 block = orig_es.es_pblk + orig_es.es_len - len2;
788 ext4_es_store_pblock(es, block);
789 }
Zheng Liu654598b2012-11-08 21:57:20 -0500790 }
791 goto out;
792 }
793
794 if (len1 > 0) {
795 node = rb_next(&es->rb_node);
796 if (node)
797 es = rb_entry(node, struct extent_status, rb_node);
798 else
799 es = NULL;
800 }
801
Zheng Liu06b0c882013-02-18 00:26:51 -0500802 while (es && ext4_es_end(es) <= end) {
Zheng Liu654598b2012-11-08 21:57:20 -0500803 node = rb_next(&es->rb_node);
804 rb_erase(&es->rb_node, &tree->root);
Zheng Liubdedbb72013-02-18 00:32:02 -0500805 ext4_es_free_extent(inode, es);
Zheng Liu654598b2012-11-08 21:57:20 -0500806 if (!node) {
807 es = NULL;
808 break;
809 }
810 es = rb_entry(node, struct extent_status, rb_node);
811 }
812
Zheng Liu06b0c882013-02-18 00:26:51 -0500813 if (es && es->es_lblk < end + 1) {
Zheng Liufdc02122013-02-18 00:26:51 -0500814 ext4_lblk_t orig_len = es->es_len;
815
Zheng Liu06b0c882013-02-18 00:26:51 -0500816 len1 = ext4_es_end(es) - end;
817 es->es_lblk = end + 1;
818 es->es_len = len1;
Zheng Liufdc02122013-02-18 00:26:51 -0500819 if (ext4_es_is_written(es) || ext4_es_is_unwritten(es)) {
820 block = es->es_pblk + orig_len - len1;
821 ext4_es_store_pblock(es, block);
822 }
Zheng Liu654598b2012-11-08 21:57:20 -0500823 }
824
825out:
Zheng Liu06b0c882013-02-18 00:26:51 -0500826 return err;
827}
828
829/*
830 * ext4_es_remove_extent() removes a space from a extent status tree.
831 *
832 * Return 0 on success, error code on failure.
833 */
834int ext4_es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
835 ext4_lblk_t len)
836{
Zheng Liu06b0c882013-02-18 00:26:51 -0500837 ext4_lblk_t end;
838 int err = 0;
839
840 trace_ext4_es_remove_extent(inode, lblk, len);
841 es_debug("remove [%u/%u) from extent status tree of inode %lu\n",
842 lblk, len, inode->i_ino);
843
Eryu Guand4381472013-02-22 15:27:47 -0500844 if (!len)
845 return err;
846
Zheng Liu06b0c882013-02-18 00:26:51 -0500847 end = lblk + len - 1;
848 BUG_ON(end < lblk);
849
Zheng Liu06b0c882013-02-18 00:26:51 -0500850 write_lock(&EXT4_I(inode)->i_es_lock);
Zheng Liubdedbb72013-02-18 00:32:02 -0500851 err = __es_remove_extent(inode, lblk, end);
Zheng Liu654598b2012-11-08 21:57:20 -0500852 write_unlock(&EXT4_I(inode)->i_es_lock);
853 ext4_es_print_tree(inode);
854 return err;
855}
Zheng Liu74cd15c2013-02-18 00:32:55 -0500856
Zheng Liuadb23552013-03-10 21:13:05 -0400857int ext4_es_zeroout(struct inode *inode, struct ext4_extent *ex)
858{
859 ext4_lblk_t ee_block;
860 ext4_fsblk_t ee_pblock;
861 unsigned int ee_len;
862
863 ee_block = le32_to_cpu(ex->ee_block);
864 ee_len = ext4_ext_get_actual_len(ex);
865 ee_pblock = ext4_ext_pblock(ex);
866
867 if (ee_len == 0)
868 return 0;
869
870 return ext4_es_insert_extent(inode, ee_block, ee_len, ee_pblock,
871 EXTENT_STATUS_WRITTEN);
872}
873
Zheng Liu74cd15c2013-02-18 00:32:55 -0500874static int ext4_es_shrink(struct shrinker *shrink, struct shrink_control *sc)
875{
876 struct ext4_sb_info *sbi = container_of(shrink,
877 struct ext4_sb_info, s_es_shrinker);
878 struct ext4_inode_info *ei;
879 struct list_head *cur, *tmp, scanned;
880 int nr_to_scan = sc->nr_to_scan;
881 int ret, nr_shrunk = 0;
882
Theodore Ts'o1ac64662013-03-02 10:27:46 -0500883 ret = percpu_counter_read_positive(&sbi->s_extent_cache_cnt);
Theodore Ts'o24630772013-02-28 23:58:56 -0500884 trace_ext4_es_shrink_enter(sbi->s_sb, nr_to_scan, ret);
Zheng Liu74cd15c2013-02-18 00:32:55 -0500885
886 if (!nr_to_scan)
Theodore Ts'o24630772013-02-28 23:58:56 -0500887 return ret;
Zheng Liu74cd15c2013-02-18 00:32:55 -0500888
889 INIT_LIST_HEAD(&scanned);
890
891 spin_lock(&sbi->s_es_lru_lock);
892 list_for_each_safe(cur, tmp, &sbi->s_es_lru) {
893 list_move_tail(cur, &scanned);
894
895 ei = list_entry(cur, struct ext4_inode_info, i_es_lru);
896
897 read_lock(&ei->i_es_lock);
898 if (ei->i_es_lru_nr == 0) {
899 read_unlock(&ei->i_es_lock);
900 continue;
901 }
902 read_unlock(&ei->i_es_lock);
903
904 write_lock(&ei->i_es_lock);
905 ret = __es_try_to_reclaim_extents(ei, nr_to_scan);
906 write_unlock(&ei->i_es_lock);
907
908 nr_shrunk += ret;
909 nr_to_scan -= ret;
910 if (nr_to_scan == 0)
911 break;
912 }
913 list_splice_tail(&scanned, &sbi->s_es_lru);
914 spin_unlock(&sbi->s_es_lru_lock);
Zheng Liu74cd15c2013-02-18 00:32:55 -0500915
Theodore Ts'o1ac64662013-03-02 10:27:46 -0500916 ret = percpu_counter_read_positive(&sbi->s_extent_cache_cnt);
Theodore Ts'o24630772013-02-28 23:58:56 -0500917 trace_ext4_es_shrink_exit(sbi->s_sb, nr_shrunk, ret);
918 return ret;
Zheng Liu74cd15c2013-02-18 00:32:55 -0500919}
920
921void ext4_es_register_shrinker(struct super_block *sb)
922{
923 struct ext4_sb_info *sbi;
924
925 sbi = EXT4_SB(sb);
926 INIT_LIST_HEAD(&sbi->s_es_lru);
927 spin_lock_init(&sbi->s_es_lru_lock);
928 sbi->s_es_shrinker.shrink = ext4_es_shrink;
929 sbi->s_es_shrinker.seeks = DEFAULT_SEEKS;
930 register_shrinker(&sbi->s_es_shrinker);
931}
932
933void ext4_es_unregister_shrinker(struct super_block *sb)
934{
935 unregister_shrinker(&EXT4_SB(sb)->s_es_shrinker);
936}
937
938void ext4_es_lru_add(struct inode *inode)
939{
940 struct ext4_inode_info *ei = EXT4_I(inode);
941 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
942
943 spin_lock(&sbi->s_es_lru_lock);
944 if (list_empty(&ei->i_es_lru))
945 list_add_tail(&ei->i_es_lru, &sbi->s_es_lru);
946 else
947 list_move_tail(&ei->i_es_lru, &sbi->s_es_lru);
948 spin_unlock(&sbi->s_es_lru_lock);
949}
950
951void ext4_es_lru_del(struct inode *inode)
952{
953 struct ext4_inode_info *ei = EXT4_I(inode);
954 struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
955
956 spin_lock(&sbi->s_es_lru_lock);
957 if (!list_empty(&ei->i_es_lru))
958 list_del_init(&ei->i_es_lru);
959 spin_unlock(&sbi->s_es_lru_lock);
960}
961
Zheng Liu74cd15c2013-02-18 00:32:55 -0500962static int __es_try_to_reclaim_extents(struct ext4_inode_info *ei,
963 int nr_to_scan)
964{
965 struct inode *inode = &ei->vfs_inode;
966 struct ext4_es_tree *tree = &ei->i_es_tree;
967 struct rb_node *node;
968 struct extent_status *es;
969 int nr_shrunk = 0;
970
971 if (ei->i_es_lru_nr == 0)
972 return 0;
973
974 node = rb_first(&tree->root);
975 while (node != NULL) {
976 es = rb_entry(node, struct extent_status, rb_node);
977 node = rb_next(&es->rb_node);
978 /*
979 * We can't reclaim delayed extent from status tree because
980 * fiemap, bigallic, and seek_data/hole need to use it.
981 */
982 if (!ext4_es_is_delayed(es)) {
983 rb_erase(&es->rb_node, &tree->root);
984 ext4_es_free_extent(inode, es);
985 nr_shrunk++;
986 if (--nr_to_scan == 0)
987 break;
988 }
989 }
990 tree->cache_es = NULL;
991 return nr_shrunk;
992}