Commit | Line | Data |
---|---|---|
7c1a000d | 1 | // SPDX-License-Identifier: GPL-2.0 |
a28ef1f5 CY |
2 | /* |
3 | * f2fs extent cache support | |
4 | * | |
5 | * Copyright (c) 2015 Motorola Mobility | |
6 | * Copyright (c) 2015 Samsung Electronics | |
7 | * Authors: Jaegeuk Kim <jaegeuk@kernel.org> | |
8 | * Chao Yu <chao2.yu@samsung.com> | |
71644dff JK |
9 | * |
10 | * block_age-based extent cache added by: | |
11 | * Copyright (c) 2022 xiaomi Co., Ltd. | |
12 | * http://www.xiaomi.com/ | |
a28ef1f5 CY |
13 | */ |
14 | ||
15 | #include <linux/fs.h> | |
16 | #include <linux/f2fs_fs.h> | |
17 | ||
18 | #include "f2fs.h" | |
19 | #include "node.h" | |
20 | #include <trace/events/f2fs.h> | |
21 | ||
269d1194 CY |
22 | bool sanity_check_extent_cache(struct inode *inode) |
23 | { | |
24 | struct f2fs_sb_info *sbi = F2FS_I_SB(inode); | |
25 | struct f2fs_inode_info *fi = F2FS_I(inode); | |
bd90c5cd | 26 | struct extent_tree *et = fi->extent_tree[EX_READ]; |
269d1194 CY |
27 | struct extent_info *ei; |
28 | ||
bd90c5cd | 29 | if (!et) |
269d1194 CY |
30 | return true; |
31 | ||
bd90c5cd JK |
32 | ei = &et->largest; |
33 | if (!ei->len) | |
34 | return true; | |
35 | ||
36 | /* Let's drop, if checkpoint got corrupted. */ | |
37 | if (is_set_ckpt_flags(sbi, CP_ERROR_FLAG)) { | |
38 | ei->len = 0; | |
39 | et->largest_updated = true; | |
40 | return true; | |
41 | } | |
269d1194 | 42 | |
bd90c5cd JK |
43 | if (!f2fs_is_valid_blkaddr(sbi, ei->blk, DATA_GENERIC_ENHANCE) || |
44 | !f2fs_is_valid_blkaddr(sbi, ei->blk + ei->len - 1, | |
45 | DATA_GENERIC_ENHANCE)) { | |
269d1194 CY |
46 | set_sbi_flag(sbi, SBI_NEED_FSCK); |
47 | f2fs_warn(sbi, "%s: inode (ino=%lx) extent info [%u, %u, %u] is incorrect, run fsck to fix", | |
48 | __func__, inode->i_ino, | |
49 | ei->blk, ei->fofs, ei->len); | |
50 | return false; | |
51 | } | |
52 | return true; | |
53 | } | |
54 | ||
3bac20a8 JK |
55 | static void __set_extent_info(struct extent_info *ei, |
56 | unsigned int fofs, unsigned int len, | |
e7547dac | 57 | block_t blk, bool keep_clen, |
71644dff | 58 | unsigned long age, unsigned long last_blocks, |
e7547dac | 59 | enum extent_type type) |
3bac20a8 JK |
60 | { |
61 | ei->fofs = fofs; | |
3bac20a8 JK |
62 | ei->len = len; |
63 | ||
e7547dac JK |
64 | if (type == EX_READ) { |
65 | ei->blk = blk; | |
66 | if (keep_clen) | |
67 | return; | |
3bac20a8 | 68 | #ifdef CONFIG_F2FS_FS_COMPRESSION |
e7547dac | 69 | ei->c_len = 0; |
3bac20a8 | 70 | #endif |
71644dff JK |
71 | } else if (type == EX_BLOCK_AGE) { |
72 | ei->age = age; | |
73 | ei->last_blocks = last_blocks; | |
e7547dac JK |
74 | } |
75 | } | |
76 | ||
72840ccc | 77 | static bool __init_may_extent_tree(struct inode *inode, enum extent_type type) |
3bac20a8 | 78 | { |
72840ccc | 79 | if (type == EX_READ) |
f8039821 JK |
80 | return test_opt(F2FS_I_SB(inode), READ_EXTENT_CACHE) && |
81 | S_ISREG(inode->i_mode); | |
82 | if (type == EX_BLOCK_AGE) | |
83 | return test_opt(F2FS_I_SB(inode), AGE_EXTENT_CACHE) && | |
84 | (S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode)); | |
72840ccc JK |
85 | return false; |
86 | } | |
3bac20a8 | 87 | |
72840ccc JK |
88 | static bool __may_extent_tree(struct inode *inode, enum extent_type type) |
89 | { | |
3bac20a8 JK |
90 | /* |
91 | * for recovered files during mount do not create extents | |
92 | * if shrinker is not registered. | |
93 | */ | |
72840ccc | 94 | if (list_empty(&F2FS_I_SB(inode)->s_list)) |
3bac20a8 JK |
95 | return false; |
96 | ||
f8039821 JK |
97 | if (!__init_may_extent_tree(inode, type)) |
98 | return false; | |
99 | ||
100 | if (type == EX_READ) { | |
101 | if (is_inode_flag_set(inode, FI_NO_EXTENT)) | |
102 | return false; | |
103 | if (is_inode_flag_set(inode, FI_COMPRESSED_FILE) && | |
104 | !f2fs_sb_has_readonly(F2FS_I_SB(inode))) | |
105 | return false; | |
106 | } else if (type == EX_BLOCK_AGE) { | |
107 | if (is_inode_flag_set(inode, FI_COMPRESSED_FILE)) | |
108 | return false; | |
109 | if (file_is_cold(inode)) | |
110 | return false; | |
111 | } | |
112 | return true; | |
3bac20a8 JK |
113 | } |
114 | ||
115 | static void __try_update_largest_extent(struct extent_tree *et, | |
116 | struct extent_node *en) | |
117 | { | |
e7547dac JK |
118 | if (et->type != EX_READ) |
119 | return; | |
3bac20a8 JK |
120 | if (en->ei.len <= et->largest.len) |
121 | return; | |
122 | ||
123 | et->largest = en->ei; | |
124 | et->largest_updated = true; | |
125 | } | |
126 | ||
127 | static bool __is_extent_mergeable(struct extent_info *back, | |
e7547dac | 128 | struct extent_info *front, enum extent_type type) |
3bac20a8 | 129 | { |
e7547dac | 130 | if (type == EX_READ) { |
3bac20a8 | 131 | #ifdef CONFIG_F2FS_FS_COMPRESSION |
e7547dac JK |
132 | if (back->c_len && back->len != back->c_len) |
133 | return false; | |
134 | if (front->c_len && front->len != front->c_len) | |
135 | return false; | |
3bac20a8 | 136 | #endif |
e7547dac JK |
137 | return (back->fofs + back->len == front->fofs && |
138 | back->blk + back->len == front->blk); | |
71644dff JK |
139 | } else if (type == EX_BLOCK_AGE) { |
140 | return (back->fofs + back->len == front->fofs && | |
141 | abs(back->age - front->age) <= SAME_AGE_REGION && | |
142 | abs(back->last_blocks - front->last_blocks) <= | |
143 | SAME_AGE_REGION); | |
e7547dac JK |
144 | } |
145 | return false; | |
3bac20a8 JK |
146 | } |
147 | ||
148 | static bool __is_back_mergeable(struct extent_info *cur, | |
e7547dac | 149 | struct extent_info *back, enum extent_type type) |
3bac20a8 | 150 | { |
e7547dac | 151 | return __is_extent_mergeable(back, cur, type); |
3bac20a8 JK |
152 | } |
153 | ||
154 | static bool __is_front_mergeable(struct extent_info *cur, | |
e7547dac | 155 | struct extent_info *front, enum extent_type type) |
3bac20a8 | 156 | { |
e7547dac | 157 | return __is_extent_mergeable(cur, front, type); |
3bac20a8 JK |
158 | } |
159 | ||
bf21acf9 JK |
160 | static struct extent_node *__lookup_extent_node(struct rb_root_cached *root, |
161 | struct extent_node *cached_en, unsigned int fofs) | |
54c2258c | 162 | { |
4dada3fd | 163 | struct rb_node *node = root->rb_root.rb_node; |
bf21acf9 JK |
164 | struct extent_node *en; |
165 | ||
166 | /* check a cached entry */ | |
167 | if (cached_en && cached_en->ei.fofs <= fofs && | |
168 | cached_en->ei.fofs + cached_en->ei.len > fofs) | |
169 | return cached_en; | |
54c2258c | 170 | |
bf21acf9 | 171 | /* check rb_tree */ |
54c2258c | 172 | while (node) { |
bf21acf9 | 173 | en = rb_entry(node, struct extent_node, rb_node); |
54c2258c | 174 | |
bf21acf9 | 175 | if (fofs < en->ei.fofs) |
54c2258c | 176 | node = node->rb_left; |
bf21acf9 | 177 | else if (fofs >= en->ei.fofs + en->ei.len) |
54c2258c CY |
178 | node = node->rb_right; |
179 | else | |
bf21acf9 | 180 | return en; |
54c2258c CY |
181 | } |
182 | return NULL; | |
183 | } | |
184 | ||
54c2258c | 185 | /* |
bf21acf9 | 186 | * lookup rb entry in position of @fofs in rb-tree, |
54c2258c | 187 | * if hit, return the entry, otherwise, return NULL |
bf21acf9 JK |
188 | * @prev_ex: extent before fofs |
189 | * @next_ex: extent after fofs | |
190 | * @insert_p: insert point for new extent at fofs | |
146949de | 191 | * in order to simplify the insertion after. |
54c2258c CY |
192 | * tree must stay unchanged between lookup and insertion. |
193 | */ | |
bf21acf9 JK |
194 | static struct extent_node *__lookup_extent_node_ret(struct rb_root_cached *root, |
195 | struct extent_node *cached_en, | |
196 | unsigned int fofs, | |
197 | struct extent_node **prev_entry, | |
198 | struct extent_node **next_entry, | |
54c2258c | 199 | struct rb_node ***insert_p, |
004b6862 | 200 | struct rb_node **insert_parent, |
bf21acf9 | 201 | bool *leftmost) |
54c2258c | 202 | { |
4dada3fd | 203 | struct rb_node **pnode = &root->rb_root.rb_node; |
54c2258c | 204 | struct rb_node *parent = NULL, *tmp_node; |
bf21acf9 | 205 | struct extent_node *en = cached_en; |
54c2258c CY |
206 | |
207 | *insert_p = NULL; | |
208 | *insert_parent = NULL; | |
209 | *prev_entry = NULL; | |
210 | *next_entry = NULL; | |
211 | ||
4dada3fd | 212 | if (RB_EMPTY_ROOT(&root->rb_root)) |
54c2258c CY |
213 | return NULL; |
214 | ||
bf21acf9 JK |
215 | if (en && en->ei.fofs <= fofs && en->ei.fofs + en->ei.len > fofs) |
216 | goto lookup_neighbors; | |
54c2258c | 217 | |
bf21acf9 | 218 | *leftmost = true; |
4dada3fd | 219 | |
54c2258c CY |
220 | while (*pnode) { |
221 | parent = *pnode; | |
bf21acf9 | 222 | en = rb_entry(*pnode, struct extent_node, rb_node); |
54c2258c | 223 | |
bf21acf9 | 224 | if (fofs < en->ei.fofs) { |
54c2258c | 225 | pnode = &(*pnode)->rb_left; |
bf21acf9 | 226 | } else if (fofs >= en->ei.fofs + en->ei.len) { |
54c2258c | 227 | pnode = &(*pnode)->rb_right; |
bf21acf9 | 228 | *leftmost = false; |
4dada3fd | 229 | } else { |
54c2258c | 230 | goto lookup_neighbors; |
4dada3fd | 231 | } |
54c2258c CY |
232 | } |
233 | ||
234 | *insert_p = pnode; | |
235 | *insert_parent = parent; | |
236 | ||
bf21acf9 | 237 | en = rb_entry(parent, struct extent_node, rb_node); |
54c2258c | 238 | tmp_node = parent; |
bf21acf9 | 239 | if (parent && fofs > en->ei.fofs) |
54c2258c | 240 | tmp_node = rb_next(parent); |
bf21acf9 | 241 | *next_entry = rb_entry_safe(tmp_node, struct extent_node, rb_node); |
54c2258c CY |
242 | |
243 | tmp_node = parent; | |
bf21acf9 | 244 | if (parent && fofs < en->ei.fofs) |
54c2258c | 245 | tmp_node = rb_prev(parent); |
bf21acf9 | 246 | *prev_entry = rb_entry_safe(tmp_node, struct extent_node, rb_node); |
54c2258c CY |
247 | return NULL; |
248 | ||
249 | lookup_neighbors: | |
bf21acf9 | 250 | if (fofs == en->ei.fofs) { |
54c2258c | 251 | /* lookup prev node for merging backward later */ |
bf21acf9 JK |
252 | tmp_node = rb_prev(&en->rb_node); |
253 | *prev_entry = rb_entry_safe(tmp_node, | |
254 | struct extent_node, rb_node); | |
54c2258c | 255 | } |
bf21acf9 | 256 | if (fofs == en->ei.fofs + en->ei.len - 1) { |
54c2258c | 257 | /* lookup next node for merging frontward later */ |
bf21acf9 JK |
258 | tmp_node = rb_next(&en->rb_node); |
259 | *next_entry = rb_entry_safe(tmp_node, | |
260 | struct extent_node, rb_node); | |
54c2258c | 261 | } |
bf21acf9 | 262 | return en; |
54c2258c CY |
263 | } |
264 | ||
a28ef1f5 CY |
265 | static struct kmem_cache *extent_tree_slab; |
266 | static struct kmem_cache *extent_node_slab; | |
267 | ||
268 | static struct extent_node *__attach_extent_node(struct f2fs_sb_info *sbi, | |
269 | struct extent_tree *et, struct extent_info *ei, | |
4dada3fd CY |
270 | struct rb_node *parent, struct rb_node **p, |
271 | bool leftmost) | |
a28ef1f5 | 272 | { |
e7547dac | 273 | struct extent_tree_info *eti = &sbi->extent_tree[et->type]; |
a28ef1f5 CY |
274 | struct extent_node *en; |
275 | ||
32410577 | 276 | en = f2fs_kmem_cache_alloc(extent_node_slab, GFP_ATOMIC, false, sbi); |
a28ef1f5 CY |
277 | if (!en) |
278 | return NULL; | |
279 | ||
280 | en->ei = *ei; | |
281 | INIT_LIST_HEAD(&en->list); | |
201ef5e0 | 282 | en->et = et; |
a28ef1f5 CY |
283 | |
284 | rb_link_node(&en->rb_node, parent, p); | |
4dada3fd | 285 | rb_insert_color_cached(&en->rb_node, &et->root, leftmost); |
68e35385 | 286 | atomic_inc(&et->node_cnt); |
e7547dac | 287 | atomic_inc(&eti->total_ext_node); |
a28ef1f5 CY |
288 | return en; |
289 | } | |
290 | ||
291 | static void __detach_extent_node(struct f2fs_sb_info *sbi, | |
292 | struct extent_tree *et, struct extent_node *en) | |
293 | { | |
e7547dac JK |
294 | struct extent_tree_info *eti = &sbi->extent_tree[et->type]; |
295 | ||
4dada3fd | 296 | rb_erase_cached(&en->rb_node, &et->root); |
68e35385 | 297 | atomic_dec(&et->node_cnt); |
e7547dac | 298 | atomic_dec(&eti->total_ext_node); |
a28ef1f5 CY |
299 | |
300 | if (et->cached_en == en) | |
301 | et->cached_en = NULL; | |
a03f01f2 HP |
302 | kmem_cache_free(extent_node_slab, en); |
303 | } | |
304 | ||
305 | /* | |
306 | * Flow to release an extent_node: | |
307 | * 1. list_del_init | |
308 | * 2. __detach_extent_node | |
309 | * 3. kmem_cache_free. | |
310 | */ | |
311 | static void __release_extent_node(struct f2fs_sb_info *sbi, | |
312 | struct extent_tree *et, struct extent_node *en) | |
313 | { | |
e7547dac JK |
314 | struct extent_tree_info *eti = &sbi->extent_tree[et->type]; |
315 | ||
316 | spin_lock(&eti->extent_lock); | |
201ef5e0 HP |
317 | f2fs_bug_on(sbi, list_empty(&en->list)); |
318 | list_del_init(&en->list); | |
e7547dac | 319 | spin_unlock(&eti->extent_lock); |
a03f01f2 HP |
320 | |
321 | __detach_extent_node(sbi, et, en); | |
a28ef1f5 CY |
322 | } |
323 | ||
e7547dac JK |
324 | static struct extent_tree *__grab_extent_tree(struct inode *inode, |
325 | enum extent_type type) | |
a28ef1f5 CY |
326 | { |
327 | struct f2fs_sb_info *sbi = F2FS_I_SB(inode); | |
e7547dac | 328 | struct extent_tree_info *eti = &sbi->extent_tree[type]; |
a28ef1f5 CY |
329 | struct extent_tree *et; |
330 | nid_t ino = inode->i_ino; | |
331 | ||
e7547dac JK |
332 | mutex_lock(&eti->extent_tree_lock); |
333 | et = radix_tree_lookup(&eti->extent_tree_root, ino); | |
a28ef1f5 | 334 | if (!et) { |
32410577 CY |
335 | et = f2fs_kmem_cache_alloc(extent_tree_slab, |
336 | GFP_NOFS, true, NULL); | |
e7547dac | 337 | f2fs_radix_tree_insert(&eti->extent_tree_root, ino, et); |
a28ef1f5 CY |
338 | memset(et, 0, sizeof(struct extent_tree)); |
339 | et->ino = ino; | |
e7547dac | 340 | et->type = type; |
4dada3fd | 341 | et->root = RB_ROOT_CACHED; |
a28ef1f5 CY |
342 | et->cached_en = NULL; |
343 | rwlock_init(&et->lock); | |
137d09f0 | 344 | INIT_LIST_HEAD(&et->list); |
68e35385 | 345 | atomic_set(&et->node_cnt, 0); |
e7547dac | 346 | atomic_inc(&eti->total_ext_tree); |
74fd8d99 | 347 | } else { |
e7547dac | 348 | atomic_dec(&eti->total_zombie_tree); |
137d09f0 | 349 | list_del_init(&et->list); |
a28ef1f5 | 350 | } |
e7547dac | 351 | mutex_unlock(&eti->extent_tree_lock); |
a28ef1f5 CY |
352 | |
353 | /* never died until evict_inode */ | |
e7547dac | 354 | F2FS_I(inode)->extent_tree[type] = et; |
a28ef1f5 CY |
355 | |
356 | return et; | |
357 | } | |
358 | ||
a28ef1f5 | 359 | static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi, |
201ef5e0 | 360 | struct extent_tree *et) |
a28ef1f5 CY |
361 | { |
362 | struct rb_node *node, *next; | |
363 | struct extent_node *en; | |
68e35385 | 364 | unsigned int count = atomic_read(&et->node_cnt); |
a28ef1f5 | 365 | |
4dada3fd | 366 | node = rb_first_cached(&et->root); |
a28ef1f5 CY |
367 | while (node) { |
368 | next = rb_next(node); | |
369 | en = rb_entry(node, struct extent_node, rb_node); | |
201ef5e0 | 370 | __release_extent_node(sbi, et, en); |
a28ef1f5 CY |
371 | node = next; |
372 | } | |
373 | ||
68e35385 | 374 | return count - atomic_read(&et->node_cnt); |
a28ef1f5 CY |
375 | } |
376 | ||
b430f726 | 377 | static void __drop_largest_extent(struct extent_tree *et, |
41a099de | 378 | pgoff_t fofs, unsigned int len) |
a28ef1f5 | 379 | { |
b430f726 ZZ |
380 | if (fofs < et->largest.fofs + et->largest.len && |
381 | fofs + len > et->largest.fofs) { | |
382 | et->largest.len = 0; | |
383 | et->largest_updated = true; | |
205b9822 | 384 | } |
a28ef1f5 CY |
385 | } |
386 | ||
72840ccc | 387 | void f2fs_init_read_extent_tree(struct inode *inode, struct page *ipage) |
a28ef1f5 CY |
388 | { |
389 | struct f2fs_sb_info *sbi = F2FS_I_SB(inode); | |
72840ccc JK |
390 | struct extent_tree_info *eti = &sbi->extent_tree[EX_READ]; |
391 | struct f2fs_extent *i_ext = &F2FS_INODE(ipage)->i_ext; | |
a28ef1f5 CY |
392 | struct extent_tree *et; |
393 | struct extent_node *en; | |
394 | struct extent_info ei; | |
395 | ||
72840ccc | 396 | if (!__may_extent_tree(inode, EX_READ)) { |
e7547dac | 397 | /* drop largest read extent */ |
72840ccc | 398 | if (i_ext && i_ext->len) { |
a6d601f3 | 399 | f2fs_wait_on_page_writeback(ipage, NODE, true, true); |
ed3d1256 | 400 | i_ext->len = 0; |
a6d601f3 | 401 | set_page_dirty(ipage); |
ed3d1256 | 402 | } |
e7547dac | 403 | goto out; |
ed3d1256 | 404 | } |
a28ef1f5 | 405 | |
72840ccc | 406 | et = __grab_extent_tree(inode, EX_READ); |
a28ef1f5 | 407 | |
ed3d1256 | 408 | if (!i_ext || !i_ext->len) |
e7547dac JK |
409 | goto out; |
410 | ||
12607c1b | 411 | get_read_extent_info(&ei, i_ext); |
a28ef1f5 CY |
412 | |
413 | write_lock(&et->lock); | |
68e35385 | 414 | if (atomic_read(&et->node_cnt)) |
e7547dac | 415 | goto unlock_out; |
a28ef1f5 | 416 | |
749d543c JK |
417 | en = __attach_extent_node(sbi, et, &ei, NULL, |
418 | &et->root.rb_root.rb_node, true); | |
a28ef1f5 | 419 | if (en) { |
749d543c JK |
420 | et->largest = en->ei; |
421 | et->cached_en = en; | |
422 | ||
e7547dac JK |
423 | spin_lock(&eti->extent_lock); |
424 | list_add_tail(&en->list, &eti->extent_list); | |
425 | spin_unlock(&eti->extent_lock); | |
a28ef1f5 | 426 | } |
e7547dac | 427 | unlock_out: |
a28ef1f5 | 428 | write_unlock(&et->lock); |
e7547dac | 429 | out: |
72840ccc | 430 | if (!F2FS_I(inode)->extent_tree[EX_READ]) |
e7547dac | 431 | set_inode_flag(inode, FI_NO_EXTENT); |
a28ef1f5 CY |
432 | } |
433 | ||
71644dff JK |
434 | void f2fs_init_age_extent_tree(struct inode *inode) |
435 | { | |
436 | if (!__init_may_extent_tree(inode, EX_BLOCK_AGE)) | |
437 | return; | |
438 | __grab_extent_tree(inode, EX_BLOCK_AGE); | |
439 | } | |
440 | ||
72840ccc | 441 | void f2fs_init_extent_tree(struct inode *inode) |
dad48e73 | 442 | { |
e7547dac | 443 | /* initialize read cache */ |
72840ccc JK |
444 | if (__init_may_extent_tree(inode, EX_READ)) |
445 | __grab_extent_tree(inode, EX_READ); | |
71644dff JK |
446 | |
447 | /* initialize block age cache */ | |
448 | if (__init_may_extent_tree(inode, EX_BLOCK_AGE)) | |
449 | __grab_extent_tree(inode, EX_BLOCK_AGE); | |
dad48e73 YH |
450 | } |
451 | ||
e7547dac JK |
452 | static bool __lookup_extent_tree(struct inode *inode, pgoff_t pgofs, |
453 | struct extent_info *ei, enum extent_type type) | |
a28ef1f5 CY |
454 | { |
455 | struct f2fs_sb_info *sbi = F2FS_I_SB(inode); | |
e7547dac JK |
456 | struct extent_tree_info *eti = &sbi->extent_tree[type]; |
457 | struct extent_tree *et = F2FS_I(inode)->extent_tree[type]; | |
a28ef1f5 CY |
458 | struct extent_node *en; |
459 | bool ret = false; | |
460 | ||
df9d44b6 JK |
461 | if (!et) |
462 | return false; | |
a28ef1f5 | 463 | |
e7547dac | 464 | trace_f2fs_lookup_extent_tree_start(inode, pgofs, type); |
a28ef1f5 CY |
465 | |
466 | read_lock(&et->lock); | |
467 | ||
e7547dac JK |
468 | if (type == EX_READ && |
469 | et->largest.fofs <= pgofs && | |
a28ef1f5 CY |
470 | et->largest.fofs + et->largest.len > pgofs) { |
471 | *ei = et->largest; | |
472 | ret = true; | |
91c481ff | 473 | stat_inc_largest_node_hit(sbi); |
a28ef1f5 CY |
474 | goto out; |
475 | } | |
476 | ||
bf21acf9 | 477 | en = __lookup_extent_node(&et->root, et->cached_en, pgofs); |
54c2258c CY |
478 | if (!en) |
479 | goto out; | |
480 | ||
481 | if (en == et->cached_en) | |
e7547dac | 482 | stat_inc_cached_node_hit(sbi, type); |
54c2258c | 483 | else |
e7547dac | 484 | stat_inc_rbtree_node_hit(sbi, type); |
54c2258c CY |
485 | |
486 | *ei = en->ei; | |
e7547dac | 487 | spin_lock(&eti->extent_lock); |
54c2258c | 488 | if (!list_empty(&en->list)) { |
e7547dac | 489 | list_move_tail(&en->list, &eti->extent_list); |
54c2258c | 490 | et->cached_en = en; |
a28ef1f5 | 491 | } |
e7547dac | 492 | spin_unlock(&eti->extent_lock); |
54c2258c | 493 | ret = true; |
a28ef1f5 | 494 | out: |
e7547dac | 495 | stat_inc_total_hit(sbi, type); |
a28ef1f5 CY |
496 | read_unlock(&et->lock); |
497 | ||
e7547dac JK |
498 | if (type == EX_READ) |
499 | trace_f2fs_lookup_read_extent_tree_end(inode, pgofs, ei); | |
71644dff JK |
500 | else if (type == EX_BLOCK_AGE) |
501 | trace_f2fs_lookup_age_extent_tree_end(inode, pgofs, ei); | |
a28ef1f5 CY |
502 | return ret; |
503 | } | |
504 | ||
b430f726 | 505 | static struct extent_node *__try_merge_extent_node(struct f2fs_sb_info *sbi, |
0f825ee6 | 506 | struct extent_tree *et, struct extent_info *ei, |
0f825ee6 | 507 | struct extent_node *prev_ex, |
ef05e221 | 508 | struct extent_node *next_ex) |
0f825ee6 | 509 | { |
e7547dac | 510 | struct extent_tree_info *eti = &sbi->extent_tree[et->type]; |
0f825ee6 | 511 | struct extent_node *en = NULL; |
0f825ee6 | 512 | |
e7547dac | 513 | if (prev_ex && __is_back_mergeable(ei, &prev_ex->ei, et->type)) { |
0f825ee6 FL |
514 | prev_ex->ei.len += ei->len; |
515 | ei = &prev_ex->ei; | |
516 | en = prev_ex; | |
517 | } | |
ef05e221 | 518 | |
e7547dac | 519 | if (next_ex && __is_front_mergeable(ei, &next_ex->ei, et->type)) { |
0f825ee6 | 520 | next_ex->ei.fofs = ei->fofs; |
0f825ee6 | 521 | next_ex->ei.len += ei->len; |
e7547dac JK |
522 | if (et->type == EX_READ) |
523 | next_ex->ei.blk = ei->blk; | |
7855eba4 YH |
524 | if (en) |
525 | __release_extent_node(sbi, et, prev_ex); | |
526 | ||
0f825ee6 FL |
527 | en = next_ex; |
528 | } | |
ef05e221 | 529 | |
43a2fa18 JK |
530 | if (!en) |
531 | return NULL; | |
532 | ||
b430f726 | 533 | __try_update_largest_extent(et, en); |
43a2fa18 | 534 | |
e7547dac | 535 | spin_lock(&eti->extent_lock); |
42926744 | 536 | if (!list_empty(&en->list)) { |
e7547dac | 537 | list_move_tail(&en->list, &eti->extent_list); |
42926744 JK |
538 | et->cached_en = en; |
539 | } | |
e7547dac | 540 | spin_unlock(&eti->extent_lock); |
ef05e221 CY |
541 | return en; |
542 | } | |
543 | ||
b430f726 | 544 | static struct extent_node *__insert_extent_tree(struct f2fs_sb_info *sbi, |
ef05e221 CY |
545 | struct extent_tree *et, struct extent_info *ei, |
546 | struct rb_node **insert_p, | |
4dada3fd CY |
547 | struct rb_node *insert_parent, |
548 | bool leftmost) | |
ef05e221 | 549 | { |
e7547dac | 550 | struct extent_tree_info *eti = &sbi->extent_tree[et->type]; |
bf21acf9 | 551 | struct rb_node **p = &et->root.rb_root.rb_node; |
ef05e221 CY |
552 | struct rb_node *parent = NULL; |
553 | struct extent_node *en = NULL; | |
0f825ee6 FL |
554 | |
555 | if (insert_p && insert_parent) { | |
556 | parent = insert_parent; | |
557 | p = insert_p; | |
558 | goto do_insert; | |
559 | } | |
560 | ||
4dada3fd CY |
561 | leftmost = true; |
562 | ||
bf21acf9 JK |
563 | /* look up extent_node in the rb tree */ |
564 | while (*p) { | |
565 | parent = *p; | |
566 | en = rb_entry(parent, struct extent_node, rb_node); | |
567 | ||
568 | if (ei->fofs < en->ei.fofs) { | |
569 | p = &(*p)->rb_left; | |
570 | } else if (ei->fofs >= en->ei.fofs + en->ei.len) { | |
571 | p = &(*p)->rb_right; | |
572 | leftmost = false; | |
573 | } else { | |
574 | f2fs_bug_on(sbi, 1); | |
575 | } | |
576 | } | |
577 | ||
0f825ee6 | 578 | do_insert: |
4dada3fd | 579 | en = __attach_extent_node(sbi, et, ei, parent, p, leftmost); |
0f825ee6 FL |
580 | if (!en) |
581 | return NULL; | |
ef05e221 | 582 | |
b430f726 | 583 | __try_update_largest_extent(et, en); |
43a2fa18 JK |
584 | |
585 | /* update in global extent list */ | |
e7547dac JK |
586 | spin_lock(&eti->extent_lock); |
587 | list_add_tail(&en->list, &eti->extent_list); | |
42926744 | 588 | et->cached_en = en; |
e7547dac | 589 | spin_unlock(&eti->extent_lock); |
0f825ee6 FL |
590 | return en; |
591 | } | |
592 | ||
e7547dac JK |
593 | static void __update_extent_tree_range(struct inode *inode, |
594 | struct extent_info *tei, enum extent_type type) | |
a28ef1f5 CY |
595 | { |
596 | struct f2fs_sb_info *sbi = F2FS_I_SB(inode); | |
e7547dac | 597 | struct extent_tree *et = F2FS_I(inode)->extent_tree[type]; |
4d1fa815 | 598 | struct extent_node *en = NULL, *en1 = NULL; |
19b2c30d | 599 | struct extent_node *prev_en = NULL, *next_en = NULL; |
a28ef1f5 | 600 | struct extent_info ei, dei, prev; |
0f825ee6 | 601 | struct rb_node **insert_p = NULL, *insert_parent = NULL; |
e7547dac | 602 | unsigned int fofs = tei->fofs, len = tei->len; |
19b2c30d | 603 | unsigned int end = fofs + len; |
b430f726 | 604 | bool updated = false; |
f9aa52a8 | 605 | bool leftmost = false; |
a28ef1f5 CY |
606 | |
607 | if (!et) | |
317e1300 | 608 | return; |
a28ef1f5 | 609 | |
e7547dac JK |
610 | if (type == EX_READ) |
611 | trace_f2fs_update_read_extent_tree_range(inode, fofs, len, | |
612 | tei->blk, 0); | |
71644dff JK |
613 | else if (type == EX_BLOCK_AGE) |
614 | trace_f2fs_update_age_extent_tree_range(inode, fofs, len, | |
615 | tei->age, tei->last_blocks); | |
616 | ||
a28ef1f5 CY |
617 | write_lock(&et->lock); |
618 | ||
e7547dac JK |
619 | if (type == EX_READ) { |
620 | if (is_inode_flag_set(inode, FI_NO_EXTENT)) { | |
621 | write_unlock(&et->lock); | |
622 | return; | |
623 | } | |
a28ef1f5 | 624 | |
e7547dac JK |
625 | prev = et->largest; |
626 | dei.len = 0; | |
a28ef1f5 | 627 | |
e7547dac JK |
628 | /* |
629 | * drop largest extent before lookup, in case it's already | |
630 | * been shrunk from extent tree | |
631 | */ | |
632 | __drop_largest_extent(et, fofs, len); | |
633 | } | |
a28ef1f5 | 634 | |
19b2c30d | 635 | /* 1. lookup first extent node in range [fofs, fofs + len - 1] */ |
bf21acf9 JK |
636 | en = __lookup_extent_node_ret(&et->root, |
637 | et->cached_en, fofs, | |
638 | &prev_en, &next_en, | |
639 | &insert_p, &insert_parent, | |
4dada3fd | 640 | &leftmost); |
4d1fa815 FL |
641 | if (!en) |
642 | en = next_en; | |
19b2c30d | 643 | |
146949de | 644 | /* 2. invalidate all extent nodes in range [fofs, fofs + len - 1] */ |
4d1fa815 FL |
645 | while (en && en->ei.fofs < end) { |
646 | unsigned int org_end; | |
647 | int parts = 0; /* # of parts current extent split into */ | |
19b2c30d | 648 | |
4d1fa815 | 649 | next_en = en1 = NULL; |
19b2c30d CY |
650 | |
651 | dei = en->ei; | |
4d1fa815 | 652 | org_end = dei.fofs + dei.len; |
e7547dac | 653 | f2fs_bug_on(sbi, fofs >= org_end); |
19b2c30d | 654 | |
e7547dac JK |
655 | if (fofs > dei.fofs && (type != EX_READ || |
656 | fofs - dei.fofs >= F2FS_MIN_EXTENT_LEN)) { | |
657 | en->ei.len = fofs - en->ei.fofs; | |
4d1fa815 FL |
658 | prev_en = en; |
659 | parts = 1; | |
660 | } | |
19b2c30d | 661 | |
e7547dac JK |
662 | if (end < org_end && (type != EX_READ || |
663 | org_end - end >= F2FS_MIN_EXTENT_LEN)) { | |
4d1fa815 | 664 | if (parts) { |
3bac20a8 JK |
665 | __set_extent_info(&ei, |
666 | end, org_end - end, | |
e7547dac | 667 | end - dei.fofs + dei.blk, false, |
71644dff | 668 | dei.age, dei.last_blocks, |
e7547dac | 669 | type); |
b430f726 | 670 | en1 = __insert_extent_tree(sbi, et, &ei, |
4dada3fd | 671 | NULL, NULL, true); |
4d1fa815 FL |
672 | next_en = en1; |
673 | } else { | |
3bac20a8 JK |
674 | __set_extent_info(&en->ei, |
675 | end, en->ei.len - (end - dei.fofs), | |
e7547dac | 676 | en->ei.blk + (end - dei.fofs), true, |
71644dff | 677 | dei.age, dei.last_blocks, |
e7547dac | 678 | type); |
4d1fa815 | 679 | next_en = en; |
19b2c30d | 680 | } |
4d1fa815 | 681 | parts++; |
19b2c30d CY |
682 | } |
683 | ||
4d1fa815 FL |
684 | if (!next_en) { |
685 | struct rb_node *node = rb_next(&en->rb_node); | |
19b2c30d | 686 | |
ed0b5620 GT |
687 | next_en = rb_entry_safe(node, struct extent_node, |
688 | rb_node); | |
a28ef1f5 CY |
689 | } |
690 | ||
4abd3f5a | 691 | if (parts) |
b430f726 | 692 | __try_update_largest_extent(et, en); |
4abd3f5a | 693 | else |
a03f01f2 | 694 | __release_extent_node(sbi, et, en); |
19b2c30d CY |
695 | |
696 | /* | |
4d1fa815 FL |
697 | * if original extent is split into zero or two parts, extent |
698 | * tree has been altered by deletion or insertion, therefore | |
699 | * invalidate pointers regard to tree. | |
19b2c30d | 700 | */ |
4d1fa815 FL |
701 | if (parts != 1) { |
702 | insert_p = NULL; | |
703 | insert_parent = NULL; | |
a28ef1f5 | 704 | } |
4d1fa815 | 705 | en = next_en; |
a28ef1f5 CY |
706 | } |
707 | ||
71644dff JK |
708 | if (type == EX_BLOCK_AGE) |
709 | goto update_age_extent_cache; | |
710 | ||
e7547dac JK |
711 | /* 3. update extent in read extent cache */ |
712 | BUG_ON(type != EX_READ); | |
713 | ||
714 | if (tei->blk) { | |
71644dff JK |
715 | __set_extent_info(&ei, fofs, len, tei->blk, false, |
716 | 0, 0, EX_READ); | |
b430f726 ZZ |
717 | if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en)) |
718 | __insert_extent_tree(sbi, et, &ei, | |
4dada3fd | 719 | insert_p, insert_parent, leftmost); |
a28ef1f5 CY |
720 | |
721 | /* give up extent_cache, if split and small updates happen */ | |
722 | if (dei.len >= 1 && | |
723 | prev.len < F2FS_MIN_EXTENT_LEN && | |
724 | et->largest.len < F2FS_MIN_EXTENT_LEN) { | |
b430f726 ZZ |
725 | et->largest.len = 0; |
726 | et->largest_updated = true; | |
91942321 | 727 | set_inode_flag(inode, FI_NO_EXTENT); |
a28ef1f5 | 728 | } |
19b2c30d | 729 | } |
a28ef1f5 | 730 | |
91942321 | 731 | if (is_inode_flag_set(inode, FI_NO_EXTENT)) |
201ef5e0 | 732 | __free_extent_tree(sbi, et); |
a28ef1f5 | 733 | |
b430f726 ZZ |
734 | if (et->largest_updated) { |
735 | et->largest_updated = false; | |
736 | updated = true; | |
737 | } | |
71644dff JK |
738 | goto out_read_extent_cache; |
739 | update_age_extent_cache: | |
740 | if (!tei->last_blocks) | |
741 | goto out_read_extent_cache; | |
b430f726 | 742 | |
71644dff JK |
743 | __set_extent_info(&ei, fofs, len, 0, false, |
744 | tei->age, tei->last_blocks, EX_BLOCK_AGE); | |
745 | if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en)) | |
746 | __insert_extent_tree(sbi, et, &ei, | |
747 | insert_p, insert_parent, leftmost); | |
748 | out_read_extent_cache: | |
a28ef1f5 | 749 | write_unlock(&et->lock); |
b430f726 ZZ |
750 | |
751 | if (updated) | |
752 | f2fs_mark_inode_dirty_sync(inode, true); | |
a28ef1f5 CY |
753 | } |
754 | ||
94afd6d6 | 755 | #ifdef CONFIG_F2FS_FS_COMPRESSION |
e7547dac | 756 | void f2fs_update_read_extent_tree_range_compressed(struct inode *inode, |
94afd6d6 CY |
757 | pgoff_t fofs, block_t blkaddr, unsigned int llen, |
758 | unsigned int c_len) | |
759 | { | |
760 | struct f2fs_sb_info *sbi = F2FS_I_SB(inode); | |
e7547dac | 761 | struct extent_tree *et = F2FS_I(inode)->extent_tree[EX_READ]; |
94afd6d6 CY |
762 | struct extent_node *en = NULL; |
763 | struct extent_node *prev_en = NULL, *next_en = NULL; | |
764 | struct extent_info ei; | |
765 | struct rb_node **insert_p = NULL, *insert_parent = NULL; | |
766 | bool leftmost = false; | |
767 | ||
e7547dac JK |
768 | trace_f2fs_update_read_extent_tree_range(inode, fofs, llen, |
769 | blkaddr, c_len); | |
94afd6d6 CY |
770 | |
771 | /* it is safe here to check FI_NO_EXTENT w/o et->lock in ro image */ | |
772 | if (is_inode_flag_set(inode, FI_NO_EXTENT)) | |
773 | return; | |
774 | ||
775 | write_lock(&et->lock); | |
776 | ||
bf21acf9 JK |
777 | en = __lookup_extent_node_ret(&et->root, |
778 | et->cached_en, fofs, | |
779 | &prev_en, &next_en, | |
780 | &insert_p, &insert_parent, | |
781 | &leftmost); | |
94afd6d6 CY |
782 | if (en) |
783 | goto unlock_out; | |
784 | ||
71644dff | 785 | __set_extent_info(&ei, fofs, llen, blkaddr, true, 0, 0, EX_READ); |
94afd6d6 CY |
786 | ei.c_len = c_len; |
787 | ||
788 | if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en)) | |
789 | __insert_extent_tree(sbi, et, &ei, | |
790 | insert_p, insert_parent, leftmost); | |
791 | unlock_out: | |
792 | write_unlock(&et->lock); | |
793 | } | |
794 | #endif | |
795 | ||
d23be468 | 796 | static unsigned long long __calculate_block_age(struct f2fs_sb_info *sbi, |
797 | unsigned long long new, | |
71644dff JK |
798 | unsigned long long old) |
799 | { | |
b03a41a4 | 800 | unsigned int rem_old, rem_new; |
801 | unsigned long long res; | |
d23be468 | 802 | unsigned int weight = sbi->last_age_weight; |
71644dff | 803 | |
d23be468 | 804 | res = div_u64_rem(new, 100, &rem_new) * (100 - weight) |
805 | + div_u64_rem(old, 100, &rem_old) * weight; | |
71644dff | 806 | |
b03a41a4 | 807 | if (rem_new) |
d23be468 | 808 | res += rem_new * (100 - weight) / 100; |
b03a41a4 | 809 | if (rem_old) |
d23be468 | 810 | res += rem_old * weight / 100; |
b03a41a4 | 811 | |
812 | return res; | |
71644dff JK |
813 | } |
814 | ||
815 | /* This returns a new age and allocated blocks in ei */ | |
ed272476 JK |
816 | static int __get_new_block_age(struct inode *inode, struct extent_info *ei, |
817 | block_t blkaddr) | |
71644dff JK |
818 | { |
819 | struct f2fs_sb_info *sbi = F2FS_I_SB(inode); | |
820 | loff_t f_size = i_size_read(inode); | |
821 | unsigned long long cur_blocks = | |
822 | atomic64_read(&sbi->allocated_data_blocks); | |
22a341b4 | 823 | struct extent_info tei = *ei; /* only fofs and len are valid */ |
71644dff JK |
824 | |
825 | /* | |
826 | * When I/O is not aligned to a PAGE_SIZE, update will happen to the last | |
827 | * file block even in seq write. So don't record age for newly last file | |
828 | * block here. | |
829 | */ | |
830 | if ((f_size >> PAGE_SHIFT) == ei->fofs && f_size & (PAGE_SIZE - 1) && | |
ed272476 | 831 | blkaddr == NEW_ADDR) |
71644dff JK |
832 | return -EINVAL; |
833 | ||
22a341b4 | 834 | if (__lookup_extent_tree(inode, ei->fofs, &tei, EX_BLOCK_AGE)) { |
71644dff JK |
835 | unsigned long long cur_age; |
836 | ||
22a341b4 JK |
837 | if (cur_blocks >= tei.last_blocks) |
838 | cur_age = cur_blocks - tei.last_blocks; | |
71644dff JK |
839 | else |
840 | /* allocated_data_blocks overflow */ | |
22a341b4 | 841 | cur_age = ULLONG_MAX - tei.last_blocks + cur_blocks; |
71644dff | 842 | |
22a341b4 | 843 | if (tei.age) |
d23be468 | 844 | ei->age = __calculate_block_age(sbi, cur_age, tei.age); |
71644dff JK |
845 | else |
846 | ei->age = cur_age; | |
847 | ei->last_blocks = cur_blocks; | |
848 | WARN_ON(ei->age > cur_blocks); | |
849 | return 0; | |
850 | } | |
851 | ||
ed272476 | 852 | f2fs_bug_on(sbi, blkaddr == NULL_ADDR); |
71644dff JK |
853 | |
854 | /* the data block was allocated for the first time */ | |
ed272476 | 855 | if (blkaddr == NEW_ADDR) |
71644dff JK |
856 | goto out; |
857 | ||
ed272476 JK |
858 | if (__is_valid_data_blkaddr(blkaddr) && |
859 | !f2fs_is_valid_blkaddr(sbi, blkaddr, DATA_GENERIC_ENHANCE)) { | |
71644dff JK |
860 | f2fs_bug_on(sbi, 1); |
861 | return -EINVAL; | |
862 | } | |
863 | out: | |
864 | /* | |
865 | * init block age with zero, this can happen when the block age extent | |
866 | * was reclaimed due to memory constraint or system reboot | |
867 | */ | |
868 | ei->age = 0; | |
869 | ei->last_blocks = cur_blocks; | |
870 | return 0; | |
871 | } | |
872 | ||
e7547dac | 873 | static void __update_extent_cache(struct dnode_of_data *dn, enum extent_type type) |
a28ef1f5 | 874 | { |
fe59109a | 875 | struct extent_info ei = {}; |
e7547dac JK |
876 | |
877 | if (!__may_extent_tree(dn->inode, type)) | |
878 | return; | |
879 | ||
880 | ei.fofs = f2fs_start_bidx_of_node(ofs_of_node(dn->node_page), dn->inode) + | |
881 | dn->ofs_in_node; | |
882 | ei.len = 1; | |
883 | ||
884 | if (type == EX_READ) { | |
885 | if (dn->data_blkaddr == NEW_ADDR) | |
886 | ei.blk = NULL_ADDR; | |
887 | else | |
888 | ei.blk = dn->data_blkaddr; | |
71644dff | 889 | } else if (type == EX_BLOCK_AGE) { |
ed272476 | 890 | if (__get_new_block_age(dn->inode, &ei, dn->data_blkaddr)) |
71644dff | 891 | return; |
e7547dac JK |
892 | } |
893 | __update_extent_tree_range(dn->inode, &ei, type); | |
894 | } | |
895 | ||
896 | static unsigned int __shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink, | |
897 | enum extent_type type) | |
898 | { | |
899 | struct extent_tree_info *eti = &sbi->extent_tree[type]; | |
137d09f0 | 900 | struct extent_tree *et, *next; |
201ef5e0 | 901 | struct extent_node *en; |
a28ef1f5 CY |
902 | unsigned int node_cnt = 0, tree_cnt = 0; |
903 | int remained; | |
904 | ||
e7547dac | 905 | if (!atomic_read(&eti->total_zombie_tree)) |
74fd8d99 JK |
906 | goto free_node; |
907 | ||
e7547dac | 908 | if (!mutex_trylock(&eti->extent_tree_lock)) |
a28ef1f5 CY |
909 | goto out; |
910 | ||
911 | /* 1. remove unreferenced extent tree */ | |
e7547dac | 912 | list_for_each_entry_safe(et, next, &eti->zombie_list, list) { |
9b72a388 CY |
913 | if (atomic_read(&et->node_cnt)) { |
914 | write_lock(&et->lock); | |
201ef5e0 | 915 | node_cnt += __free_extent_tree(sbi, et); |
9b72a388 CY |
916 | write_unlock(&et->lock); |
917 | } | |
201ef5e0 | 918 | f2fs_bug_on(sbi, atomic_read(&et->node_cnt)); |
137d09f0 | 919 | list_del_init(&et->list); |
e7547dac | 920 | radix_tree_delete(&eti->extent_tree_root, et->ino); |
137d09f0 | 921 | kmem_cache_free(extent_tree_slab, et); |
e7547dac JK |
922 | atomic_dec(&eti->total_ext_tree); |
923 | atomic_dec(&eti->total_zombie_tree); | |
137d09f0 | 924 | tree_cnt++; |
a28ef1f5 | 925 | |
137d09f0 JK |
926 | if (node_cnt + tree_cnt >= nr_shrink) |
927 | goto unlock_out; | |
6fe2bc95 | 928 | cond_resched(); |
a28ef1f5 | 929 | } |
e7547dac | 930 | mutex_unlock(&eti->extent_tree_lock); |
a28ef1f5 | 931 | |
74fd8d99 | 932 | free_node: |
a28ef1f5 | 933 | /* 2. remove LRU extent entries */ |
e7547dac | 934 | if (!mutex_trylock(&eti->extent_tree_lock)) |
a28ef1f5 CY |
935 | goto out; |
936 | ||
937 | remained = nr_shrink - (node_cnt + tree_cnt); | |
938 | ||
e7547dac | 939 | spin_lock(&eti->extent_lock); |
201ef5e0 | 940 | for (; remained > 0; remained--) { |
e7547dac | 941 | if (list_empty(&eti->extent_list)) |
a28ef1f5 | 942 | break; |
e7547dac | 943 | en = list_first_entry(&eti->extent_list, |
201ef5e0 HP |
944 | struct extent_node, list); |
945 | et = en->et; | |
946 | if (!write_trylock(&et->lock)) { | |
947 | /* refresh this extent node's position in extent list */ | |
e7547dac | 948 | list_move_tail(&en->list, &eti->extent_list); |
201ef5e0 HP |
949 | continue; |
950 | } | |
a28ef1f5 | 951 | |
201ef5e0 | 952 | list_del_init(&en->list); |
e7547dac | 953 | spin_unlock(&eti->extent_lock); |
9b72a388 | 954 | |
201ef5e0 | 955 | __detach_extent_node(sbi, et, en); |
a28ef1f5 | 956 | |
201ef5e0 HP |
957 | write_unlock(&et->lock); |
958 | node_cnt++; | |
e7547dac | 959 | spin_lock(&eti->extent_lock); |
a28ef1f5 | 960 | } |
e7547dac | 961 | spin_unlock(&eti->extent_lock); |
201ef5e0 | 962 | |
a28ef1f5 | 963 | unlock_out: |
e7547dac | 964 | mutex_unlock(&eti->extent_tree_lock); |
a28ef1f5 | 965 | out: |
e7547dac | 966 | trace_f2fs_shrink_extent_tree(sbi, node_cnt, tree_cnt, type); |
a28ef1f5 CY |
967 | |
968 | return node_cnt + tree_cnt; | |
969 | } | |
970 | ||
e7547dac JK |
971 | /* read extent cache operations */ |
972 | bool f2fs_lookup_read_extent_cache(struct inode *inode, pgoff_t pgofs, | |
973 | struct extent_info *ei) | |
974 | { | |
975 | if (!__may_extent_tree(inode, EX_READ)) | |
976 | return false; | |
977 | ||
978 | return __lookup_extent_tree(inode, pgofs, ei, EX_READ); | |
979 | } | |
980 | ||
04a91ab0 CH |
981 | bool f2fs_lookup_read_extent_cache_block(struct inode *inode, pgoff_t index, |
982 | block_t *blkaddr) | |
983 | { | |
984 | struct extent_info ei = {}; | |
985 | ||
986 | if (!f2fs_lookup_read_extent_cache(inode, index, &ei)) | |
987 | return false; | |
988 | *blkaddr = ei.blk + index - ei.fofs; | |
989 | return true; | |
990 | } | |
991 | ||
e7547dac JK |
992 | void f2fs_update_read_extent_cache(struct dnode_of_data *dn) |
993 | { | |
994 | return __update_extent_cache(dn, EX_READ); | |
995 | } | |
996 | ||
997 | void f2fs_update_read_extent_cache_range(struct dnode_of_data *dn, | |
998 | pgoff_t fofs, block_t blkaddr, unsigned int len) | |
999 | { | |
1000 | struct extent_info ei = { | |
1001 | .fofs = fofs, | |
1002 | .len = len, | |
1003 | .blk = blkaddr, | |
1004 | }; | |
1005 | ||
1006 | if (!__may_extent_tree(dn->inode, EX_READ)) | |
1007 | return; | |
1008 | ||
1009 | __update_extent_tree_range(dn->inode, &ei, EX_READ); | |
1010 | } | |
1011 | ||
1012 | unsigned int f2fs_shrink_read_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink) | |
1013 | { | |
1014 | if (!test_opt(sbi, READ_EXTENT_CACHE)) | |
1015 | return 0; | |
1016 | ||
1017 | return __shrink_extent_tree(sbi, nr_shrink, EX_READ); | |
1018 | } | |
1019 | ||
71644dff JK |
1020 | /* block age extent cache operations */ |
1021 | bool f2fs_lookup_age_extent_cache(struct inode *inode, pgoff_t pgofs, | |
1022 | struct extent_info *ei) | |
1023 | { | |
1024 | if (!__may_extent_tree(inode, EX_BLOCK_AGE)) | |
1025 | return false; | |
1026 | ||
1027 | return __lookup_extent_tree(inode, pgofs, ei, EX_BLOCK_AGE); | |
1028 | } | |
1029 | ||
1030 | void f2fs_update_age_extent_cache(struct dnode_of_data *dn) | |
1031 | { | |
1032 | return __update_extent_cache(dn, EX_BLOCK_AGE); | |
1033 | } | |
1034 | ||
1035 | void f2fs_update_age_extent_cache_range(struct dnode_of_data *dn, | |
1036 | pgoff_t fofs, unsigned int len) | |
1037 | { | |
1038 | struct extent_info ei = { | |
1039 | .fofs = fofs, | |
1040 | .len = len, | |
1041 | }; | |
1042 | ||
1043 | if (!__may_extent_tree(dn->inode, EX_BLOCK_AGE)) | |
1044 | return; | |
1045 | ||
1046 | __update_extent_tree_range(dn->inode, &ei, EX_BLOCK_AGE); | |
1047 | } | |
1048 | ||
1049 | unsigned int f2fs_shrink_age_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink) | |
1050 | { | |
1051 | if (!test_opt(sbi, AGE_EXTENT_CACHE)) | |
1052 | return 0; | |
1053 | ||
1054 | return __shrink_extent_tree(sbi, nr_shrink, EX_BLOCK_AGE); | |
1055 | } | |
1056 | ||
e7547dac JK |
1057 | static unsigned int __destroy_extent_node(struct inode *inode, |
1058 | enum extent_type type) | |
a28ef1f5 CY |
1059 | { |
1060 | struct f2fs_sb_info *sbi = F2FS_I_SB(inode); | |
e7547dac | 1061 | struct extent_tree *et = F2FS_I(inode)->extent_tree[type]; |
a28ef1f5 CY |
1062 | unsigned int node_cnt = 0; |
1063 | ||
9b72a388 | 1064 | if (!et || !atomic_read(&et->node_cnt)) |
a28ef1f5 CY |
1065 | return 0; |
1066 | ||
1067 | write_lock(&et->lock); | |
201ef5e0 | 1068 | node_cnt = __free_extent_tree(sbi, et); |
a28ef1f5 CY |
1069 | write_unlock(&et->lock); |
1070 | ||
1071 | return node_cnt; | |
1072 | } | |
1073 | ||
e7547dac JK |
1074 | void f2fs_destroy_extent_node(struct inode *inode) |
1075 | { | |
1076 | __destroy_extent_node(inode, EX_READ); | |
71644dff | 1077 | __destroy_extent_node(inode, EX_BLOCK_AGE); |
e7547dac JK |
1078 | } |
1079 | ||
1080 | static void __drop_extent_tree(struct inode *inode, enum extent_type type) | |
5f281fab JK |
1081 | { |
1082 | struct f2fs_sb_info *sbi = F2FS_I_SB(inode); | |
e7547dac | 1083 | struct extent_tree *et = F2FS_I(inode)->extent_tree[type]; |
b430f726 | 1084 | bool updated = false; |
5f281fab | 1085 | |
e7547dac | 1086 | if (!__may_extent_tree(inode, type)) |
bf617f7a CY |
1087 | return; |
1088 | ||
5f281fab JK |
1089 | write_lock(&et->lock); |
1090 | __free_extent_tree(sbi, et); | |
e7547dac JK |
1091 | if (type == EX_READ) { |
1092 | set_inode_flag(inode, FI_NO_EXTENT); | |
1093 | if (et->largest.len) { | |
1094 | et->largest.len = 0; | |
1095 | updated = true; | |
1096 | } | |
b430f726 | 1097 | } |
5f281fab | 1098 | write_unlock(&et->lock); |
b430f726 ZZ |
1099 | if (updated) |
1100 | f2fs_mark_inode_dirty_sync(inode, true); | |
5f281fab JK |
1101 | } |
1102 | ||
e7547dac JK |
1103 | void f2fs_drop_extent_tree(struct inode *inode) |
1104 | { | |
1105 | __drop_extent_tree(inode, EX_READ); | |
71644dff | 1106 | __drop_extent_tree(inode, EX_BLOCK_AGE); |
e7547dac JK |
1107 | } |
1108 | ||
1109 | static void __destroy_extent_tree(struct inode *inode, enum extent_type type) | |
a28ef1f5 CY |
1110 | { |
1111 | struct f2fs_sb_info *sbi = F2FS_I_SB(inode); | |
e7547dac JK |
1112 | struct extent_tree_info *eti = &sbi->extent_tree[type]; |
1113 | struct extent_tree *et = F2FS_I(inode)->extent_tree[type]; | |
a28ef1f5 CY |
1114 | unsigned int node_cnt = 0; |
1115 | ||
1116 | if (!et) | |
1117 | return; | |
1118 | ||
68e35385 CY |
1119 | if (inode->i_nlink && !is_bad_inode(inode) && |
1120 | atomic_read(&et->node_cnt)) { | |
e7547dac JK |
1121 | mutex_lock(&eti->extent_tree_lock); |
1122 | list_add_tail(&et->list, &eti->zombie_list); | |
1123 | atomic_inc(&eti->total_zombie_tree); | |
1124 | mutex_unlock(&eti->extent_tree_lock); | |
a28ef1f5 CY |
1125 | return; |
1126 | } | |
1127 | ||
1128 | /* free all extent info belong to this extent tree */ | |
e7547dac | 1129 | node_cnt = __destroy_extent_node(inode, type); |
a28ef1f5 CY |
1130 | |
1131 | /* delete extent tree entry in radix tree */ | |
e7547dac | 1132 | mutex_lock(&eti->extent_tree_lock); |
68e35385 | 1133 | f2fs_bug_on(sbi, atomic_read(&et->node_cnt)); |
e7547dac | 1134 | radix_tree_delete(&eti->extent_tree_root, inode->i_ino); |
a28ef1f5 | 1135 | kmem_cache_free(extent_tree_slab, et); |
e7547dac JK |
1136 | atomic_dec(&eti->total_ext_tree); |
1137 | mutex_unlock(&eti->extent_tree_lock); | |
a28ef1f5 | 1138 | |
e7547dac | 1139 | F2FS_I(inode)->extent_tree[type] = NULL; |
a28ef1f5 | 1140 | |
e7547dac | 1141 | trace_f2fs_destroy_extent_tree(inode, node_cnt, type); |
a28ef1f5 CY |
1142 | } |
1143 | ||
e7547dac | 1144 | void f2fs_destroy_extent_tree(struct inode *inode) |
a28ef1f5 | 1145 | { |
e7547dac | 1146 | __destroy_extent_tree(inode, EX_READ); |
71644dff | 1147 | __destroy_extent_tree(inode, EX_BLOCK_AGE); |
19b2c30d CY |
1148 | } |
1149 | ||
e7547dac | 1150 | static void __init_extent_tree_info(struct extent_tree_info *eti) |
19b2c30d | 1151 | { |
e7547dac JK |
1152 | INIT_RADIX_TREE(&eti->extent_tree_root, GFP_NOIO); |
1153 | mutex_init(&eti->extent_tree_lock); | |
1154 | INIT_LIST_HEAD(&eti->extent_list); | |
1155 | spin_lock_init(&eti->extent_lock); | |
1156 | atomic_set(&eti->total_ext_tree, 0); | |
1157 | INIT_LIST_HEAD(&eti->zombie_list); | |
1158 | atomic_set(&eti->total_zombie_tree, 0); | |
1159 | atomic_set(&eti->total_ext_node, 0); | |
a28ef1f5 CY |
1160 | } |
1161 | ||
4d57b86d | 1162 | void f2fs_init_extent_cache_info(struct f2fs_sb_info *sbi) |
a28ef1f5 | 1163 | { |
e7547dac | 1164 | __init_extent_tree_info(&sbi->extent_tree[EX_READ]); |
71644dff JK |
1165 | __init_extent_tree_info(&sbi->extent_tree[EX_BLOCK_AGE]); |
1166 | ||
1167 | /* initialize for block age extents */ | |
1168 | atomic64_set(&sbi->allocated_data_blocks, 0); | |
1169 | sbi->hot_data_age_threshold = DEF_HOT_DATA_AGE_THRESHOLD; | |
1170 | sbi->warm_data_age_threshold = DEF_WARM_DATA_AGE_THRESHOLD; | |
d23be468 | 1171 | sbi->last_age_weight = LAST_AGE_WEIGHT; |
a28ef1f5 CY |
1172 | } |
1173 | ||
4d57b86d | 1174 | int __init f2fs_create_extent_cache(void) |
a28ef1f5 CY |
1175 | { |
1176 | extent_tree_slab = f2fs_kmem_cache_create("f2fs_extent_tree", | |
1177 | sizeof(struct extent_tree)); | |
1178 | if (!extent_tree_slab) | |
1179 | return -ENOMEM; | |
1180 | extent_node_slab = f2fs_kmem_cache_create("f2fs_extent_node", | |
1181 | sizeof(struct extent_node)); | |
1182 | if (!extent_node_slab) { | |
1183 | kmem_cache_destroy(extent_tree_slab); | |
1184 | return -ENOMEM; | |
1185 | } | |
1186 | return 0; | |
1187 | } | |
1188 | ||
4d57b86d | 1189 | void f2fs_destroy_extent_cache(void) |
a28ef1f5 CY |
1190 | { |
1191 | kmem_cache_destroy(extent_node_slab); | |
1192 | kmem_cache_destroy(extent_tree_slab); | |
1193 | } |