| blob | baed103eecf371c69376a75f5b5ebfd35c62f37e |
1 ext4: generalize extents status tree search functions
3 From: Eric Whitney <enwlinux@gmail.com>
5 Ext4 contains a few functions that are used to search for delayed
6 extents or blocks in the extents status tree. Rather than duplicate
7 code to add new functions to search for extents with different status
8 values, such as written or a combination of delayed and unwritten,
9 generalize the existing code to search for caller-specified extents
10 status values. Also, move this code into extents_status.c where it
11 is better associated with the data structures it operates upon, and
12 where it can be more readily used to implement new extents status tree
13 functions that might want a broader scope for i_es_lock.
15 Three missing static specifiers in RFC version of patch reported and
16 fixed by Fengguang Wu <fengguang.wu@intel.com>.
18 Signed-off-by: Eric Whitney <enwlinux@gmail.com>
19 Signed-off-by: Theodore Ts'o <tytso@mit.edu>
20 ---
21 fs/ext4/ext4.h | 4 --
22 fs/ext4/extents.c | 52 ++++------------
23 fs/ext4/extents_status.c | 149 ++++++++++++++++++++++++++++++++++++++------
24 fs/ext4/extents_status.h | 13 +++-
25 fs/ext4/inode.c | 17 ++---
26 include/trace/events/ext4.h | 4 +-
27 6 files changed, 165 insertions(+), 74 deletions(-)
29 diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
30 index caff935fbeb8..ad2c215720be 100644
31 --- a/fs/ext4/ext4.h
32 +++ b/fs/ext4/ext4.h
33 @@ -3142,10 +3142,6 @@ extern struct ext4_ext_path *ext4_find_extent(struct inode *, ext4_lblk_t,
34 int flags);
35 extern void ext4_ext_drop_refs(struct ext4_ext_path *);
36 extern int ext4_ext_check_inode(struct inode *inode);
37 -extern int ext4_find_delalloc_range(struct inode *inode,
38 - ext4_lblk_t lblk_start,
39 - ext4_lblk_t lblk_end);
40 -extern int ext4_find_delalloc_cluster(struct inode *inode, ext4_lblk_t lblk);
41 extern ext4_lblk_t ext4_ext_next_allocated_block(struct ext4_ext_path *path);
42 extern int ext4_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo,
43 __u64 start, __u64 len);
44 diff --git a/fs/ext4/extents.c b/fs/ext4/extents.c
45 index 72a361d5ef74..95796f00e4e6 100644
46 --- a/fs/ext4/extents.c
47 +++ b/fs/ext4/extents.c
48 @@ -2351,8 +2351,8 @@ ext4_ext_put_gap_in_cache(struct inode *inode, ext4_lblk_t hole_start,
49 {
50 struct extent_status es;
52 - ext4_es_find_delayed_extent_range(inode, hole_start,
53 - hole_start + hole_len - 1, &es);
54 + ext4_es_find_extent_range(inode, &ext4_es_is_delayed, hole_start,
55 + hole_start + hole_len - 1, &es);
56 if (es.es_len) {
57 /* There's delayed extent containing lblock? */
58 if (es.es_lblk <= hole_start)
59 @@ -3820,39 +3820,6 @@ static int check_eofblocks_fl(handle_t *handle, struct inode *inode,
60 }
62 /**
63 - * ext4_find_delalloc_range: find delayed allocated block in the given range.
64 - *
65 - * Return 1 if there is a delalloc block in the range, otherwise 0.
66 - */
67 -int ext4_find_delalloc_range(struct inode *inode,
68 - ext4_lblk_t lblk_start,
69 - ext4_lblk_t lblk_end)
70 -{
71 - struct extent_status es;
72 -
73 - ext4_es_find_delayed_extent_range(inode, lblk_start, lblk_end, &es);
74 - if (es.es_len == 0)
75 - return 0; /* there is no delay extent in this tree */
76 - else if (es.es_lblk <= lblk_start &&
77 - lblk_start < es.es_lblk + es.es_len)
78 - return 1;
79 - else if (lblk_start <= es.es_lblk && es.es_lblk <= lblk_end)
80 - return 1;
81 - else
82 - return 0;
83 -}
84 -
85 -int ext4_find_delalloc_cluster(struct inode *inode, ext4_lblk_t lblk)
86 -{
87 - struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
88 - ext4_lblk_t lblk_start, lblk_end;
89 - lblk_start = EXT4_LBLK_CMASK(sbi, lblk);
90 - lblk_end = lblk_start + sbi->s_cluster_ratio - 1;
91 -
92 - return ext4_find_delalloc_range(inode, lblk_start, lblk_end);
93 -}
94 -
95 -/**
96 * Determines how many complete clusters (out of those specified by the 'map')
97 * are under delalloc and were reserved quota for.
98 * This function is called when we are writing out the blocks that were
99 @@ -3910,7 +3877,8 @@ get_reserved_cluster_alloc(struct inode *inode, ext4_lblk_t lblk_start,
100 lblk_from = EXT4_LBLK_CMASK(sbi, lblk_start);
101 lblk_to = lblk_from + c_offset - 1;
103 - if (ext4_find_delalloc_range(inode, lblk_from, lblk_to))
104 + if (ext4_es_scan_range(inode, &ext4_es_is_delayed, lblk_from,
105 + lblk_to))
106 allocated_clusters--;
107 }
109 @@ -3920,7 +3888,8 @@ get_reserved_cluster_alloc(struct inode *inode, ext4_lblk_t lblk_start,
110 lblk_from = lblk_start + num_blks;
111 lblk_to = lblk_from + (sbi->s_cluster_ratio - c_offset) - 1;
113 - if (ext4_find_delalloc_range(inode, lblk_from, lblk_to))
114 + if (ext4_es_scan_range(inode, &ext4_es_is_delayed, lblk_from,
115 + lblk_to))
116 allocated_clusters--;
117 }
119 @@ -5075,8 +5044,10 @@ static int ext4_find_delayed_extent(struct inode *inode,
120 ext4_lblk_t block, next_del;
122 if (newes->es_pblk == 0) {
123 - ext4_es_find_delayed_extent_range(inode, newes->es_lblk,
124 - newes->es_lblk + newes->es_len - 1, &es);
125 + ext4_es_find_extent_range(inode, &ext4_es_is_delayed,
126 + newes->es_lblk,
127 + newes->es_lblk + newes->es_len - 1,
128 + &es);
130 /*
131 * No extent in extent-tree contains block @newes->es_pblk,
132 @@ -5097,7 +5068,8 @@ static int ext4_find_delayed_extent(struct inode *inode,
133 }
135 block = newes->es_lblk + newes->es_len;
136 - ext4_es_find_delayed_extent_range(inode, block, EXT_MAX_BLOCKS, &es);
137 + ext4_es_find_extent_range(inode, &ext4_es_is_delayed, block,
138 + EXT_MAX_BLOCKS, &es);
139 if (es.es_len == 0)
140 next_del = EXT_MAX_BLOCKS;
141 else
142 diff --git a/fs/ext4/extents_status.c b/fs/ext4/extents_status.c
143 index c4e6fb15101b..8530fbd3012d 100644
144 --- a/fs/ext4/extents_status.c
145 +++ b/fs/ext4/extents_status.c
146 @@ -233,30 +233,38 @@ static struct extent_status *__es_tree_search(struct rb_root *root,
147 }
149 /*
150 - * ext4_es_find_delayed_extent_range: find the 1st delayed extent covering
151 - * @es->lblk if it exists, otherwise, the next extent after @es->lblk.
152 + * ext4_es_find_extent_range - find extent with specified status within block
153 + * range or next extent following block range in
154 + * extents status tree
155 *
156 - * @inode: the inode which owns delayed extents
157 - * @lblk: the offset where we start to search
158 - * @end: the offset where we stop to search
159 - * @es: delayed extent that we found
160 + * @inode - file containing the range
161 + * @matching_fn - pointer to function that matches extents with desired status
162 + * @lblk - logical block defining start of range
163 + * @end - logical block defining end of range
164 + * @es - extent found, if any
165 + *
166 + * Find the first extent within the block range specified by @lblk and @end
167 + * in the extents status tree that satisfies @matching_fn. If a match
168 + * is found, it's returned in @es. If not, and a matching extent is found
169 + * beyond the block range, it's returned in @es. If no match is found, an
170 + * extent is returned in @es whose es_lblk, es_len, and es_pblk components
171 + * are 0.
172 */
173 -void ext4_es_find_delayed_extent_range(struct inode *inode,
174 - ext4_lblk_t lblk, ext4_lblk_t end,
175 - struct extent_status *es)
176 +static void __es_find_extent_range(struct inode *inode,
177 + int (*matching_fn)(struct extent_status *es),
178 + ext4_lblk_t lblk, ext4_lblk_t end,
179 + struct extent_status *es)
180 {
181 struct ext4_es_tree *tree = NULL;
182 struct extent_status *es1 = NULL;
183 struct rb_node *node;
185 - BUG_ON(es == NULL);
186 - BUG_ON(end < lblk);
187 - trace_ext4_es_find_delayed_extent_range_enter(inode, lblk);
188 + WARN_ON(es == NULL);
189 + WARN_ON(end < lblk);
191 - read_lock(&EXT4_I(inode)->i_es_lock);
192 tree = &EXT4_I(inode)->i_es_tree;
194 - /* find extent in cache firstly */
195 + /* see if the extent has been cached */
196 es->es_lblk = es->es_len = es->es_pblk = 0;
197 if (tree->cache_es) {
198 es1 = tree->cache_es;
199 @@ -271,28 +279,133 @@ void ext4_es_find_delayed_extent_range(struct inode *inode,
200 es1 = __es_tree_search(&tree->root, lblk);
202 out:
203 - if (es1 && !ext4_es_is_delayed(es1)) {
204 + if (es1 && !matching_fn(es1)) {
205 while ((node = rb_next(&es1->rb_node)) != NULL) {
206 es1 = rb_entry(node, struct extent_status, rb_node);
207 if (es1->es_lblk > end) {
208 es1 = NULL;
209 break;
210 }
211 - if (ext4_es_is_delayed(es1))
212 + if (matching_fn(es1))
213 break;
214 }
215 }
217 - if (es1 && ext4_es_is_delayed(es1)) {
218 + if (es1 && matching_fn(es1)) {
219 tree->cache_es = es1;
220 es->es_lblk = es1->es_lblk;
221 es->es_len = es1->es_len;
222 es->es_pblk = es1->es_pblk;
223 }
225 +}
226 +
227 +/*
228 + * Locking for __es_find_extent_range() for external use
229 + */
230 +void ext4_es_find_extent_range(struct inode *inode,
231 + int (*matching_fn)(struct extent_status *es),
232 + ext4_lblk_t lblk, ext4_lblk_t end,
233 + struct extent_status *es)
234 +{
235 + trace_ext4_es_find_extent_range_enter(inode, lblk);
236 +
237 + read_lock(&EXT4_I(inode)->i_es_lock);
238 + __es_find_extent_range(inode, matching_fn, lblk, end, es);
239 + read_unlock(&EXT4_I(inode)->i_es_lock);
240 +
241 + trace_ext4_es_find_extent_range_exit(inode, es);
242 +}
243 +
244 +/*
245 + * __es_scan_range - search block range for block with specified status
246 + * in extents status tree
247 + *
248 + * @inode - file containing the range
249 + * @matching_fn - pointer to function that matches extents with desired status
250 + * @lblk - logical block defining start of range
251 + * @end - logical block defining end of range
252 + *
253 + * Returns true if at least one block in the specified block range satisfies
254 + * the criterion specified by @matching_fn, and false if not. If at least
255 + * one extent has the specified status, then there is at least one block
256 + * in the cluster with that status. Should only be called by code that has
257 + * taken i_es_lock.
258 + */
259 +static bool __es_scan_range(struct inode *inode,
260 + int (*matching_fn)(struct extent_status *es),
261 + ext4_lblk_t start, ext4_lblk_t end)
262 +{
263 + struct extent_status es;
264 +
265 + __es_find_extent_range(inode, matching_fn, start, end, &es);
266 + if (es.es_len == 0)
267 + return false; /* no matching extent in the tree */
268 + else if (es.es_lblk <= start &&
269 + start < es.es_lblk + es.es_len)
270 + return true;
271 + else if (start <= es.es_lblk && es.es_lblk <= end)
272 + return true;
273 + else
274 + return false;
275 +}
276 +/*
277 + * Locking for __es_scan_range() for external use
278 + */
279 +bool ext4_es_scan_range(struct inode *inode,
280 + int (*matching_fn)(struct extent_status *es),
281 + ext4_lblk_t lblk, ext4_lblk_t end)
282 +{
283 + bool ret;
284 +
285 + read_lock(&EXT4_I(inode)->i_es_lock);
286 + ret = __es_scan_range(inode, matching_fn, lblk, end);
287 + read_unlock(&EXT4_I(inode)->i_es_lock);
288 +
289 + return ret;
290 +}
291 +
292 +/*
293 + * __es_scan_clu - search cluster for block with specified status in
294 + * extents status tree
295 + *
296 + * @inode - file containing the cluster
297 + * @matching_fn - pointer to function that matches extents with desired status
298 + * @lblk - logical block in cluster to be searched
299 + *
300 + * Returns true if at least one extent in the cluster containing @lblk
301 + * satisfies the criterion specified by @matching_fn, and false if not. If at
302 + * least one extent has the specified status, then there is at least one block
303 + * in the cluster with that status. Should only be called by code that has
304 + * taken i_es_lock.
305 + */
306 +static bool __es_scan_clu(struct inode *inode,
307 + int (*matching_fn)(struct extent_status *es),
308 + ext4_lblk_t lblk)
309 +{
310 + struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
311 + ext4_lblk_t lblk_start, lblk_end;
312 +
313 + lblk_start = EXT4_LBLK_CMASK(sbi, lblk);
314 + lblk_end = lblk_start + sbi->s_cluster_ratio - 1;
315 +
316 + return __es_scan_range(inode, matching_fn, lblk_start, lblk_end);
317 +}
318 +
319 +/*
320 + * Locking for __es_scan_clu() for external use
321 + */
322 +bool ext4_es_scan_clu(struct inode *inode,
323 + int (*matching_fn)(struct extent_status *es),
324 + ext4_lblk_t lblk)
325 +{
326 + bool ret;
327 +
328 + read_lock(&EXT4_I(inode)->i_es_lock);
329 + ret = __es_scan_clu(inode, matching_fn, lblk);
330 read_unlock(&EXT4_I(inode)->i_es_lock);
332 - trace_ext4_es_find_delayed_extent_range_exit(inode, es);
333 + return ret;
334 }
336 static void ext4_es_list_add(struct inode *inode)
337 diff --git a/fs/ext4/extents_status.h b/fs/ext4/extents_status.h
338 index 8efdeb903d6b..df9628c3ec3b 100644
339 --- a/fs/ext4/extents_status.h
340 +++ b/fs/ext4/extents_status.h
341 @@ -90,11 +90,18 @@ extern void ext4_es_cache_extent(struct inode *inode, ext4_lblk_t lblk,
342 unsigned int status);
343 extern int ext4_es_remove_extent(struct inode *inode, ext4_lblk_t lblk,
344 ext4_lblk_t len);
345 -extern void ext4_es_find_delayed_extent_range(struct inode *inode,
346 - ext4_lblk_t lblk, ext4_lblk_t end,
347 - struct extent_status *es);
348 +extern void ext4_es_find_extent_range(struct inode *inode,
349 + int (*match_fn)(struct extent_status *es),
350 + ext4_lblk_t lblk, ext4_lblk_t end,
351 + struct extent_status *es);
352 extern int ext4_es_lookup_extent(struct inode *inode, ext4_lblk_t lblk,
353 struct extent_status *es);
354 +extern bool ext4_es_scan_range(struct inode *inode,
355 + int (*matching_fn)(struct extent_status *es),
356 + ext4_lblk_t lblk, ext4_lblk_t end);
357 +extern bool ext4_es_scan_clu(struct inode *inode,
358 + int (*matching_fn)(struct extent_status *es),
359 + ext4_lblk_t lblk);
361 static inline unsigned int ext4_es_status(struct extent_status *es)
362 {
363 diff --git a/fs/ext4/inode.c b/fs/ext4/inode.c
364 index d767e993591d..b83bf3308b5e 100644
365 --- a/fs/ext4/inode.c
366 +++ b/fs/ext4/inode.c
367 @@ -577,8 +577,8 @@ int ext4_map_blocks(handle_t *handle, struct inode *inode,
368 EXTENT_STATUS_UNWRITTEN : EXTENT_STATUS_WRITTEN;
369 if (!(flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE) &&
370 !(status & EXTENT_STATUS_WRITTEN) &&
371 - ext4_find_delalloc_range(inode, map->m_lblk,
372 - map->m_lblk + map->m_len - 1))
373 + ext4_es_scan_range(inode, &ext4_es_is_delayed, map->m_lblk,
374 + map->m_lblk + map->m_len - 1))
375 status |= EXTENT_STATUS_DELAYED;
376 ret = ext4_es_insert_extent(inode, map->m_lblk,
377 map->m_len, map->m_pblk, status);
378 @@ -701,8 +701,8 @@ int ext4_map_blocks(handle_t *handle, struct inode *inode,
379 EXTENT_STATUS_UNWRITTEN : EXTENT_STATUS_WRITTEN;
380 if (!(flags & EXT4_GET_BLOCKS_DELALLOC_RESERVE) &&
381 !(status & EXTENT_STATUS_WRITTEN) &&
382 - ext4_find_delalloc_range(inode, map->m_lblk,
383 - map->m_lblk + map->m_len - 1))
384 + ext4_es_scan_range(inode, &ext4_es_is_delayed, map->m_lblk,
385 + map->m_lblk + map->m_len - 1))
386 status |= EXTENT_STATUS_DELAYED;
387 ret = ext4_es_insert_extent(inode, map->m_lblk, map->m_len,
388 map->m_pblk, status);
389 @@ -1681,7 +1681,7 @@ static void ext4_da_page_release_reservation(struct page *page,
390 lblk = (page->index << (PAGE_SHIFT - inode->i_blkbits)) +
391 ((num_clusters - 1) << sbi->s_cluster_bits);
392 if (sbi->s_cluster_ratio == 1 ||
393 - !ext4_find_delalloc_cluster(inode, lblk))
394 + !ext4_es_scan_clu(inode, &ext4_es_is_delayed, lblk))
395 ext4_da_release_space(inode, 1);
397 num_clusters--;
398 @@ -1859,6 +1859,7 @@ static int ext4_da_map_blocks(struct inode *inode, sector_t iblock,
399 add_delayed:
400 if (retval == 0) {
401 int ret;
402 +
403 /*
404 * XXX: __block_prepare_write() unmaps passed block,
405 * is it OK?
406 @@ -1869,7 +1870,8 @@ static int ext4_da_map_blocks(struct inode *inode, sector_t iblock,
407 * to reserve metadata for every block we're going to write.
408 */
409 if (EXT4_SB(inode->i_sb)->s_cluster_ratio == 1 ||
410 - !ext4_find_delalloc_cluster(inode, map->m_lblk)) {
411 + !ext4_es_scan_clu(inode,
412 + &ext4_es_is_delayed, map->m_lblk)) {
413 ret = ext4_da_reserve_space(inode);
414 if (ret) {
415 /* not enough space to reserve */
416 @@ -3450,7 +3452,8 @@ static int ext4_iomap_begin(struct inode *inode, loff_t offset, loff_t length,
417 ext4_lblk_t end = map.m_lblk + map.m_len - 1;
418 struct extent_status es;
420 - ext4_es_find_delayed_extent_range(inode, map.m_lblk, end, &es);
421 + ext4_es_find_extent_range(inode, &ext4_es_is_delayed,
422 + map.m_lblk, end, &es);
424 if (!es.es_len || es.es_lblk > end) {
425 /* entire range is a hole */
426 diff --git a/include/trace/events/ext4.h b/include/trace/events/ext4.h
427 index 0e31eb136c57..7849b7f8fd9d 100644
428 --- a/include/trace/events/ext4.h
429 +++ b/include/trace/events/ext4.h
430 @@ -2270,7 +2270,7 @@ TRACE_EVENT(ext4_es_remove_extent,
431 __entry->lblk, __entry->len)
432 );
434 -TRACE_EVENT(ext4_es_find_delayed_extent_range_enter,
435 +TRACE_EVENT(ext4_es_find_extent_range_enter,
436 TP_PROTO(struct inode *inode, ext4_lblk_t lblk),
438 TP_ARGS(inode, lblk),
439 @@ -2292,7 +2292,7 @@ TRACE_EVENT(ext4_es_find_delayed_extent_range_enter,
440 (unsigned long) __entry->ino, __entry->lblk)
441 );
443 -TRACE_EVENT(ext4_es_find_delayed_extent_range_exit,
444 +TRACE_EVENT(ext4_es_find_extent_range_exit,
445 TP_PROTO(struct inode *inode, struct extent_status *es),
447 TP_ARGS(inode, es),
448 --
449 2.11.0