Branch data Line data Source code
1 : : // SPDX-License-Identifier: GPL-2.0
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>
9 : : */
10 : :
11 : : #include <linux/fs.h>
12 : : #include <linux/f2fs_fs.h>
13 : :
14 : : #include "f2fs.h"
15 : : #include "node.h"
16 : : #include <trace/events/f2fs.h>
17 : :
18 : : static struct rb_entry *__lookup_rb_tree_fast(struct rb_entry *cached_re,
19 : : unsigned int ofs)
20 : : {
21 : 0 : if (cached_re) {
22 : 0 : if (cached_re->ofs <= ofs &&
23 : 0 : cached_re->ofs + cached_re->len > ofs) {
24 : : return cached_re;
25 : : }
26 : : }
27 : : return NULL;
28 : : }
29 : :
30 : : static struct rb_entry *__lookup_rb_tree_slow(struct rb_root_cached *root,
31 : : unsigned int ofs)
32 : : {
33 : 0 : struct rb_node *node = root->rb_root.rb_node;
34 : : struct rb_entry *re;
35 : :
36 : 0 : while (node) {
37 : : re = rb_entry(node, struct rb_entry, rb_node);
38 : :
39 : 0 : if (ofs < re->ofs)
40 : 0 : node = node->rb_left;
41 : 0 : else if (ofs >= re->ofs + re->len)
42 : 0 : node = node->rb_right;
43 : : else
44 : 0 : return re;
45 : : }
46 : : return NULL;
47 : : }
48 : :
49 : 0 : struct rb_entry *f2fs_lookup_rb_tree(struct rb_root_cached *root,
50 : : struct rb_entry *cached_re, unsigned int ofs)
51 : : {
52 : : struct rb_entry *re;
53 : :
54 : : re = __lookup_rb_tree_fast(cached_re, ofs);
55 : 0 : if (!re)
56 : 0 : return __lookup_rb_tree_slow(root, ofs);
57 : :
58 : : return re;
59 : : }
60 : :
61 : 0 : struct rb_node **f2fs_lookup_rb_tree_for_insert(struct f2fs_sb_info *sbi,
62 : : struct rb_root_cached *root,
63 : : struct rb_node **parent,
64 : : unsigned int ofs, bool *leftmost)
65 : : {
66 : 0 : struct rb_node **p = &root->rb_root.rb_node;
67 : : struct rb_entry *re;
68 : :
69 : 0 : while (*p) {
70 : 0 : *parent = *p;
71 : : re = rb_entry(*parent, struct rb_entry, rb_node);
72 : :
73 : 0 : if (ofs < re->ofs) {
74 : 0 : p = &(*p)->rb_left;
75 : 0 : } else if (ofs >= re->ofs + re->len) {
76 : 0 : p = &(*p)->rb_right;
77 : 0 : *leftmost = false;
78 : : } else {
79 : 0 : f2fs_bug_on(sbi, 1);
80 : : }
81 : : }
82 : :
83 : 0 : return p;
84 : : }
85 : :
86 : : /*
87 : : * lookup rb entry in position of @ofs in rb-tree,
88 : : * if hit, return the entry, otherwise, return NULL
89 : : * @prev_ex: extent before ofs
90 : : * @next_ex: extent after ofs
91 : : * @insert_p: insert point for new extent at ofs
92 : : * in order to simpfy the insertion after.
93 : : * tree must stay unchanged between lookup and insertion.
94 : : */
95 : 0 : struct rb_entry *f2fs_lookup_rb_tree_ret(struct rb_root_cached *root,
96 : : struct rb_entry *cached_re,
97 : : unsigned int ofs,
98 : : struct rb_entry **prev_entry,
99 : : struct rb_entry **next_entry,
100 : : struct rb_node ***insert_p,
101 : : struct rb_node **insert_parent,
102 : : bool force, bool *leftmost)
103 : : {
104 : 0 : struct rb_node **pnode = &root->rb_root.rb_node;
105 : : struct rb_node *parent = NULL, *tmp_node;
106 : : struct rb_entry *re = cached_re;
107 : :
108 : 0 : *insert_p = NULL;
109 : 0 : *insert_parent = NULL;
110 : 0 : *prev_entry = NULL;
111 : 0 : *next_entry = NULL;
112 : :
113 : 0 : if (RB_EMPTY_ROOT(&root->rb_root))
114 : : return NULL;
115 : :
116 : 0 : if (re) {
117 : 0 : if (re->ofs <= ofs && re->ofs + re->len > ofs)
118 : : goto lookup_neighbors;
119 : : }
120 : :
121 : 0 : if (leftmost)
122 : 0 : *leftmost = true;
123 : :
124 : 0 : while (*pnode) {
125 : : parent = *pnode;
126 : : re = rb_entry(*pnode, struct rb_entry, rb_node);
127 : :
128 : 0 : if (ofs < re->ofs) {
129 : 0 : pnode = &(*pnode)->rb_left;
130 : 0 : } else if (ofs >= re->ofs + re->len) {
131 : 0 : pnode = &(*pnode)->rb_right;
132 : 0 : if (leftmost)
133 : 0 : *leftmost = false;
134 : : } else {
135 : : goto lookup_neighbors;
136 : : }
137 : : }
138 : :
139 : 0 : *insert_p = pnode;
140 : 0 : *insert_parent = parent;
141 : :
142 : 0 : re = rb_entry(parent, struct rb_entry, rb_node);
143 : 0 : tmp_node = parent;
144 : 0 : if (parent && ofs > re->ofs)
145 : 0 : tmp_node = rb_next(parent);
146 : 0 : *next_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node);
147 : :
148 : 0 : tmp_node = parent;
149 : 0 : if (parent && ofs < re->ofs)
150 : 0 : tmp_node = rb_prev(parent);
151 : 0 : *prev_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node);
152 : 0 : return NULL;
153 : :
154 : : lookup_neighbors:
155 : 0 : if (ofs == re->ofs || force) {
156 : : /* lookup prev node for merging backward later */
157 : 0 : tmp_node = rb_prev(&re->rb_node);
158 : 0 : *prev_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node);
159 : : }
160 : 0 : if (ofs == re->ofs + re->len - 1 || force) {
161 : : /* lookup next node for merging frontward later */
162 : 0 : tmp_node = rb_next(&re->rb_node);
163 : 0 : *next_entry = rb_entry_safe(tmp_node, struct rb_entry, rb_node);
164 : : }
165 : 0 : return re;
166 : : }
167 : :
168 : 0 : bool f2fs_check_rb_tree_consistence(struct f2fs_sb_info *sbi,
169 : : struct rb_root_cached *root)
170 : : {
171 : : #ifdef CONFIG_F2FS_CHECK_FS
172 : : struct rb_node *cur = rb_first_cached(root), *next;
173 : : struct rb_entry *cur_re, *next_re;
174 : :
175 : : if (!cur)
176 : : return true;
177 : :
178 : : while (cur) {
179 : : next = rb_next(cur);
180 : : if (!next)
181 : : return true;
182 : :
183 : : cur_re = rb_entry(cur, struct rb_entry, rb_node);
184 : : next_re = rb_entry(next, struct rb_entry, rb_node);
185 : :
186 : : if (cur_re->ofs + cur_re->len > next_re->ofs) {
187 : : f2fs_info(sbi, "inconsistent rbtree, cur(%u, %u) next(%u, %u)",
188 : : cur_re->ofs, cur_re->len,
189 : : next_re->ofs, next_re->len);
190 : : return false;
191 : : }
192 : :
193 : : cur = next;
194 : : }
195 : : #endif
196 : 0 : return true;
197 : : }
198 : :
199 : : static struct kmem_cache *extent_tree_slab;
200 : : static struct kmem_cache *extent_node_slab;
201 : :
202 : 0 : static struct extent_node *__attach_extent_node(struct f2fs_sb_info *sbi,
203 : : struct extent_tree *et, struct extent_info *ei,
204 : : struct rb_node *parent, struct rb_node **p,
205 : : bool leftmost)
206 : : {
207 : : struct extent_node *en;
208 : :
209 : 0 : en = kmem_cache_alloc(extent_node_slab, GFP_ATOMIC);
210 : 0 : if (!en)
211 : : return NULL;
212 : :
213 : 0 : en->ei = *ei;
214 : 0 : INIT_LIST_HEAD(&en->list);
215 : 0 : en->et = et;
216 : :
217 : 0 : rb_link_node(&en->rb_node, parent, p);
218 : : rb_insert_color_cached(&en->rb_node, &et->root, leftmost);
219 : 0 : atomic_inc(&et->node_cnt);
220 : 0 : atomic_inc(&sbi->total_ext_node);
221 : 0 : return en;
222 : : }
223 : :
224 : 0 : static void __detach_extent_node(struct f2fs_sb_info *sbi,
225 : : struct extent_tree *et, struct extent_node *en)
226 : : {
227 : 0 : rb_erase_cached(&en->rb_node, &et->root);
228 : 0 : atomic_dec(&et->node_cnt);
229 : 0 : atomic_dec(&sbi->total_ext_node);
230 : :
231 : 0 : if (et->cached_en == en)
232 : 0 : et->cached_en = NULL;
233 : 0 : kmem_cache_free(extent_node_slab, en);
234 : 0 : }
235 : :
236 : : /*
237 : : * Flow to release an extent_node:
238 : : * 1. list_del_init
239 : : * 2. __detach_extent_node
240 : : * 3. kmem_cache_free.
241 : : */
242 : 0 : static void __release_extent_node(struct f2fs_sb_info *sbi,
243 : : struct extent_tree *et, struct extent_node *en)
244 : : {
245 : : spin_lock(&sbi->extent_lock);
246 : 0 : f2fs_bug_on(sbi, list_empty(&en->list));
247 : : list_del_init(&en->list);
248 : : spin_unlock(&sbi->extent_lock);
249 : :
250 : 0 : __detach_extent_node(sbi, et, en);
251 : 0 : }
252 : :
253 : 0 : static struct extent_tree *__grab_extent_tree(struct inode *inode)
254 : : {
255 : : struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
256 : : struct extent_tree *et;
257 : 0 : nid_t ino = inode->i_ino;
258 : :
259 : 0 : mutex_lock(&sbi->extent_tree_lock);
260 : 0 : et = radix_tree_lookup(&sbi->extent_tree_root, ino);
261 : 0 : if (!et) {
262 : 0 : et = f2fs_kmem_cache_alloc(extent_tree_slab, GFP_NOFS);
263 : 0 : f2fs_radix_tree_insert(&sbi->extent_tree_root, ino, et);
264 : 0 : memset(et, 0, sizeof(struct extent_tree));
265 : 0 : et->ino = ino;
266 : 0 : et->root = RB_ROOT_CACHED;
267 : 0 : et->cached_en = NULL;
268 : 0 : rwlock_init(&et->lock);
269 : 0 : INIT_LIST_HEAD(&et->list);
270 : : atomic_set(&et->node_cnt, 0);
271 : 0 : atomic_inc(&sbi->total_ext_tree);
272 : : } else {
273 : 0 : atomic_dec(&sbi->total_zombie_tree);
274 : 0 : list_del_init(&et->list);
275 : : }
276 : 0 : mutex_unlock(&sbi->extent_tree_lock);
277 : :
278 : : /* never died until evict_inode */
279 : 0 : F2FS_I(inode)->extent_tree = et;
280 : :
281 : 0 : return et;
282 : : }
283 : :
284 : 0 : static struct extent_node *__init_extent_tree(struct f2fs_sb_info *sbi,
285 : : struct extent_tree *et, struct extent_info *ei)
286 : : {
287 : 0 : struct rb_node **p = &et->root.rb_root.rb_node;
288 : : struct extent_node *en;
289 : :
290 : 0 : en = __attach_extent_node(sbi, et, ei, NULL, p, true);
291 : 0 : if (!en)
292 : : return NULL;
293 : :
294 : 0 : et->largest = en->ei;
295 : 0 : et->cached_en = en;
296 : 0 : return en;
297 : : }
298 : :
299 : 0 : static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi,
300 : : struct extent_tree *et)
301 : : {
302 : : struct rb_node *node, *next;
303 : : struct extent_node *en;
304 : : unsigned int count = atomic_read(&et->node_cnt);
305 : :
306 : 0 : node = rb_first_cached(&et->root);
307 : 0 : while (node) {
308 : 0 : next = rb_next(node);
309 : : en = rb_entry(node, struct extent_node, rb_node);
310 : 0 : __release_extent_node(sbi, et, en);
311 : : node = next;
312 : : }
313 : :
314 : 0 : return count - atomic_read(&et->node_cnt);
315 : : }
316 : :
317 : : static void __drop_largest_extent(struct extent_tree *et,
318 : : pgoff_t fofs, unsigned int len)
319 : : {
320 : 0 : if (fofs < et->largest.fofs + et->largest.len &&
321 : : fofs + len > et->largest.fofs) {
322 : 0 : et->largest.len = 0;
323 : 0 : et->largest_updated = true;
324 : : }
325 : : }
326 : :
327 : : /* return true, if inode page is changed */
328 : 0 : static bool __f2fs_init_extent_tree(struct inode *inode, struct f2fs_extent *i_ext)
329 : : {
330 : : struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
331 : : struct extent_tree *et;
332 : : struct extent_node *en;
333 : : struct extent_info ei;
334 : :
335 : 0 : if (!f2fs_may_extent_tree(inode)) {
336 : : /* drop largest extent */
337 : 0 : if (i_ext && i_ext->len) {
338 : 0 : i_ext->len = 0;
339 : 0 : return true;
340 : : }
341 : : return false;
342 : : }
343 : :
344 : 0 : et = __grab_extent_tree(inode);
345 : :
346 : 0 : if (!i_ext || !i_ext->len)
347 : : return false;
348 : :
349 : : get_extent_info(&ei, i_ext);
350 : :
351 : 0 : write_lock(&et->lock);
352 : 0 : if (atomic_read(&et->node_cnt))
353 : : goto out;
354 : :
355 : 0 : en = __init_extent_tree(sbi, et, &ei);
356 : 0 : if (en) {
357 : : spin_lock(&sbi->extent_lock);
358 : 0 : list_add_tail(&en->list, &sbi->extent_list);
359 : : spin_unlock(&sbi->extent_lock);
360 : : }
361 : : out:
362 : : write_unlock(&et->lock);
363 : 0 : return false;
364 : : }
365 : :
366 : 0 : bool f2fs_init_extent_tree(struct inode *inode, struct f2fs_extent *i_ext)
367 : : {
368 : 0 : bool ret = __f2fs_init_extent_tree(inode, i_ext);
369 : :
370 : 0 : if (!F2FS_I(inode)->extent_tree)
371 : 0 : set_inode_flag(inode, FI_NO_EXTENT);
372 : :
373 : 0 : return ret;
374 : : }
375 : :
376 : 0 : static bool f2fs_lookup_extent_tree(struct inode *inode, pgoff_t pgofs,
377 : : struct extent_info *ei)
378 : : {
379 : : struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
380 : 0 : struct extent_tree *et = F2FS_I(inode)->extent_tree;
381 : : struct extent_node *en;
382 : : bool ret = false;
383 : :
384 : 0 : f2fs_bug_on(sbi, !et);
385 : :
386 : 0 : trace_f2fs_lookup_extent_tree_start(inode, pgofs);
387 : :
388 : 0 : read_lock(&et->lock);
389 : :
390 : 0 : if (et->largest.fofs <= pgofs &&
391 : 0 : et->largest.fofs + et->largest.len > pgofs) {
392 : 0 : *ei = et->largest;
393 : : ret = true;
394 : 0 : stat_inc_largest_node_hit(sbi);
395 : 0 : goto out;
396 : : }
397 : :
398 : 0 : en = (struct extent_node *)f2fs_lookup_rb_tree(&et->root,
399 : 0 : (struct rb_entry *)et->cached_en, pgofs);
400 : 0 : if (!en)
401 : : goto out;
402 : :
403 : 0 : if (en == et->cached_en)
404 : 0 : stat_inc_cached_node_hit(sbi);
405 : : else
406 : 0 : stat_inc_rbtree_node_hit(sbi);
407 : :
408 : 0 : *ei = en->ei;
409 : : spin_lock(&sbi->extent_lock);
410 : 0 : if (!list_empty(&en->list)) {
411 : 0 : list_move_tail(&en->list, &sbi->extent_list);
412 : 0 : et->cached_en = en;
413 : : }
414 : : spin_unlock(&sbi->extent_lock);
415 : : ret = true;
416 : : out:
417 : 0 : stat_inc_total_hit(sbi);
418 : : read_unlock(&et->lock);
419 : :
420 : 0 : trace_f2fs_lookup_extent_tree_end(inode, pgofs, ei);
421 : 0 : return ret;
422 : : }
423 : :
424 : 0 : static struct extent_node *__try_merge_extent_node(struct f2fs_sb_info *sbi,
425 : : struct extent_tree *et, struct extent_info *ei,
426 : : struct extent_node *prev_ex,
427 : : struct extent_node *next_ex)
428 : : {
429 : : struct extent_node *en = NULL;
430 : :
431 : 0 : if (prev_ex && __is_back_mergeable(ei, &prev_ex->ei)) {
432 : 0 : prev_ex->ei.len += ei->len;
433 : 0 : ei = &prev_ex->ei;
434 : : en = prev_ex;
435 : : }
436 : :
437 : 0 : if (next_ex && __is_front_mergeable(ei, &next_ex->ei)) {
438 : 0 : next_ex->ei.fofs = ei->fofs;
439 : 0 : next_ex->ei.blk = ei->blk;
440 : 0 : next_ex->ei.len += ei->len;
441 : 0 : if (en)
442 : 0 : __release_extent_node(sbi, et, prev_ex);
443 : :
444 : : en = next_ex;
445 : : }
446 : :
447 : 0 : if (!en)
448 : : return NULL;
449 : :
450 : : __try_update_largest_extent(et, en);
451 : :
452 : : spin_lock(&sbi->extent_lock);
453 : 0 : if (!list_empty(&en->list)) {
454 : 0 : list_move_tail(&en->list, &sbi->extent_list);
455 : 0 : et->cached_en = en;
456 : : }
457 : : spin_unlock(&sbi->extent_lock);
458 : 0 : return en;
459 : : }
460 : :
461 : 0 : static struct extent_node *__insert_extent_tree(struct f2fs_sb_info *sbi,
462 : : struct extent_tree *et, struct extent_info *ei,
463 : : struct rb_node **insert_p,
464 : : struct rb_node *insert_parent,
465 : : bool leftmost)
466 : : {
467 : : struct rb_node **p;
468 : 0 : struct rb_node *parent = NULL;
469 : : struct extent_node *en = NULL;
470 : :
471 : 0 : if (insert_p && insert_parent) {
472 : 0 : parent = insert_parent;
473 : : p = insert_p;
474 : 0 : goto do_insert;
475 : : }
476 : :
477 : 0 : leftmost = true;
478 : :
479 : 0 : p = f2fs_lookup_rb_tree_for_insert(sbi, &et->root, &parent,
480 : : ei->fofs, &leftmost);
481 : : do_insert:
482 : 0 : en = __attach_extent_node(sbi, et, ei, parent, p, leftmost);
483 : 0 : if (!en)
484 : : return NULL;
485 : :
486 : : __try_update_largest_extent(et, en);
487 : :
488 : : /* update in global extent list */
489 : : spin_lock(&sbi->extent_lock);
490 : 0 : list_add_tail(&en->list, &sbi->extent_list);
491 : 0 : et->cached_en = en;
492 : : spin_unlock(&sbi->extent_lock);
493 : 0 : return en;
494 : : }
495 : :
496 : 0 : static void f2fs_update_extent_tree_range(struct inode *inode,
497 : : pgoff_t fofs, block_t blkaddr, unsigned int len)
498 : : {
499 : : struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
500 : 0 : struct extent_tree *et = F2FS_I(inode)->extent_tree;
501 : : struct extent_node *en = NULL, *en1 = NULL;
502 : 0 : struct extent_node *prev_en = NULL, *next_en = NULL;
503 : : struct extent_info ei, dei, prev;
504 : 0 : struct rb_node **insert_p = NULL, *insert_parent = NULL;
505 : 0 : unsigned int end = fofs + len;
506 : : unsigned int pos = (unsigned int)fofs;
507 : : bool updated = false;
508 : 0 : bool leftmost = false;
509 : :
510 : 0 : if (!et)
511 : 0 : return;
512 : :
513 : 0 : trace_f2fs_update_extent_tree_range(inode, fofs, blkaddr, len);
514 : :
515 : 0 : write_lock(&et->lock);
516 : :
517 : 0 : if (is_inode_flag_set(inode, FI_NO_EXTENT)) {
518 : : write_unlock(&et->lock);
519 : : return;
520 : : }
521 : :
522 : 0 : prev = et->largest;
523 : : dei.len = 0;
524 : :
525 : : /*
526 : : * drop largest extent before lookup, in case it's already
527 : : * been shrunk from extent tree
528 : : */
529 : : __drop_largest_extent(et, fofs, len);
530 : :
531 : : /* 1. lookup first extent node in range [fofs, fofs + len - 1] */
532 : 0 : en = (struct extent_node *)f2fs_lookup_rb_tree_ret(&et->root,
533 : 0 : (struct rb_entry *)et->cached_en, fofs,
534 : : (struct rb_entry **)&prev_en,
535 : : (struct rb_entry **)&next_en,
536 : : &insert_p, &insert_parent, false,
537 : : &leftmost);
538 : 0 : if (!en)
539 : 0 : en = next_en;
540 : :
541 : : /* 2. invlidate all extent nodes in range [fofs, fofs + len - 1] */
542 : 0 : while (en && en->ei.fofs < end) {
543 : : unsigned int org_end;
544 : : int parts = 0; /* # of parts current extent split into */
545 : :
546 : 0 : next_en = en1 = NULL;
547 : :
548 : 0 : dei = en->ei;
549 : 0 : org_end = dei.fofs + dei.len;
550 : 0 : f2fs_bug_on(sbi, pos >= org_end);
551 : :
552 : 0 : if (pos > dei.fofs && pos - dei.fofs >= F2FS_MIN_EXTENT_LEN) {
553 : 0 : en->ei.len = pos - en->ei.fofs;
554 : 0 : prev_en = en;
555 : : parts = 1;
556 : : }
557 : :
558 : 0 : if (end < org_end && org_end - end >= F2FS_MIN_EXTENT_LEN) {
559 : 0 : if (parts) {
560 : 0 : set_extent_info(&ei, end,
561 : 0 : end - dei.fofs + dei.blk,
562 : : org_end - end);
563 : 0 : en1 = __insert_extent_tree(sbi, et, &ei,
564 : : NULL, NULL, true);
565 : 0 : next_en = en1;
566 : : } else {
567 : 0 : en->ei.fofs = end;
568 : 0 : en->ei.blk += end - dei.fofs;
569 : 0 : en->ei.len -= end - dei.fofs;
570 : 0 : next_en = en;
571 : : }
572 : 0 : parts++;
573 : : }
574 : :
575 : 0 : if (!next_en) {
576 : 0 : struct rb_node *node = rb_next(&en->rb_node);
577 : :
578 : 0 : next_en = rb_entry_safe(node, struct extent_node,
579 : : rb_node);
580 : : }
581 : :
582 : 0 : if (parts)
583 : : __try_update_largest_extent(et, en);
584 : : else
585 : 0 : __release_extent_node(sbi, et, en);
586 : :
587 : : /*
588 : : * if original extent is split into zero or two parts, extent
589 : : * tree has been altered by deletion or insertion, therefore
590 : : * invalidate pointers regard to tree.
591 : : */
592 : 0 : if (parts != 1) {
593 : 0 : insert_p = NULL;
594 : 0 : insert_parent = NULL;
595 : : }
596 : 0 : en = next_en;
597 : : }
598 : :
599 : : /* 3. update extent in extent cache */
600 : 0 : if (blkaddr) {
601 : :
602 : : set_extent_info(&ei, fofs, blkaddr, len);
603 : 0 : if (!__try_merge_extent_node(sbi, et, &ei, prev_en, next_en))
604 : 0 : __insert_extent_tree(sbi, et, &ei,
605 : : insert_p, insert_parent, leftmost);
606 : :
607 : : /* give up extent_cache, if split and small updates happen */
608 : 0 : if (dei.len >= 1 &&
609 : 0 : prev.len < F2FS_MIN_EXTENT_LEN &&
610 : 0 : et->largest.len < F2FS_MIN_EXTENT_LEN) {
611 : 0 : et->largest.len = 0;
612 : 0 : et->largest_updated = true;
613 : 0 : set_inode_flag(inode, FI_NO_EXTENT);
614 : : }
615 : : }
616 : :
617 : 0 : if (is_inode_flag_set(inode, FI_NO_EXTENT))
618 : 0 : __free_extent_tree(sbi, et);
619 : :
620 : 0 : if (et->largest_updated) {
621 : 0 : et->largest_updated = false;
622 : : updated = true;
623 : : }
624 : :
625 : : write_unlock(&et->lock);
626 : :
627 : 0 : if (updated)
628 : 0 : f2fs_mark_inode_dirty_sync(inode, true);
629 : : }
630 : :
631 : 0 : unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink)
632 : : {
633 : : struct extent_tree *et, *next;
634 : : struct extent_node *en;
635 : : unsigned int node_cnt = 0, tree_cnt = 0;
636 : : int remained;
637 : :
638 : 0 : if (!test_opt(sbi, EXTENT_CACHE))
639 : : return 0;
640 : :
641 : 0 : if (!atomic_read(&sbi->total_zombie_tree))
642 : : goto free_node;
643 : :
644 : 0 : if (!mutex_trylock(&sbi->extent_tree_lock))
645 : : goto out;
646 : :
647 : : /* 1. remove unreferenced extent tree */
648 : 0 : list_for_each_entry_safe(et, next, &sbi->zombie_list, list) {
649 : 0 : if (atomic_read(&et->node_cnt)) {
650 : 0 : write_lock(&et->lock);
651 : 0 : node_cnt += __free_extent_tree(sbi, et);
652 : : write_unlock(&et->lock);
653 : : }
654 : 0 : f2fs_bug_on(sbi, atomic_read(&et->node_cnt));
655 : : list_del_init(&et->list);
656 : 0 : radix_tree_delete(&sbi->extent_tree_root, et->ino);
657 : 0 : kmem_cache_free(extent_tree_slab, et);
658 : 0 : atomic_dec(&sbi->total_ext_tree);
659 : 0 : atomic_dec(&sbi->total_zombie_tree);
660 : 0 : tree_cnt++;
661 : :
662 : 0 : if (node_cnt + tree_cnt >= nr_shrink)
663 : : goto unlock_out;
664 : 0 : cond_resched();
665 : : }
666 : 0 : mutex_unlock(&sbi->extent_tree_lock);
667 : :
668 : : free_node:
669 : : /* 2. remove LRU extent entries */
670 : 0 : if (!mutex_trylock(&sbi->extent_tree_lock))
671 : : goto out;
672 : :
673 : 0 : remained = nr_shrink - (node_cnt + tree_cnt);
674 : :
675 : : spin_lock(&sbi->extent_lock);
676 : 0 : for (; remained > 0; remained--) {
677 : 0 : if (list_empty(&sbi->extent_list))
678 : : break;
679 : 0 : en = list_first_entry(&sbi->extent_list,
680 : : struct extent_node, list);
681 : 0 : et = en->et;
682 : 0 : if (!write_trylock(&et->lock)) {
683 : : /* refresh this extent node's position in extent list */
684 : 0 : list_move_tail(&en->list, &sbi->extent_list);
685 : 0 : continue;
686 : : }
687 : :
688 : 0 : list_del_init(&en->list);
689 : : spin_unlock(&sbi->extent_lock);
690 : :
691 : 0 : __detach_extent_node(sbi, et, en);
692 : :
693 : : write_unlock(&et->lock);
694 : 0 : node_cnt++;
695 : : spin_lock(&sbi->extent_lock);
696 : : }
697 : : spin_unlock(&sbi->extent_lock);
698 : :
699 : : unlock_out:
700 : 0 : mutex_unlock(&sbi->extent_tree_lock);
701 : : out:
702 : 0 : trace_f2fs_shrink_extent_tree(sbi, node_cnt, tree_cnt);
703 : :
704 : 0 : return node_cnt + tree_cnt;
705 : : }
706 : :
707 : 0 : unsigned int f2fs_destroy_extent_node(struct inode *inode)
708 : : {
709 : : struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
710 : 0 : struct extent_tree *et = F2FS_I(inode)->extent_tree;
711 : : unsigned int node_cnt = 0;
712 : :
713 : 0 : if (!et || !atomic_read(&et->node_cnt))
714 : : return 0;
715 : :
716 : 0 : write_lock(&et->lock);
717 : 0 : node_cnt = __free_extent_tree(sbi, et);
718 : : write_unlock(&et->lock);
719 : :
720 : 0 : return node_cnt;
721 : : }
722 : :
723 : 0 : void f2fs_drop_extent_tree(struct inode *inode)
724 : : {
725 : : struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
726 : 0 : struct extent_tree *et = F2FS_I(inode)->extent_tree;
727 : : bool updated = false;
728 : :
729 : 0 : if (!f2fs_may_extent_tree(inode))
730 : 0 : return;
731 : :
732 : 0 : set_inode_flag(inode, FI_NO_EXTENT);
733 : :
734 : 0 : write_lock(&et->lock);
735 : 0 : __free_extent_tree(sbi, et);
736 : 0 : if (et->largest.len) {
737 : 0 : et->largest.len = 0;
738 : : updated = true;
739 : : }
740 : : write_unlock(&et->lock);
741 : 0 : if (updated)
742 : 0 : f2fs_mark_inode_dirty_sync(inode, true);
743 : : }
744 : :
745 : 0 : void f2fs_destroy_extent_tree(struct inode *inode)
746 : : {
747 : : struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
748 : 0 : struct extent_tree *et = F2FS_I(inode)->extent_tree;
749 : : unsigned int node_cnt = 0;
750 : :
751 : 0 : if (!et)
752 : : return;
753 : :
754 : 0 : if (inode->i_nlink && !is_bad_inode(inode) &&
755 : 0 : atomic_read(&et->node_cnt)) {
756 : 0 : mutex_lock(&sbi->extent_tree_lock);
757 : 0 : list_add_tail(&et->list, &sbi->zombie_list);
758 : 0 : atomic_inc(&sbi->total_zombie_tree);
759 : 0 : mutex_unlock(&sbi->extent_tree_lock);
760 : 0 : return;
761 : : }
762 : :
763 : : /* free all extent info belong to this extent tree */
764 : 0 : node_cnt = f2fs_destroy_extent_node(inode);
765 : :
766 : : /* delete extent tree entry in radix tree */
767 : 0 : mutex_lock(&sbi->extent_tree_lock);
768 : 0 : f2fs_bug_on(sbi, atomic_read(&et->node_cnt));
769 : 0 : radix_tree_delete(&sbi->extent_tree_root, inode->i_ino);
770 : 0 : kmem_cache_free(extent_tree_slab, et);
771 : 0 : atomic_dec(&sbi->total_ext_tree);
772 : 0 : mutex_unlock(&sbi->extent_tree_lock);
773 : :
774 : 0 : F2FS_I(inode)->extent_tree = NULL;
775 : :
776 : 0 : trace_f2fs_destroy_extent_tree(inode, node_cnt);
777 : : }
778 : :
779 : 0 : bool f2fs_lookup_extent_cache(struct inode *inode, pgoff_t pgofs,
780 : : struct extent_info *ei)
781 : : {
782 : 0 : if (!f2fs_may_extent_tree(inode))
783 : : return false;
784 : :
785 : 0 : return f2fs_lookup_extent_tree(inode, pgofs, ei);
786 : : }
787 : :
788 : 0 : void f2fs_update_extent_cache(struct dnode_of_data *dn)
789 : : {
790 : : pgoff_t fofs;
791 : : block_t blkaddr;
792 : :
793 : 0 : if (!f2fs_may_extent_tree(dn->inode))
794 : 0 : return;
795 : :
796 : 0 : if (dn->data_blkaddr == NEW_ADDR)
797 : : blkaddr = NULL_ADDR;
798 : : else
799 : : blkaddr = dn->data_blkaddr;
800 : :
801 : 0 : fofs = f2fs_start_bidx_of_node(ofs_of_node(dn->node_page), dn->inode) +
802 : 0 : dn->ofs_in_node;
803 : 0 : f2fs_update_extent_tree_range(dn->inode, fofs, blkaddr, 1);
804 : : }
805 : :
806 : 0 : void f2fs_update_extent_cache_range(struct dnode_of_data *dn,
807 : : pgoff_t fofs, block_t blkaddr, unsigned int len)
808 : :
809 : : {
810 : 0 : if (!f2fs_may_extent_tree(dn->inode))
811 : 0 : return;
812 : :
813 : 0 : f2fs_update_extent_tree_range(dn->inode, fofs, blkaddr, len);
814 : : }
815 : :
816 : 0 : void f2fs_init_extent_cache_info(struct f2fs_sb_info *sbi)
817 : : {
818 : : INIT_RADIX_TREE(&sbi->extent_tree_root, GFP_NOIO);
819 : 0 : mutex_init(&sbi->extent_tree_lock);
820 : 0 : INIT_LIST_HEAD(&sbi->extent_list);
821 : 0 : spin_lock_init(&sbi->extent_lock);
822 : : atomic_set(&sbi->total_ext_tree, 0);
823 : 0 : INIT_LIST_HEAD(&sbi->zombie_list);
824 : : atomic_set(&sbi->total_zombie_tree, 0);
825 : : atomic_set(&sbi->total_ext_node, 0);
826 : 0 : }
827 : :
828 : 3 : int __init f2fs_create_extent_cache(void)
829 : : {
830 : 3 : extent_tree_slab = f2fs_kmem_cache_create("f2fs_extent_tree",
831 : : sizeof(struct extent_tree));
832 : 3 : if (!extent_tree_slab)
833 : : return -ENOMEM;
834 : 3 : extent_node_slab = f2fs_kmem_cache_create("f2fs_extent_node",
835 : : sizeof(struct extent_node));
836 : 3 : if (!extent_node_slab) {
837 : 0 : kmem_cache_destroy(extent_tree_slab);
838 : 0 : return -ENOMEM;
839 : : }
840 : : return 0;
841 : : }
842 : :
843 : 0 : void f2fs_destroy_extent_cache(void)
844 : : {
845 : 0 : kmem_cache_destroy(extent_node_slab);
846 : 0 : kmem_cache_destroy(extent_tree_slab);
847 : 0 : }
|
