| 1 | /* |
| 2 | * Copyright (C) 2007 Oracle. All rights reserved. |
| 3 | * |
| 4 | * This program is free software; you can redistribute it and/or |
| 5 | * modify it under the terms of the GNU General Public |
| 6 | * License v2 as published by the Free Software Foundation. |
| 7 | * |
| 8 | * This program is distributed in the hope that it will be useful, |
| 9 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 10 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 11 | * General Public License for more details. |
| 12 | * |
| 13 | * You should have received a copy of the GNU General Public |
| 14 | * License along with this program; if not, write to the |
| 15 | * Free Software Foundation, Inc., 59 Temple Place - Suite 330, |
| 16 | * Boston, MA 021110-1307, USA. |
| 17 | */ |
| 18 | |
| 19 | #include <linux/sched.h> |
| 20 | #include "ctree.h" |
| 21 | #include "disk-io.h" |
| 22 | #include "print-tree.h" |
| 23 | #include "transaction.h" |
| 24 | #include "locking.h" |
| 25 | |
| 26 | /* |
| 27 | * Defrag all the leaves in a given btree. |
| 28 | * Read all the leaves and try to get key order to |
| 29 | * better reflect disk order |
| 30 | */ |
| 31 | |
| 32 | int btrfs_defrag_leaves(struct btrfs_trans_handle *trans, |
| 33 | struct btrfs_root *root) |
| 34 | { |
| 35 | struct btrfs_path *path = NULL; |
| 36 | struct btrfs_key key; |
| 37 | int ret = 0; |
| 38 | int wret; |
| 39 | int level; |
| 40 | int next_key_ret = 0; |
| 41 | u64 last_ret = 0; |
| 42 | u64 min_trans = 0; |
| 43 | |
| 44 | if (root->fs_info->extent_root == root) { |
| 45 | /* |
| 46 | * there's recursion here right now in the tree locking, |
| 47 | * we can't defrag the extent root without deadlock |
| 48 | */ |
| 49 | goto out; |
| 50 | } |
| 51 | |
| 52 | if (!test_bit(BTRFS_ROOT_REF_COWS, &root->state)) |
| 53 | goto out; |
| 54 | |
| 55 | path = btrfs_alloc_path(); |
| 56 | if (!path) |
| 57 | return -ENOMEM; |
| 58 | |
| 59 | level = btrfs_header_level(root->node); |
| 60 | |
| 61 | if (level == 0) |
| 62 | goto out; |
| 63 | |
| 64 | if (root->defrag_progress.objectid == 0) { |
| 65 | struct extent_buffer *root_node; |
| 66 | u32 nritems; |
| 67 | |
| 68 | root_node = btrfs_lock_root_node(root); |
| 69 | btrfs_set_lock_blocking(root_node); |
| 70 | nritems = btrfs_header_nritems(root_node); |
| 71 | root->defrag_max.objectid = 0; |
| 72 | /* from above we know this is not a leaf */ |
| 73 | btrfs_node_key_to_cpu(root_node, &root->defrag_max, |
| 74 | nritems - 1); |
| 75 | btrfs_tree_unlock(root_node); |
| 76 | free_extent_buffer(root_node); |
| 77 | memset(&key, 0, sizeof(key)); |
| 78 | } else { |
| 79 | memcpy(&key, &root->defrag_progress, sizeof(key)); |
| 80 | } |
| 81 | |
| 82 | path->keep_locks = 1; |
| 83 | |
| 84 | ret = btrfs_search_forward(root, &key, path, min_trans); |
| 85 | if (ret < 0) |
| 86 | goto out; |
| 87 | if (ret > 0) { |
| 88 | ret = 0; |
| 89 | goto out; |
| 90 | } |
| 91 | btrfs_release_path(path); |
| 92 | /* |
| 93 | * We don't need a lock on a leaf. btrfs_realloc_node() will lock all |
| 94 | * leafs from path->nodes[1], so set lowest_level to 1 to avoid later |
| 95 | * a deadlock (attempting to write lock an already write locked leaf). |
| 96 | */ |
| 97 | path->lowest_level = 1; |
| 98 | wret = btrfs_search_slot(trans, root, &key, path, 0, 1); |
| 99 | |
| 100 | if (wret < 0) { |
| 101 | ret = wret; |
| 102 | goto out; |
| 103 | } |
| 104 | if (!path->nodes[1]) { |
| 105 | ret = 0; |
| 106 | goto out; |
| 107 | } |
| 108 | /* |
| 109 | * The node at level 1 must always be locked when our path has |
| 110 | * keep_locks set and lowest_level is 1, regardless of the value of |
| 111 | * path->slots[1]. |
| 112 | */ |
| 113 | BUG_ON(path->locks[1] == 0); |
| 114 | ret = btrfs_realloc_node(trans, root, |
| 115 | path->nodes[1], 0, |
| 116 | &last_ret, |
| 117 | &root->defrag_progress); |
| 118 | if (ret) { |
| 119 | WARN_ON(ret == -EAGAIN); |
| 120 | goto out; |
| 121 | } |
| 122 | /* |
| 123 | * Now that we reallocated the node we can find the next key. Note that |
| 124 | * btrfs_find_next_key() can release our path and do another search |
| 125 | * without COWing, this is because even with path->keep_locks = 1, |
| 126 | * btrfs_search_slot() / ctree.c:unlock_up() does not keeps a lock on a |
| 127 | * node when path->slots[node_level - 1] does not point to the last |
| 128 | * item or a slot beyond the last item (ctree.c:unlock_up()). Therefore |
| 129 | * we search for the next key after reallocating our node. |
| 130 | */ |
| 131 | path->slots[1] = btrfs_header_nritems(path->nodes[1]); |
| 132 | next_key_ret = btrfs_find_next_key(root, path, &key, 1, |
| 133 | min_trans); |
| 134 | if (next_key_ret == 0) { |
| 135 | memcpy(&root->defrag_progress, &key, sizeof(key)); |
| 136 | ret = -EAGAIN; |
| 137 | } |
| 138 | out: |
| 139 | btrfs_free_path(path); |
| 140 | if (ret == -EAGAIN) { |
| 141 | if (root->defrag_max.objectid > root->defrag_progress.objectid) |
| 142 | goto done; |
| 143 | if (root->defrag_max.type > root->defrag_progress.type) |
| 144 | goto done; |
| 145 | if (root->defrag_max.offset > root->defrag_progress.offset) |
| 146 | goto done; |
| 147 | ret = 0; |
| 148 | } |
| 149 | done: |
| 150 | if (ret != -EAGAIN) { |
| 151 | memset(&root->defrag_progress, 0, |
| 152 | sizeof(root->defrag_progress)); |
| 153 | root->defrag_trans_start = trans->transid; |
| 154 | } |
| 155 | return ret; |
| 156 | } |