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 #include "accessors.h" 13 14 /* 15 * Defrag all the leaves in a given btree. 16 * Read all the leaves and try to get key order to 17 * better reflect disk order 18 */ 19 20 int btrfs_defrag_leaves(struct btrfs_trans_handle *trans, 21 struct btrfs_root *root) 22 { 23 struct btrfs_path *path = NULL; 24 struct btrfs_key key; 25 int ret = 0; 26 int wret; 27 int level; 28 int next_key_ret = 0; 29 u64 last_ret = 0; 30 31 if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) 32 goto out; 33 34 path = btrfs_alloc_path(); 35 if (!path) 36 return -ENOMEM; 37 38 level = btrfs_header_level(root->node); 39 40 if (level == 0) 41 goto out; 42 43 if (root->defrag_progress.objectid == 0) { 44 struct extent_buffer *root_node; 45 u32 nritems; 46 47 root_node = btrfs_lock_root_node(root); 48 nritems = btrfs_header_nritems(root_node); 49 root->defrag_max.objectid = 0; 50 /* from above we know this is not a leaf */ 51 btrfs_node_key_to_cpu(root_node, &root->defrag_max, 52 nritems - 1); 53 btrfs_tree_unlock(root_node); 54 free_extent_buffer(root_node); 55 memset(&key, 0, sizeof(key)); 56 } else { 57 memcpy(&key, &root->defrag_progress, sizeof(key)); 58 } 59 60 path->keep_locks = 1; 61 62 ret = btrfs_search_forward(root, &key, path, BTRFS_OLDEST_GENERATION); 63 if (ret < 0) 64 goto out; 65 if (ret > 0) { 66 ret = 0; 67 goto out; 68 } 69 btrfs_release_path(path); 70 /* 71 * We don't need a lock on a leaf. btrfs_realloc_node() will lock all 72 * leafs from path->nodes[1], so set lowest_level to 1 to avoid later 73 * a deadlock (attempting to write lock an already write locked leaf). 74 */ 75 path->lowest_level = 1; 76 wret = btrfs_search_slot(trans, root, &key, path, 0, 1); 77 78 if (wret < 0) { 79 ret = wret; 80 goto out; 81 } 82 if (!path->nodes[1]) { 83 ret = 0; 84 goto out; 85 } 86 /* 87 * The node at level 1 must always be locked when our path has 88 * keep_locks set and lowest_level is 1, regardless of the value of 89 * path->slots[1]. 90 */ 91 BUG_ON(path->locks[1] == 0); 92 ret = btrfs_realloc_node(trans, root, 93 path->nodes[1], 0, 94 &last_ret, 95 &root->defrag_progress); 96 if (ret) { 97 WARN_ON(ret == -EAGAIN); 98 goto out; 99 } 100 /* 101 * Now that we reallocated the node we can find the next key. Note that 102 * btrfs_find_next_key() can release our path and do another search 103 * without COWing, this is because even with path->keep_locks = 1, 104 * btrfs_search_slot() / ctree.c:unlock_up() does not keeps a lock on a 105 * node when path->slots[node_level - 1] does not point to the last 106 * item or a slot beyond the last item (ctree.c:unlock_up()). Therefore 107 * we search for the next key after reallocating our node. 108 */ 109 path->slots[1] = btrfs_header_nritems(path->nodes[1]); 110 next_key_ret = btrfs_find_next_key(root, path, &key, 1, 111 BTRFS_OLDEST_GENERATION); 112 if (next_key_ret == 0) { 113 memcpy(&root->defrag_progress, &key, sizeof(key)); 114 ret = -EAGAIN; 115 } 116 out: 117 btrfs_free_path(path); 118 if (ret == -EAGAIN) { 119 if (root->defrag_max.objectid > root->defrag_progress.objectid) 120 goto done; 121 if (root->defrag_max.type > root->defrag_progress.type) 122 goto done; 123 if (root->defrag_max.offset > root->defrag_progress.offset) 124 goto done; 125 ret = 0; 126 } 127 done: 128 if (ret != -EAGAIN) 129 memset(&root->defrag_progress, 0, 130 sizeof(root->defrag_progress)); 131 132 return ret; 133 } 134