fs/btrfs/tree-defrag.c

   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
  25 static void reada_defrag(struct btrfs_root *root,
  26                          struct extent_buffer *node)
  27 {
  28         int i;
  29         u32 nritems;
  30         u64 bytenr;
  31         u64 gen;
  32         u32 blocksize;
  33         int ret;
  34
  35         blocksize = btrfs_level_size(root, btrfs_header_level(node) - 1);
  36         nritems = btrfs_header_nritems(node);
  37         for (i = 0; i < nritems; i++) {
  38                 bytenr = btrfs_node_blockptr(node, i);
  39                 gen = btrfs_node_ptr_generation(node, i);
  40                 ret = readahead_tree_block(root, bytenr, blocksize, gen);
  41                 if (ret)
  42                         break;
  43         }
  44 }
  45
  46 static int defrag_walk_down(struct btrfs_trans_handle *trans,
  47                             struct btrfs_root *root,
  48                             struct btrfs_path *path, int *level,
  49                             int cache_only, u64 *last_ret)
  50 {
  51         struct extent_buffer *next;
  52         struct extent_buffer *cur;
  53         u64 bytenr;
  54         u64 ptr_gen;
  55         int ret = 0;
  56         int is_extent = 0;
  57
  58         WARN_ON(*level < 0);
  59         WARN_ON(*level >= BTRFS_MAX_LEVEL);
  60
  61         if (root->fs_info->extent_root == root)
  62                 is_extent = 1;
  63
  64         if (*level == 1 && cache_only && path->nodes[1] &&
  65             !btrfs_buffer_defrag(path->nodes[1])) {
  66                 goto out;
  67         }
  68         while(*level > 0) {
  69                 WARN_ON(*level < 0);
  70                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
  71                 cur = path->nodes[*level];
  72
  73                 if (!cache_only && *level > 1 && path->slots[*level] == 0)
  74                         reada_defrag(root, cur);
  75
  76                 if (btrfs_header_level(cur) != *level)
  77                         WARN_ON(1);
  78
  79                 if (path->slots[*level] >=
  80                     btrfs_header_nritems(cur))
  81                         break;
  82
  83                 if (*level == 1) {
  84                         WARN_ON(btrfs_header_generation(path->nodes[*level]) !=
  85                                                         trans->transid);
  86                         ret = btrfs_realloc_node(trans, root,
  87                                                  path->nodes[*level],
  88                                                  path->slots[*level],
  89                                                  cache_only, last_ret,
  90                                                  &root->defrag_progress);
  91                         if (is_extent)
  92                                 btrfs_extent_post_op(trans, root);
  93
  94                         break;
  95                 }
  96                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
  97                 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
  98
  99                 if (cache_only) {
 100                         next = btrfs_find_tree_block(root, bytenr,
 101                                            btrfs_level_size(root, *level - 1));
 102                         if (!next || !btrfs_buffer_uptodate(next, ptr_gen) ||
 103                             !btrfs_buffer_defrag(next)) {
 104                                 free_extent_buffer(next);
 105                                 path->slots[*level]++;
 106                                 continue;
 107                         }
 108                 } else {
 109                         next = read_tree_block(root, bytenr,
 110                                        btrfs_level_size(root, *level - 1),
 111                                        ptr_gen);
 112                 }
 113                 ret = btrfs_cow_block(trans, root, next, path->nodes[*level],
 114                                       path->slots[*level], &next);
 115                 BUG_ON(ret);
 116                 if (is_extent)
 117                         btrfs_extent_post_op(trans, root);
 118
 119                 WARN_ON(*level <= 0);
 120                 if (path->nodes[*level-1])
 121                         free_extent_buffer(path->nodes[*level-1]);
 122                 path->nodes[*level-1] = next;
 123                 *level = btrfs_header_level(next);
 124                 path->slots[*level] = 0;
 125         }
 126         WARN_ON(*level < 0);
 127         WARN_ON(*level >= BTRFS_MAX_LEVEL);
 128
 129         btrfs_clear_buffer_defrag(path->nodes[*level]);
 130 out:
 131         free_extent_buffer(path->nodes[*level]);
 132         path->nodes[*level] = NULL;
 133         *level += 1;
 134         WARN_ON(ret && ret != -EAGAIN);
 135         return ret;
 136 }
 137
 138 static int defrag_walk_up(struct btrfs_trans_handle *trans,
 139                           struct btrfs_root *root,
 140                           struct btrfs_path *path, int *level,
 141                           int cache_only)
 142 {
 143         int i;
 144         int slot;
 145         struct extent_buffer *node;
 146
 147         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
 148                 slot = path->slots[i];
 149                 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
 150                         path->slots[i]++;
 151                         *level = i;
 152                         node = path->nodes[i];
 153                         WARN_ON(i == 0);
 154                         btrfs_node_key_to_cpu(node, &root->defrag_progress,
 155                                               path->slots[i]);
 156                         root->defrag_level = i;
 157                         return 0;
 158                 } else {
 159                         btrfs_clear_buffer_defrag(path->nodes[*level]);
 160                         free_extent_buffer(path->nodes[*level]);
 161                         path->nodes[*level] = NULL;
 162                         *level = i + 1;
 163                 }
 164         }
 165         return 1;
 166 }
 167
 168 int btrfs_defrag_leaves(struct btrfs_trans_handle *trans,
 169                         struct btrfs_root *root, int cache_only)
 170 {
 171         struct btrfs_path *path = NULL;
 172         struct extent_buffer *tmp;
 173         int ret = 0;
 174         int wret;
 175         int level;
 176         int orig_level;
 177         int i;
 178         int is_extent = 0;
 179         u64 last_ret = 0;
 180
 181         if (root->fs_info->extent_root == root)
 182                 is_extent = 1;
 183
 184         goto out;
 185
 186         if (root->ref_cows == 0 && !is_extent)
 187                 goto out;
 188
 189         if (btrfs_test_opt(root, SSD))
 190                 goto out;
 191
 192         path = btrfs_alloc_path();
 193         if (!path)
 194                 return -ENOMEM;
 195
 196         level = btrfs_header_level(root->node);
 197         orig_level = level;
 198
 199         if (level == 0) {
 200                 goto out;
 201         }
 202         if (root->defrag_progress.objectid == 0) {
 203                 u32 nritems;
 204
 205                 nritems = btrfs_header_nritems(root->node);
 206                 root->defrag_max.objectid = 0;
 207                 /* from above we know this is not a leaf */
 208                 btrfs_node_key_to_cpu(root->node, &root->defrag_max,
 209                                       nritems - 1);
 210                 extent_buffer_get(root->node);
 211                 ret = btrfs_cow_block(trans, root, root->node, NULL, 0, &tmp);
 212                 BUG_ON(ret);
 213                 path->nodes[level] = root->node;
 214                 path->slots[level] = 0;
 215                 if (is_extent)
 216                         btrfs_extent_post_op(trans, root);
 217         } else {
 218                 level = root->defrag_level;
 219                 path->lowest_level = level;
 220                 wret = btrfs_search_slot(trans, root, &root->defrag_progress,
 221                                          path, 0, 1);
 222
 223                 if (is_extent)
 224                         btrfs_extent_post_op(trans, root);
 225
 226                 if (wret < 0) {
 227                         ret = wret;
 228                         goto out;
 229                 }
 230
 231                 while(level > 0 && !path->nodes[level])
 232                         level--;
 233
 234                 if (!path->nodes[level]) {
 235                         ret = 0;
 236                         goto out;
 237                 }
 238         }
 239
 240         while(1) {
 241                 wret = defrag_walk_down(trans, root, path, &level, cache_only,
 242                                         &last_ret);
 243                 if (wret > 0)
 244                         break;
 245                 if (wret < 0)
 246                         ret = wret;
 247
 248                 wret = defrag_walk_up(trans, root, path, &level, cache_only);
 249                 if (wret > 0)
 250                         break;
 251                 if (wret < 0)
 252                         ret = wret;
 253                 else
 254                         ret = -EAGAIN;
 255                 break;
 256         }
 257         for (i = 0; i <= orig_level; i++) {
 258                 if (path->nodes[i]) {
 259                         free_extent_buffer(path->nodes[i]);
 260                         path->nodes[i] = NULL;
 261                 }
 262         }
 263 out:
 264         if (path)
 265                 btrfs_free_path(path);
 266         if (ret == -EAGAIN) {
 267                 if (root->defrag_max.objectid > root->defrag_progress.objectid)
 268                         goto done;
 269                 if (root->defrag_max.type > root->defrag_progress.type)
 270                         goto done;
 271                 if (root->defrag_max.offset > root->defrag_progress.offset)
 272                         goto done;
 273                 ret = 0;
 274         }
 275 done:
 276         if (ret != -EAGAIN) {
 277                 memset(&root->defrag_progress, 0,
 278                        sizeof(root->defrag_progress));
 279         }
 280         return ret;
 281 }