blob: 997ac86f2a1d5526e9ac77969e668e6fc9b0bc87 [file] [log] [blame]
Chao Yua28ef1f2015-07-08 17:59:36 +08001/*
2 * f2fs extent cache support
3 *
4 * Copyright (c) 2015 Motorola Mobility
5 * Copyright (c) 2015 Samsung Electronics
6 * Authors: Jaegeuk Kim <jaegeuk@kernel.org>
7 * Chao Yu <chao2.yu@samsung.com>
8 *
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License version 2 as
11 * published by the Free Software Foundation.
12 */
13
14#include <linux/fs.h>
15#include <linux/f2fs_fs.h>
16
17#include "f2fs.h"
18#include "node.h"
19#include <trace/events/f2fs.h>
20
21static struct kmem_cache *extent_tree_slab;
22static struct kmem_cache *extent_node_slab;
23
24static struct extent_node *__attach_extent_node(struct f2fs_sb_info *sbi,
25 struct extent_tree *et, struct extent_info *ei,
26 struct rb_node *parent, struct rb_node **p)
27{
28 struct extent_node *en;
29
30 en = kmem_cache_alloc(extent_node_slab, GFP_ATOMIC);
31 if (!en)
32 return NULL;
33
34 en->ei = *ei;
35 INIT_LIST_HEAD(&en->list);
36
37 rb_link_node(&en->rb_node, parent, p);
38 rb_insert_color(&en->rb_node, &et->root);
39 et->count++;
40 atomic_inc(&sbi->total_ext_node);
41 return en;
42}
43
44static void __detach_extent_node(struct f2fs_sb_info *sbi,
45 struct extent_tree *et, struct extent_node *en)
46{
47 rb_erase(&en->rb_node, &et->root);
48 et->count--;
49 atomic_dec(&sbi->total_ext_node);
50
51 if (et->cached_en == en)
52 et->cached_en = NULL;
53}
54
55static struct extent_tree *__grab_extent_tree(struct inode *inode)
56{
57 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
58 struct extent_tree *et;
59 nid_t ino = inode->i_ino;
60
61 down_write(&sbi->extent_tree_lock);
62 et = radix_tree_lookup(&sbi->extent_tree_root, ino);
63 if (!et) {
64 et = f2fs_kmem_cache_alloc(extent_tree_slab, GFP_NOFS);
65 f2fs_radix_tree_insert(&sbi->extent_tree_root, ino, et);
66 memset(et, 0, sizeof(struct extent_tree));
67 et->ino = ino;
68 et->root = RB_ROOT;
69 et->cached_en = NULL;
70 rwlock_init(&et->lock);
71 atomic_set(&et->refcount, 0);
72 et->count = 0;
73 sbi->total_ext_tree++;
74 }
75 atomic_inc(&et->refcount);
76 up_write(&sbi->extent_tree_lock);
77
78 /* never died until evict_inode */
79 F2FS_I(inode)->extent_tree = et;
80
81 return et;
82}
83
Chao Yu91c481f2015-08-19 19:12:20 +080084static struct extent_node *__lookup_extent_tree(struct f2fs_sb_info *sbi,
85 struct extent_tree *et, unsigned int fofs)
Chao Yua28ef1f2015-07-08 17:59:36 +080086{
87 struct rb_node *node = et->root.rb_node;
Fan Lif8b703d2015-08-18 17:13:13 +080088 struct extent_node *en = et->cached_en;
Chao Yua28ef1f2015-07-08 17:59:36 +080089
Fan Lif8b703d2015-08-18 17:13:13 +080090 if (en) {
91 struct extent_info *cei = &en->ei;
Chao Yua28ef1f2015-07-08 17:59:36 +080092
Chao Yu91c481f2015-08-19 19:12:20 +080093 if (cei->fofs <= fofs && cei->fofs + cei->len > fofs) {
94 stat_inc_cached_node_hit(sbi);
Fan Lif8b703d2015-08-18 17:13:13 +080095 return en;
Chao Yu91c481f2015-08-19 19:12:20 +080096 }
Chao Yua28ef1f2015-07-08 17:59:36 +080097 }
98
99 while (node) {
100 en = rb_entry(node, struct extent_node, rb_node);
101
Chao Yu029e13c2015-08-19 19:13:25 +0800102 if (fofs < en->ei.fofs) {
Chao Yua28ef1f2015-07-08 17:59:36 +0800103 node = node->rb_left;
Chao Yu029e13c2015-08-19 19:13:25 +0800104 } else if (fofs >= en->ei.fofs + en->ei.len) {
Chao Yua28ef1f2015-07-08 17:59:36 +0800105 node = node->rb_right;
Chao Yu029e13c2015-08-19 19:13:25 +0800106 } else {
107 stat_inc_rbtree_node_hit(sbi);
Chao Yua28ef1f2015-07-08 17:59:36 +0800108 return en;
Chao Yu029e13c2015-08-19 19:13:25 +0800109 }
Chao Yua28ef1f2015-07-08 17:59:36 +0800110 }
111 return NULL;
112}
113
Chao Yua6f78342015-08-19 19:14:15 +0800114static struct extent_node *__init_extent_tree(struct f2fs_sb_info *sbi,
115 struct extent_tree *et, struct extent_info *ei)
Chao Yua28ef1f2015-07-08 17:59:36 +0800116{
117 struct rb_node **p = &et->root.rb_node;
Chao Yua28ef1f2015-07-08 17:59:36 +0800118 struct extent_node *en;
119
Chao Yua6f78342015-08-19 19:14:15 +0800120 en = __attach_extent_node(sbi, et, ei, NULL, p);
Chao Yua28ef1f2015-07-08 17:59:36 +0800121 if (!en)
122 return NULL;
Chao Yua6f78342015-08-19 19:14:15 +0800123
124 et->largest = en->ei;
Chao Yua28ef1f2015-07-08 17:59:36 +0800125 et->cached_en = en;
126 return en;
127}
128
129static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi,
130 struct extent_tree *et, bool free_all)
131{
132 struct rb_node *node, *next;
133 struct extent_node *en;
134 unsigned int count = et->count;
135
136 node = rb_first(&et->root);
137 while (node) {
138 next = rb_next(node);
139 en = rb_entry(node, struct extent_node, rb_node);
140
141 if (free_all) {
142 spin_lock(&sbi->extent_lock);
143 if (!list_empty(&en->list))
144 list_del_init(&en->list);
145 spin_unlock(&sbi->extent_lock);
146 }
147
148 if (free_all || list_empty(&en->list)) {
149 __detach_extent_node(sbi, et, en);
150 kmem_cache_free(extent_node_slab, en);
151 }
152 node = next;
153 }
154
155 return count - et->count;
156}
157
Chao Yu54d71852015-08-28 18:18:57 +0800158static void __drop_largest_extent(struct inode *inode, pgoff_t fofs)
Chao Yua28ef1f2015-07-08 17:59:36 +0800159{
160 struct extent_info *largest = &F2FS_I(inode)->extent_tree->largest;
161
162 if (largest->fofs <= fofs && largest->fofs + largest->len > fofs)
163 largest->len = 0;
164}
165
Chao Yu54d71852015-08-28 18:18:57 +0800166void f2fs_drop_largest_extent(struct inode *inode, pgoff_t fofs)
167{
168 if (!f2fs_may_extent_tree(inode))
169 return;
170
171 __drop_largest_extent(inode, fofs);
172}
173
Chao Yua28ef1f2015-07-08 17:59:36 +0800174void f2fs_init_extent_tree(struct inode *inode, struct f2fs_extent *i_ext)
175{
176 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
177 struct extent_tree *et;
178 struct extent_node *en;
179 struct extent_info ei;
180
181 if (!f2fs_may_extent_tree(inode))
182 return;
183
184 et = __grab_extent_tree(inode);
185
186 if (!i_ext || le32_to_cpu(i_ext->len) < F2FS_MIN_EXTENT_LEN)
187 return;
188
189 set_extent_info(&ei, le32_to_cpu(i_ext->fofs),
190 le32_to_cpu(i_ext->blk), le32_to_cpu(i_ext->len));
191
192 write_lock(&et->lock);
193 if (et->count)
194 goto out;
195
Chao Yua6f78342015-08-19 19:14:15 +0800196 en = __init_extent_tree(sbi, et, &ei);
Chao Yua28ef1f2015-07-08 17:59:36 +0800197 if (en) {
198 spin_lock(&sbi->extent_lock);
199 list_add_tail(&en->list, &sbi->extent_list);
200 spin_unlock(&sbi->extent_lock);
201 }
202out:
203 write_unlock(&et->lock);
204}
205
206static bool f2fs_lookup_extent_tree(struct inode *inode, pgoff_t pgofs,
207 struct extent_info *ei)
208{
209 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
210 struct extent_tree *et = F2FS_I(inode)->extent_tree;
211 struct extent_node *en;
212 bool ret = false;
213
214 f2fs_bug_on(sbi, !et);
215
216 trace_f2fs_lookup_extent_tree_start(inode, pgofs);
217
218 read_lock(&et->lock);
219
220 if (et->largest.fofs <= pgofs &&
221 et->largest.fofs + et->largest.len > pgofs) {
222 *ei = et->largest;
223 ret = true;
Chao Yu91c481f2015-08-19 19:12:20 +0800224 stat_inc_largest_node_hit(sbi);
Chao Yua28ef1f2015-07-08 17:59:36 +0800225 goto out;
226 }
227
Chao Yu91c481f2015-08-19 19:12:20 +0800228 en = __lookup_extent_tree(sbi, et, pgofs);
Chao Yua28ef1f2015-07-08 17:59:36 +0800229 if (en) {
230 *ei = en->ei;
231 spin_lock(&sbi->extent_lock);
232 if (!list_empty(&en->list))
233 list_move_tail(&en->list, &sbi->extent_list);
234 et->cached_en = en;
235 spin_unlock(&sbi->extent_lock);
236 ret = true;
Chao Yua28ef1f2015-07-08 17:59:36 +0800237 }
238out:
Chao Yu727edac2015-07-15 17:29:49 +0800239 stat_inc_total_hit(sbi);
Chao Yua28ef1f2015-07-08 17:59:36 +0800240 read_unlock(&et->lock);
241
242 trace_f2fs_lookup_extent_tree_end(inode, pgofs, ei);
243 return ret;
244}
245
Fan Li0f825ee2015-07-15 18:05:17 +0800246
247/*
248 * lookup extent at @fofs, if hit, return the extent
249 * if not, return NULL and
250 * @prev_ex: extent before fofs
251 * @next_ex: extent after fofs
252 * @insert_p: insert point for new extent at fofs
253 * in order to simpfy the insertion after.
254 * tree must stay unchanged between lookup and insertion.
255 */
256static struct extent_node *__lookup_extent_tree_ret(struct extent_tree *et,
Chao Yu91c481f2015-08-19 19:12:20 +0800257 unsigned int fofs,
258 struct extent_node **prev_ex,
Fan Li0f825ee2015-07-15 18:05:17 +0800259 struct extent_node **next_ex,
260 struct rb_node ***insert_p,
261 struct rb_node **insert_parent)
262{
263 struct rb_node **pnode = &et->root.rb_node;
264 struct rb_node *parent = NULL, *tmp_node;
Chao Yudac2dde2015-08-19 19:16:09 +0800265 struct extent_node *en = et->cached_en;
Fan Li0f825ee2015-07-15 18:05:17 +0800266
Chao Yudac2dde2015-08-19 19:16:09 +0800267 *insert_p = NULL;
268 *insert_parent = NULL;
269 *prev_ex = NULL;
270 *next_ex = NULL;
271
272 if (RB_EMPTY_ROOT(&et->root))
273 return NULL;
274
275 if (en) {
276 struct extent_info *cei = &en->ei;
Fan Li0f825ee2015-07-15 18:05:17 +0800277
278 if (cei->fofs <= fofs && cei->fofs + cei->len > fofs)
Chao Yudac2dde2015-08-19 19:16:09 +0800279 goto lookup_neighbors;
Fan Li0f825ee2015-07-15 18:05:17 +0800280 }
281
282 while (*pnode) {
283 parent = *pnode;
284 en = rb_entry(*pnode, struct extent_node, rb_node);
285
286 if (fofs < en->ei.fofs)
287 pnode = &(*pnode)->rb_left;
288 else if (fofs >= en->ei.fofs + en->ei.len)
289 pnode = &(*pnode)->rb_right;
290 else
Chao Yudac2dde2015-08-19 19:16:09 +0800291 goto lookup_neighbors;
Fan Li0f825ee2015-07-15 18:05:17 +0800292 }
293
294 *insert_p = pnode;
295 *insert_parent = parent;
296
297 en = rb_entry(parent, struct extent_node, rb_node);
298 tmp_node = parent;
299 if (parent && fofs > en->ei.fofs)
300 tmp_node = rb_next(parent);
301 *next_ex = tmp_node ?
302 rb_entry(tmp_node, struct extent_node, rb_node) : NULL;
303
304 tmp_node = parent;
305 if (parent && fofs < en->ei.fofs)
306 tmp_node = rb_prev(parent);
307 *prev_ex = tmp_node ?
308 rb_entry(tmp_node, struct extent_node, rb_node) : NULL;
Fan Li0f825ee2015-07-15 18:05:17 +0800309 return NULL;
Chao Yudac2dde2015-08-19 19:16:09 +0800310
311lookup_neighbors:
312 if (fofs == en->ei.fofs) {
313 /* lookup prev node for merging backward later */
314 tmp_node = rb_prev(&en->rb_node);
315 *prev_ex = tmp_node ?
316 rb_entry(tmp_node, struct extent_node, rb_node) : NULL;
317 }
318 if (fofs == en->ei.fofs + en->ei.len - 1) {
319 /* lookup next node for merging frontward later */
320 tmp_node = rb_next(&en->rb_node);
321 *next_ex = tmp_node ?
322 rb_entry(tmp_node, struct extent_node, rb_node) : NULL;
323 }
324 return en;
Fan Li0f825ee2015-07-15 18:05:17 +0800325}
326
Chao Yuef05e222015-08-19 19:15:09 +0800327static struct extent_node *__try_merge_extent_node(struct f2fs_sb_info *sbi,
Fan Li0f825ee2015-07-15 18:05:17 +0800328 struct extent_tree *et, struct extent_info *ei,
329 struct extent_node **den,
330 struct extent_node *prev_ex,
Chao Yuef05e222015-08-19 19:15:09 +0800331 struct extent_node *next_ex)
Fan Li0f825ee2015-07-15 18:05:17 +0800332{
Fan Li0f825ee2015-07-15 18:05:17 +0800333 struct extent_node *en = NULL;
Fan Li0f825ee2015-07-15 18:05:17 +0800334
335 if (prev_ex && __is_back_mergeable(ei, &prev_ex->ei)) {
Fan Li0f825ee2015-07-15 18:05:17 +0800336 prev_ex->ei.len += ei->len;
337 ei = &prev_ex->ei;
338 en = prev_ex;
339 }
Chao Yuef05e222015-08-19 19:15:09 +0800340
Fan Li0f825ee2015-07-15 18:05:17 +0800341 if (next_ex && __is_front_mergeable(ei, &next_ex->ei)) {
Chao Yuef05e222015-08-19 19:15:09 +0800342 if (en) {
Fan Li0f825ee2015-07-15 18:05:17 +0800343 __detach_extent_node(sbi, et, prev_ex);
344 *den = prev_ex;
345 }
346 next_ex->ei.fofs = ei->fofs;
347 next_ex->ei.blk = ei->blk;
348 next_ex->ei.len += ei->len;
349 en = next_ex;
350 }
Chao Yuef05e222015-08-19 19:15:09 +0800351
352 if (en) {
353 if (en->ei.len > et->largest.len)
354 et->largest = en->ei;
355 et->cached_en = en;
356 }
357 return en;
358}
359
360static struct extent_node *__insert_extent_tree(struct f2fs_sb_info *sbi,
361 struct extent_tree *et, struct extent_info *ei,
362 struct rb_node **insert_p,
363 struct rb_node *insert_parent)
364{
365 struct rb_node **p = &et->root.rb_node;
366 struct rb_node *parent = NULL;
367 struct extent_node *en = NULL;
Fan Li0f825ee2015-07-15 18:05:17 +0800368
369 if (insert_p && insert_parent) {
370 parent = insert_parent;
371 p = insert_p;
372 goto do_insert;
373 }
374
375 while (*p) {
376 parent = *p;
377 en = rb_entry(parent, struct extent_node, rb_node);
378
379 if (ei->fofs < en->ei.fofs)
380 p = &(*p)->rb_left;
381 else if (ei->fofs >= en->ei.fofs + en->ei.len)
382 p = &(*p)->rb_right;
383 else
384 f2fs_bug_on(sbi, 1);
385 }
386do_insert:
387 en = __attach_extent_node(sbi, et, ei, parent, p);
388 if (!en)
389 return NULL;
Chao Yuef05e222015-08-19 19:15:09 +0800390
Fan Li0f825ee2015-07-15 18:05:17 +0800391 if (en->ei.len > et->largest.len)
392 et->largest = en->ei;
393 et->cached_en = en;
394 return en;
395}
396
Chao Yu19b2c302015-08-26 20:34:48 +0800397unsigned int f2fs_update_extent_tree_range(struct inode *inode,
398 pgoff_t fofs, block_t blkaddr, unsigned int len)
Chao Yua28ef1f2015-07-08 17:59:36 +0800399{
400 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
401 struct extent_tree *et = F2FS_I(inode)->extent_tree;
402 struct extent_node *en = NULL, *en1 = NULL, *en2 = NULL, *en3 = NULL;
Chao Yu19b2c302015-08-26 20:34:48 +0800403 struct extent_node *prev_en = NULL, *next_en = NULL;
Chao Yua28ef1f2015-07-08 17:59:36 +0800404 struct extent_info ei, dei, prev;
Fan Li0f825ee2015-07-15 18:05:17 +0800405 struct rb_node **insert_p = NULL, *insert_parent = NULL;
Chao Yu19b2c302015-08-26 20:34:48 +0800406 unsigned int end = fofs + len;
407 unsigned int pos = (unsigned int)fofs;
Chao Yua28ef1f2015-07-08 17:59:36 +0800408
409 if (!et)
410 return false;
411
Chao Yua28ef1f2015-07-08 17:59:36 +0800412 write_lock(&et->lock);
413
414 if (is_inode_flag_set(F2FS_I(inode), FI_NO_EXTENT)) {
415 write_unlock(&et->lock);
416 return false;
417 }
418
419 prev = et->largest;
420 dei.len = 0;
421
422 /* we do not guarantee that the largest extent is cached all the time */
Chao Yu54d71852015-08-28 18:18:57 +0800423 __drop_largest_extent(inode, fofs);
Chao Yua28ef1f2015-07-08 17:59:36 +0800424
Chao Yu19b2c302015-08-26 20:34:48 +0800425 /* 1. lookup first extent node in range [fofs, fofs + len - 1] */
426 en = __lookup_extent_tree_ret(et, fofs, &prev_en, &next_en,
Fan Li0f825ee2015-07-15 18:05:17 +0800427 &insert_p, &insert_parent);
Chao Yu19b2c302015-08-26 20:34:48 +0800428 if (!en) {
429 if (next_en) {
430 en = next_en;
431 f2fs_bug_on(sbi, en->ei.fofs <= pos);
432 pos = en->ei.fofs;
433 } else {
434 /*
435 * skip searching in the tree since there is no
436 * larger extent node in the cache.
437 */
438 goto update_extent;
439 }
440 }
Chao Yua28ef1f2015-07-08 17:59:36 +0800441
Chao Yu19b2c302015-08-26 20:34:48 +0800442 /* 2. invlidate all extent nodes in range [fofs, fofs + len - 1] */
443 while (en) {
444 struct rb_node *node;
Chao Yua28ef1f2015-07-08 17:59:36 +0800445
Chao Yu19b2c302015-08-26 20:34:48 +0800446 if (pos >= end)
447 break;
448
449 dei = en->ei;
450 en1 = en2 = NULL;
451
452 node = rb_next(&en->rb_node);
453
454 /*
455 * 2.1 there are four cases when we invalidate blkaddr in extent
456 * node, |V: valid address, X: will be invalidated|
457 */
458 /* case#1, invalidate right part of extent node |VVVVVXXXXX| */
459 if (pos > dei.fofs && end >= dei.fofs + dei.len) {
460 en->ei.len = pos - dei.fofs;
461
462 if (en->ei.len < F2FS_MIN_EXTENT_LEN) {
463 __detach_extent_node(sbi, et, en);
464 insert_p = NULL;
465 insert_parent = NULL;
466 goto update;
467 }
468
469 if (__is_extent_same(&dei, &et->largest))
470 et->largest = en->ei;
471 goto next;
Chao Yua28ef1f2015-07-08 17:59:36 +0800472 }
473
Chao Yu19b2c302015-08-26 20:34:48 +0800474 /* case#2, invalidate left part of extent node |XXXXXVVVVV| */
475 if (pos <= dei.fofs && end < dei.fofs + dei.len) {
476 en->ei.fofs = end;
477 en->ei.blk += end - dei.fofs;
478 en->ei.len -= end - dei.fofs;
479
480 if (en->ei.len < F2FS_MIN_EXTENT_LEN) {
481 __detach_extent_node(sbi, et, en);
482 insert_p = NULL;
483 insert_parent = NULL;
484 goto update;
485 }
486
487 if (__is_extent_same(&dei, &et->largest))
488 et->largest = en->ei;
489 goto next;
Chao Yua28ef1f2015-07-08 17:59:36 +0800490 }
Chao Yu19b2c302015-08-26 20:34:48 +0800491
492 __detach_extent_node(sbi, et, en);
493
494 /*
495 * if we remove node in rb-tree, our parent node pointer may
496 * point the wrong place, discard them.
497 */
498 insert_p = NULL;
499 insert_parent = NULL;
500
501 /* case#3, invalidate entire extent node |XXXXXXXXXX| */
502 if (pos <= dei.fofs && end >= dei.fofs + dei.len) {
503 if (__is_extent_same(&dei, &et->largest))
504 et->largest.len = 0;
505 goto update;
506 }
507
508 /*
509 * case#4, invalidate data in the middle of extent node
510 * |VVVXXXXVVV|
511 */
512 if (dei.len > F2FS_MIN_EXTENT_LEN) {
513 unsigned int endofs;
514
515 /* insert left part of split extent into cache */
516 if (pos - dei.fofs >= F2FS_MIN_EXTENT_LEN) {
517 set_extent_info(&ei, dei.fofs, dei.blk,
518 pos - dei.fofs);
519 en1 = __insert_extent_tree(sbi, et, &ei,
520 NULL, NULL);
521 }
522
523 /* insert right part of split extent into cache */
524 endofs = dei.fofs + dei.len;
525 if (endofs - end >= F2FS_MIN_EXTENT_LEN) {
526 set_extent_info(&ei, end,
527 end - dei.fofs + dei.blk,
528 endofs - end);
529 en2 = __insert_extent_tree(sbi, et, &ei,
530 NULL, NULL);
531 }
532 }
533update:
534 /* 2.2 update in global extent list */
535 spin_lock(&sbi->extent_lock);
536 if (en && !list_empty(&en->list))
537 list_del(&en->list);
538 if (en1)
539 list_add_tail(&en1->list, &sbi->extent_list);
540 if (en2)
541 list_add_tail(&en2->list, &sbi->extent_list);
542 spin_unlock(&sbi->extent_lock);
543
544 /* 2.3 release extent node */
545 if (en)
546 kmem_cache_free(extent_node_slab, en);
547next:
548 en = node ? rb_entry(node, struct extent_node, rb_node) : NULL;
549 next_en = en;
550 if (en)
551 pos = en->ei.fofs;
Chao Yua28ef1f2015-07-08 17:59:36 +0800552 }
553
554update_extent:
555 /* 3. update extent in extent cache */
556 if (blkaddr) {
Chao Yu19b2c302015-08-26 20:34:48 +0800557 struct extent_node *den = NULL;
558
559 set_extent_info(&ei, fofs, blkaddr, len);
Chao Yuef05e222015-08-19 19:15:09 +0800560 en3 = __try_merge_extent_node(sbi, et, &ei, &den,
Chao Yu19b2c302015-08-26 20:34:48 +0800561 prev_en, next_en);
Chao Yuef05e222015-08-19 19:15:09 +0800562 if (!en3)
563 en3 = __insert_extent_tree(sbi, et, &ei,
564 insert_p, insert_parent);
Chao Yua28ef1f2015-07-08 17:59:36 +0800565
566 /* give up extent_cache, if split and small updates happen */
567 if (dei.len >= 1 &&
568 prev.len < F2FS_MIN_EXTENT_LEN &&
569 et->largest.len < F2FS_MIN_EXTENT_LEN) {
570 et->largest.len = 0;
571 set_inode_flag(F2FS_I(inode), FI_NO_EXTENT);
572 }
Chao Yua28ef1f2015-07-08 17:59:36 +0800573
Chao Yu19b2c302015-08-26 20:34:48 +0800574 spin_lock(&sbi->extent_lock);
575 if (en3) {
576 if (list_empty(&en3->list))
577 list_add_tail(&en3->list, &sbi->extent_list);
578 else
579 list_move_tail(&en3->list, &sbi->extent_list);
580 }
581 if (den && !list_empty(&den->list))
582 list_del(&den->list);
583 spin_unlock(&sbi->extent_lock);
Chao Yua28ef1f2015-07-08 17:59:36 +0800584
Chao Yu19b2c302015-08-26 20:34:48 +0800585 if (den)
586 kmem_cache_free(extent_node_slab, den);
587 }
Chao Yua28ef1f2015-07-08 17:59:36 +0800588
589 if (is_inode_flag_set(F2FS_I(inode), FI_NO_EXTENT))
590 __free_extent_tree(sbi, et, true);
591
592 write_unlock(&et->lock);
593
594 return !__is_extent_same(&prev, &et->largest);
595}
596
597unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink)
598{
599 struct extent_tree *treevec[EXT_TREE_VEC_SIZE];
600 struct extent_node *en, *tmp;
601 unsigned long ino = F2FS_ROOT_INO(sbi);
602 struct radix_tree_root *root = &sbi->extent_tree_root;
603 unsigned int found;
604 unsigned int node_cnt = 0, tree_cnt = 0;
605 int remained;
606
607 if (!test_opt(sbi, EXTENT_CACHE))
608 return 0;
609
610 if (!down_write_trylock(&sbi->extent_tree_lock))
611 goto out;
612
613 /* 1. remove unreferenced extent tree */
614 while ((found = radix_tree_gang_lookup(root,
615 (void **)treevec, ino, EXT_TREE_VEC_SIZE))) {
616 unsigned i;
617
618 ino = treevec[found - 1]->ino + 1;
619 for (i = 0; i < found; i++) {
620 struct extent_tree *et = treevec[i];
621
622 if (!atomic_read(&et->refcount)) {
623 write_lock(&et->lock);
624 node_cnt += __free_extent_tree(sbi, et, true);
625 write_unlock(&et->lock);
626
627 radix_tree_delete(root, et->ino);
628 kmem_cache_free(extent_tree_slab, et);
629 sbi->total_ext_tree--;
630 tree_cnt++;
631
632 if (node_cnt + tree_cnt >= nr_shrink)
633 goto unlock_out;
634 }
635 }
636 }
637 up_write(&sbi->extent_tree_lock);
638
639 /* 2. remove LRU extent entries */
640 if (!down_write_trylock(&sbi->extent_tree_lock))
641 goto out;
642
643 remained = nr_shrink - (node_cnt + tree_cnt);
644
645 spin_lock(&sbi->extent_lock);
646 list_for_each_entry_safe(en, tmp, &sbi->extent_list, list) {
647 if (!remained--)
648 break;
649 list_del_init(&en->list);
650 }
651 spin_unlock(&sbi->extent_lock);
652
653 while ((found = radix_tree_gang_lookup(root,
654 (void **)treevec, ino, EXT_TREE_VEC_SIZE))) {
655 unsigned i;
656
657 ino = treevec[found - 1]->ino + 1;
658 for (i = 0; i < found; i++) {
659 struct extent_tree *et = treevec[i];
660
661 write_lock(&et->lock);
662 node_cnt += __free_extent_tree(sbi, et, false);
663 write_unlock(&et->lock);
664
665 if (node_cnt + tree_cnt >= nr_shrink)
666 break;
667 }
668 }
669unlock_out:
670 up_write(&sbi->extent_tree_lock);
671out:
672 trace_f2fs_shrink_extent_tree(sbi, node_cnt, tree_cnt);
673
674 return node_cnt + tree_cnt;
675}
676
677unsigned int f2fs_destroy_extent_node(struct inode *inode)
678{
679 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
680 struct extent_tree *et = F2FS_I(inode)->extent_tree;
681 unsigned int node_cnt = 0;
682
683 if (!et)
684 return 0;
685
686 write_lock(&et->lock);
687 node_cnt = __free_extent_tree(sbi, et, true);
688 write_unlock(&et->lock);
689
690 return node_cnt;
691}
692
693void f2fs_destroy_extent_tree(struct inode *inode)
694{
695 struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
696 struct extent_tree *et = F2FS_I(inode)->extent_tree;
697 unsigned int node_cnt = 0;
698
699 if (!et)
700 return;
701
702 if (inode->i_nlink && !is_bad_inode(inode) && et->count) {
703 atomic_dec(&et->refcount);
704 return;
705 }
706
707 /* free all extent info belong to this extent tree */
708 node_cnt = f2fs_destroy_extent_node(inode);
709
710 /* delete extent tree entry in radix tree */
711 down_write(&sbi->extent_tree_lock);
712 atomic_dec(&et->refcount);
713 f2fs_bug_on(sbi, atomic_read(&et->refcount) || et->count);
714 radix_tree_delete(&sbi->extent_tree_root, inode->i_ino);
715 kmem_cache_free(extent_tree_slab, et);
716 sbi->total_ext_tree--;
717 up_write(&sbi->extent_tree_lock);
718
719 F2FS_I(inode)->extent_tree = NULL;
720
721 trace_f2fs_destroy_extent_tree(inode, node_cnt);
722}
723
724bool f2fs_lookup_extent_cache(struct inode *inode, pgoff_t pgofs,
725 struct extent_info *ei)
726{
727 if (!f2fs_may_extent_tree(inode))
728 return false;
729
730 return f2fs_lookup_extent_tree(inode, pgofs, ei);
731}
732
733void f2fs_update_extent_cache(struct dnode_of_data *dn)
734{
735 struct f2fs_inode_info *fi = F2FS_I(dn->inode);
736 pgoff_t fofs;
737
738 if (!f2fs_may_extent_tree(dn->inode))
739 return;
740
741 f2fs_bug_on(F2FS_I_SB(dn->inode), dn->data_blkaddr == NEW_ADDR);
742
Chao Yu19b2c302015-08-26 20:34:48 +0800743
Chao Yua28ef1f2015-07-08 17:59:36 +0800744 fofs = start_bidx_of_node(ofs_of_node(dn->node_page), fi) +
745 dn->ofs_in_node;
746
Chao Yu19b2c302015-08-26 20:34:48 +0800747 if (f2fs_update_extent_tree_range(dn->inode, fofs, dn->data_blkaddr, 1))
748 sync_inode_page(dn);
749}
750
751void f2fs_update_extent_cache_range(struct dnode_of_data *dn,
752 pgoff_t fofs, block_t blkaddr, unsigned int len)
753
754{
755 if (!f2fs_may_extent_tree(dn->inode))
756 return;
757
758 if (f2fs_update_extent_tree_range(dn->inode, fofs, blkaddr, len))
Chao Yua28ef1f2015-07-08 17:59:36 +0800759 sync_inode_page(dn);
760}
761
762void init_extent_cache_info(struct f2fs_sb_info *sbi)
763{
764 INIT_RADIX_TREE(&sbi->extent_tree_root, GFP_NOIO);
765 init_rwsem(&sbi->extent_tree_lock);
766 INIT_LIST_HEAD(&sbi->extent_list);
767 spin_lock_init(&sbi->extent_lock);
768 sbi->total_ext_tree = 0;
769 atomic_set(&sbi->total_ext_node, 0);
770}
771
772int __init create_extent_cache(void)
773{
774 extent_tree_slab = f2fs_kmem_cache_create("f2fs_extent_tree",
775 sizeof(struct extent_tree));
776 if (!extent_tree_slab)
777 return -ENOMEM;
778 extent_node_slab = f2fs_kmem_cache_create("f2fs_extent_node",
779 sizeof(struct extent_node));
780 if (!extent_node_slab) {
781 kmem_cache_destroy(extent_tree_slab);
782 return -ENOMEM;
783 }
784 return 0;
785}
786
787void destroy_extent_cache(void)
788{
789 kmem_cache_destroy(extent_node_slab);
790 kmem_cache_destroy(extent_tree_slab);
791}