1 // SPDX-License-Identifier: GPL-2.0
2 /*
3 * Copyright (C) 2007 Oracle. All rights reserved.
4 */
5
6 #include <linux/sched.h>
7 #include "ctree.h"
8 #include "disk-io.h"
9 #include "print-tree.h"
10 #include "transaction.h"
11 #include "locking.h"
12
13 static struct kmem_cache *btrfs_inode_defrag_cachep;
14
15 /*
16 * When auto defrag is enabled we queue up these defrag structs to remember
17 * which inodes need defragging passes.
18 */
19 struct inode_defrag {
20 struct rb_node rb_node;
21 /* Inode number */
22 u64 ino;
23 /*
24 * Transid where the defrag was added, we search for extents newer than
25 * this.
26 */
27 u64 transid;
28
29 /* Root objectid */
30 u64 root;
31
32 /*
33 * The extent size threshold for autodefrag.
34 *
35 * This value is different for compressed/non-compressed extents, thus
36 * needs to be passed from higher layer.
37 * (aka, inode_should_defrag())
38 */
39 u32 extent_thresh;
40 };
41
__compare_inode_defrag(struct inode_defrag * defrag1,struct inode_defrag * defrag2)42 static int __compare_inode_defrag(struct inode_defrag *defrag1,
43 struct inode_defrag *defrag2)
44 {
45 if (defrag1->root > defrag2->root)
46 return 1;
47 else if (defrag1->root < defrag2->root)
48 return -1;
49 else if (defrag1->ino > defrag2->ino)
50 return 1;
51 else if (defrag1->ino < defrag2->ino)
52 return -1;
53 else
54 return 0;
55 }
56
57 /*
58 * Pop a record for an inode into the defrag tree. The lock must be held
59 * already.
60 *
61 * If you're inserting a record for an older transid than an existing record,
62 * the transid already in the tree is lowered.
63 *
64 * If an existing record is found the defrag item you pass in is freed.
65 */
__btrfs_add_inode_defrag(struct btrfs_inode * inode,struct inode_defrag * defrag)66 static int __btrfs_add_inode_defrag(struct btrfs_inode *inode,
67 struct inode_defrag *defrag)
68 {
69 struct btrfs_fs_info *fs_info = inode->root->fs_info;
70 struct inode_defrag *entry;
71 struct rb_node **p;
72 struct rb_node *parent = NULL;
73 int ret;
74
75 p = &fs_info->defrag_inodes.rb_node;
76 while (*p) {
77 parent = *p;
78 entry = rb_entry(parent, struct inode_defrag, rb_node);
79
80 ret = __compare_inode_defrag(defrag, entry);
81 if (ret < 0)
82 p = &parent->rb_left;
83 else if (ret > 0)
84 p = &parent->rb_right;
85 else {
86 /*
87 * If we're reinserting an entry for an old defrag run,
88 * make sure to lower the transid of our existing
89 * record.
90 */
91 if (defrag->transid < entry->transid)
92 entry->transid = defrag->transid;
93 entry->extent_thresh = min(defrag->extent_thresh,
94 entry->extent_thresh);
95 return -EEXIST;
96 }
97 }
98 set_bit(BTRFS_INODE_IN_DEFRAG, &inode->runtime_flags);
99 rb_link_node(&defrag->rb_node, parent, p);
100 rb_insert_color(&defrag->rb_node, &fs_info->defrag_inodes);
101 return 0;
102 }
103
__need_auto_defrag(struct btrfs_fs_info * fs_info)104 static inline int __need_auto_defrag(struct btrfs_fs_info *fs_info)
105 {
106 if (!btrfs_test_opt(fs_info, AUTO_DEFRAG))
107 return 0;
108
109 if (btrfs_fs_closing(fs_info))
110 return 0;
111
112 return 1;
113 }
114
115 /*
116 * Insert a defrag record for this inode if auto defrag is enabled.
117 */
btrfs_add_inode_defrag(struct btrfs_trans_handle * trans,struct btrfs_inode * inode,u32 extent_thresh)118 int btrfs_add_inode_defrag(struct btrfs_trans_handle *trans,
119 struct btrfs_inode *inode, u32 extent_thresh)
120 {
121 struct btrfs_root *root = inode->root;
122 struct btrfs_fs_info *fs_info = root->fs_info;
123 struct inode_defrag *defrag;
124 u64 transid;
125 int ret;
126
127 if (!__need_auto_defrag(fs_info))
128 return 0;
129
130 if (test_bit(BTRFS_INODE_IN_DEFRAG, &inode->runtime_flags))
131 return 0;
132
133 if (trans)
134 transid = trans->transid;
135 else
136 transid = inode->root->last_trans;
137
138 defrag = kmem_cache_zalloc(btrfs_inode_defrag_cachep, GFP_NOFS);
139 if (!defrag)
140 return -ENOMEM;
141
142 defrag->ino = btrfs_ino(inode);
143 defrag->transid = transid;
144 defrag->root = root->root_key.objectid;
145 defrag->extent_thresh = extent_thresh;
146
147 spin_lock(&fs_info->defrag_inodes_lock);
148 if (!test_bit(BTRFS_INODE_IN_DEFRAG, &inode->runtime_flags)) {
149 /*
150 * If we set IN_DEFRAG flag and evict the inode from memory,
151 * and then re-read this inode, this new inode doesn't have
152 * IN_DEFRAG flag. At the case, we may find the existed defrag.
153 */
154 ret = __btrfs_add_inode_defrag(inode, defrag);
155 if (ret)
156 kmem_cache_free(btrfs_inode_defrag_cachep, defrag);
157 } else {
158 kmem_cache_free(btrfs_inode_defrag_cachep, defrag);
159 }
160 spin_unlock(&fs_info->defrag_inodes_lock);
161 return 0;
162 }
163
164 /*
165 * Pick the defragable inode that we want, if it doesn't exist, we will get the
166 * next one.
167 */
btrfs_pick_defrag_inode(struct btrfs_fs_info * fs_info,u64 root,u64 ino)168 static struct inode_defrag *btrfs_pick_defrag_inode(
169 struct btrfs_fs_info *fs_info, u64 root, u64 ino)
170 {
171 struct inode_defrag *entry = NULL;
172 struct inode_defrag tmp;
173 struct rb_node *p;
174 struct rb_node *parent = NULL;
175 int ret;
176
177 tmp.ino = ino;
178 tmp.root = root;
179
180 spin_lock(&fs_info->defrag_inodes_lock);
181 p = fs_info->defrag_inodes.rb_node;
182 while (p) {
183 parent = p;
184 entry = rb_entry(parent, struct inode_defrag, rb_node);
185
186 ret = __compare_inode_defrag(&tmp, entry);
187 if (ret < 0)
188 p = parent->rb_left;
189 else if (ret > 0)
190 p = parent->rb_right;
191 else
192 goto out;
193 }
194
195 if (parent && __compare_inode_defrag(&tmp, entry) > 0) {
196 parent = rb_next(parent);
197 if (parent)
198 entry = rb_entry(parent, struct inode_defrag, rb_node);
199 else
200 entry = NULL;
201 }
202 out:
203 if (entry)
204 rb_erase(parent, &fs_info->defrag_inodes);
205 spin_unlock(&fs_info->defrag_inodes_lock);
206 return entry;
207 }
208
btrfs_cleanup_defrag_inodes(struct btrfs_fs_info * fs_info)209 void btrfs_cleanup_defrag_inodes(struct btrfs_fs_info *fs_info)
210 {
211 struct inode_defrag *defrag;
212 struct rb_node *node;
213
214 spin_lock(&fs_info->defrag_inodes_lock);
215 node = rb_first(&fs_info->defrag_inodes);
216 while (node) {
217 rb_erase(node, &fs_info->defrag_inodes);
218 defrag = rb_entry(node, struct inode_defrag, rb_node);
219 kmem_cache_free(btrfs_inode_defrag_cachep, defrag);
220
221 cond_resched_lock(&fs_info->defrag_inodes_lock);
222
223 node = rb_first(&fs_info->defrag_inodes);
224 }
225 spin_unlock(&fs_info->defrag_inodes_lock);
226 }
227
228 #define BTRFS_DEFRAG_BATCH 1024
229
__btrfs_run_defrag_inode(struct btrfs_fs_info * fs_info,struct inode_defrag * defrag)230 static int __btrfs_run_defrag_inode(struct btrfs_fs_info *fs_info,
231 struct inode_defrag *defrag)
232 {
233 struct btrfs_root *inode_root;
234 struct inode *inode;
235 struct btrfs_ioctl_defrag_range_args range;
236 int ret = 0;
237 u64 cur = 0;
238
239 again:
240 if (test_bit(BTRFS_FS_STATE_REMOUNTING, &fs_info->fs_state))
241 goto cleanup;
242 if (!__need_auto_defrag(fs_info))
243 goto cleanup;
244
245 /* Get the inode */
246 inode_root = btrfs_get_fs_root(fs_info, defrag->root, true);
247 if (IS_ERR(inode_root)) {
248 ret = PTR_ERR(inode_root);
249 goto cleanup;
250 }
251
252 inode = btrfs_iget(fs_info->sb, defrag->ino, inode_root);
253 btrfs_put_root(inode_root);
254 if (IS_ERR(inode)) {
255 ret = PTR_ERR(inode);
256 goto cleanup;
257 }
258
259 if (cur >= i_size_read(inode)) {
260 iput(inode);
261 goto cleanup;
262 }
263
264 /* Do a chunk of defrag */
265 clear_bit(BTRFS_INODE_IN_DEFRAG, &BTRFS_I(inode)->runtime_flags);
266 memset(&range, 0, sizeof(range));
267 range.len = (u64)-1;
268 range.start = cur;
269 range.extent_thresh = defrag->extent_thresh;
270
271 sb_start_write(fs_info->sb);
272 ret = btrfs_defrag_file(inode, NULL, &range, defrag->transid,
273 BTRFS_DEFRAG_BATCH);
274 sb_end_write(fs_info->sb);
275 iput(inode);
276
277 if (ret < 0)
278 goto cleanup;
279
280 cur = max(cur + fs_info->sectorsize, range.start);
281 goto again;
282
283 cleanup:
284 kmem_cache_free(btrfs_inode_defrag_cachep, defrag);
285 return ret;
286 }
287
288 /*
289 * Run through the list of inodes in the FS that need defragging.
290 */
btrfs_run_defrag_inodes(struct btrfs_fs_info * fs_info)291 int btrfs_run_defrag_inodes(struct btrfs_fs_info *fs_info)
292 {
293 struct inode_defrag *defrag;
294 u64 first_ino = 0;
295 u64 root_objectid = 0;
296
297 atomic_inc(&fs_info->defrag_running);
298 while (1) {
299 /* Pause the auto defragger. */
300 if (test_bit(BTRFS_FS_STATE_REMOUNTING, &fs_info->fs_state))
301 break;
302
303 if (!__need_auto_defrag(fs_info))
304 break;
305
306 /* find an inode to defrag */
307 defrag = btrfs_pick_defrag_inode(fs_info, root_objectid, first_ino);
308 if (!defrag) {
309 if (root_objectid || first_ino) {
310 root_objectid = 0;
311 first_ino = 0;
312 continue;
313 } else {
314 break;
315 }
316 }
317
318 first_ino = defrag->ino + 1;
319 root_objectid = defrag->root;
320
321 __btrfs_run_defrag_inode(fs_info, defrag);
322 }
323 atomic_dec(&fs_info->defrag_running);
324
325 /*
326 * During unmount, we use the transaction_wait queue to wait for the
327 * defragger to stop.
328 */
329 wake_up(&fs_info->transaction_wait);
330 return 0;
331 }
332
333 /*
334 * Defrag all the leaves in a given btree.
335 * Read all the leaves and try to get key order to
336 * better reflect disk order
337 */
338
btrfs_defrag_leaves(struct btrfs_trans_handle * trans,struct btrfs_root * root)339 int btrfs_defrag_leaves(struct btrfs_trans_handle *trans,
340 struct btrfs_root *root)
341 {
342 struct btrfs_path *path = NULL;
343 struct btrfs_key key;
344 int ret = 0;
345 int wret;
346 int level;
347 int next_key_ret = 0;
348 u64 last_ret = 0;
349
350 if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state))
351 goto out;
352
353 path = btrfs_alloc_path();
354 if (!path) {
355 ret = -ENOMEM;
356 goto out;
357 }
358
359 level = btrfs_header_level(root->node);
360
361 if (level == 0)
362 goto out;
363
364 if (root->defrag_progress.objectid == 0) {
365 struct extent_buffer *root_node;
366 u32 nritems;
367
368 root_node = btrfs_lock_root_node(root);
369 nritems = btrfs_header_nritems(root_node);
370 root->defrag_max.objectid = 0;
371 /* from above we know this is not a leaf */
372 btrfs_node_key_to_cpu(root_node, &root->defrag_max,
373 nritems - 1);
374 btrfs_tree_unlock(root_node);
375 free_extent_buffer(root_node);
376 memset(&key, 0, sizeof(key));
377 } else {
378 memcpy(&key, &root->defrag_progress, sizeof(key));
379 }
380
381 path->keep_locks = 1;
382
383 ret = btrfs_search_forward(root, &key, path, BTRFS_OLDEST_GENERATION);
384 if (ret < 0)
385 goto out;
386 if (ret > 0) {
387 ret = 0;
388 goto out;
389 }
390 btrfs_release_path(path);
391 /*
392 * We don't need a lock on a leaf. btrfs_realloc_node() will lock all
393 * leafs from path->nodes[1], so set lowest_level to 1 to avoid later
394 * a deadlock (attempting to write lock an already write locked leaf).
395 */
396 path->lowest_level = 1;
397 wret = btrfs_search_slot(trans, root, &key, path, 0, 1);
398
399 if (wret < 0) {
400 ret = wret;
401 goto out;
402 }
403 if (!path->nodes[1]) {
404 ret = 0;
405 goto out;
406 }
407 /*
408 * The node at level 1 must always be locked when our path has
409 * keep_locks set and lowest_level is 1, regardless of the value of
410 * path->slots[1].
411 */
412 BUG_ON(path->locks[1] == 0);
413 ret = btrfs_realloc_node(trans, root,
414 path->nodes[1], 0,
415 &last_ret,
416 &root->defrag_progress);
417 if (ret) {
418 WARN_ON(ret == -EAGAIN);
419 goto out;
420 }
421 /*
422 * Now that we reallocated the node we can find the next key. Note that
423 * btrfs_find_next_key() can release our path and do another search
424 * without COWing, this is because even with path->keep_locks = 1,
425 * btrfs_search_slot() / ctree.c:unlock_up() does not keeps a lock on a
426 * node when path->slots[node_level - 1] does not point to the last
427 * item or a slot beyond the last item (ctree.c:unlock_up()). Therefore
428 * we search for the next key after reallocating our node.
429 */
430 path->slots[1] = btrfs_header_nritems(path->nodes[1]);
431 next_key_ret = btrfs_find_next_key(root, path, &key, 1,
432 BTRFS_OLDEST_GENERATION);
433 if (next_key_ret == 0) {
434 memcpy(&root->defrag_progress, &key, sizeof(key));
435 ret = -EAGAIN;
436 }
437 out:
438 btrfs_free_path(path);
439 if (ret == -EAGAIN) {
440 if (root->defrag_max.objectid > root->defrag_progress.objectid)
441 goto done;
442 if (root->defrag_max.type > root->defrag_progress.type)
443 goto done;
444 if (root->defrag_max.offset > root->defrag_progress.offset)
445 goto done;
446 ret = 0;
447 }
448 done:
449 if (ret != -EAGAIN)
450 memset(&root->defrag_progress, 0,
451 sizeof(root->defrag_progress));
452
453 return ret;
454 }
455
btrfs_auto_defrag_exit(void)456 void __cold btrfs_auto_defrag_exit(void)
457 {
458 kmem_cache_destroy(btrfs_inode_defrag_cachep);
459 }
460
btrfs_auto_defrag_init(void)461 int __init btrfs_auto_defrag_init(void)
462 {
463 btrfs_inode_defrag_cachep = kmem_cache_create("btrfs_inode_defrag",
464 sizeof(struct inode_defrag), 0,
465 SLAB_MEM_SPREAD,
466 NULL);
467 if (!btrfs_inode_defrag_cachep)
468 return -ENOMEM;
469
470 return 0;
471 }
472