fs/btrfs/tree-defrag.c

   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
  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  */
  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
 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  */
 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  */
 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
 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
 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  */
 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
 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
 456 void __cold btrfs_auto_defrag_exit(void)
 457 {
 458         kmem_cache_destroy(btrfs_inode_defrag_cachep);
 459 }
 460
 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 }