SAFE public projects git trees. - safe/jmp/linux-2.6/blob - 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         int ret = 0;
  55         int is_extent = 0;
  56
  57         WARN_ON(*level < 0);
  58         WARN_ON(*level >= BTRFS_MAX_LEVEL);
  59
  60         if (root->fs_info->extent_root == root)
  61                 is_extent = 1;
  62
  63         if (*level == 1 && cache_only && path->nodes[1] &&
  64             !btrfs_buffer_defrag(path->nodes[1])) {
  65                 goto out;
  66         }
  67         while(*level > 0) {
  68                 WARN_ON(*level < 0);
  69                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
  70                 cur = path->nodes[*level];
  71
  72                 if (!cache_only && *level > 1 && path->slots[*level] == 0)
  73                         reada_defrag(root, cur);
  74
  75                 if (btrfs_header_level(cur) != *level)
  76                         WARN_ON(1);
  77
  78                 if (path->slots[*level] >=
  79                     btrfs_header_nritems(cur))
  80                         break;
  81
  82                 if (*level == 1) {
  83                         WARN_ON(btrfs_header_generation(path->nodes[*level]) !=
  84                                                         trans->transid);
  85                         ret = btrfs_realloc_node(trans, root,
  86                                                  path->nodes[*level],
  87                                                  path->slots[*level],
  88                                                  cache_only, last_ret,
  89                                                  &root->defrag_progress);
  90                         if (is_extent)
  91                                 btrfs_extent_post_op(trans, root);
  92
  93                         break;
  94                 }
  95                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
  96
  97                 if (cache_only) {
  98                         next = btrfs_find_tree_block(root, bytenr,
  99                                            btrfs_level_size(root, *level - 1));
 100                         if (!next || !btrfs_buffer_uptodate(next) ||
 101                             !btrfs_buffer_defrag(next)) {
 102                                 free_extent_buffer(next);
 103                                 path->slots[*level]++;
 104                                 continue;
 105                         }
 106                 } else {
 107                         next = read_tree_block(root, bytenr,
 108                                        btrfs_level_size(root, *level - 1),
 109                                        btrfs_node_ptr_generation(cur,
 110                                                          path->slots[*level]));
 111                 }
 112                 ret = btrfs_cow_block(trans, root, next, path->nodes[*level],
 113                                       path->slots[*level], &next);
 114                 BUG_ON(ret);
 115                 if (is_extent)
 116                         btrfs_extent_post_op(trans, root);
 117
 118                 WARN_ON(*level <= 0);
 119                 if (path->nodes[*level-1])
 120                         free_extent_buffer(path->nodes[*level-1]);
 121                 path->nodes[*level-1] = next;
 122                 *level = btrfs_header_level(next);
 123                 path->slots[*level] = 0;
 124         }
 125         WARN_ON(*level < 0);
 126         WARN_ON(*level >= BTRFS_MAX_LEVEL);
 127
 128         btrfs_clear_buffer_defrag(path->nodes[*level]);
 129 out:
 130         free_extent_buffer(path->nodes[*level]);
 131         path->nodes[*level] = NULL;
 132         *level += 1;
 133         WARN_ON(ret && ret != -EAGAIN);
 134         return ret;
 135 }
 136
 137 static int defrag_walk_up(struct btrfs_trans_handle *trans,
 138                           struct btrfs_root *root,
 139                           struct btrfs_path *path, int *level,
 140                           int cache_only)
 141 {
 142         int i;
 143         int slot;
 144         struct extent_buffer *node;
 145
 146         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
 147                 slot = path->slots[i];
 148                 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
 149                         path->slots[i]++;
 150                         *level = i;
 151                         node = path->nodes[i];
 152                         WARN_ON(i == 0);
 153                         btrfs_node_key_to_cpu(node, &root->defrag_progress,
 154                                               path->slots[i]);
 155                         root->defrag_level = i;
 156                         return 0;
 157                 } else {
 158                         btrfs_clear_buffer_defrag(path->nodes[*level]);
 159                         free_extent_buffer(path->nodes[*level]);
 160                         path->nodes[*level] = NULL;
 161                         *level = i + 1;
 162                 }
 163         }
 164         return 1;
 165 }
 166
 167 int btrfs_defrag_leaves(struct btrfs_trans_handle *trans,
 168                         struct btrfs_root *root, int cache_only)
 169 {
 170         struct btrfs_path *path = NULL;
 171         struct extent_buffer *tmp;
 172         int ret = 0;
 173         int wret;
 174         int level;
 175         int orig_level;
 176         int i;
 177         int is_extent = 0;
 178         u64 last_ret = 0;
 179
 180         if (root->fs_info->extent_root == root)
 181                 is_extent = 1;
 182
 183         if (root->ref_cows == 0 && !is_extent)
 184                 goto out;
 185
 186         if (btrfs_test_opt(root, SSD))
 187                 goto out;
 188
 189         path = btrfs_alloc_path();
 190         if (!path)
 191                 return -ENOMEM;
 192
 193         level = btrfs_header_level(root->node);
 194         orig_level = level;
 195
 196         if (level == 0) {
 197                 goto out;
 198         }
 199         if (root->defrag_progress.objectid == 0) {
 200                 extent_buffer_get(root->node);
 201                 ret = btrfs_cow_block(trans, root, root->node, NULL, 0, &tmp);
 202                 BUG_ON(ret);
 203                 path->nodes[level] = root->node;
 204                 path->slots[level] = 0;
 205                 if (is_extent)
 206                         btrfs_extent_post_op(trans, root);
 207         } else {
 208                 level = root->defrag_level;
 209                 path->lowest_level = level;
 210                 wret = btrfs_search_slot(trans, root, &root->defrag_progress,
 211                                          path, 0, 1);
 212
 213                 if (is_extent)
 214                         btrfs_extent_post_op(trans, root);
 215
 216                 if (wret < 0) {
 217                         ret = wret;
 218                         goto out;
 219                 }
 220
 221                 while(level > 0 && !path->nodes[level])
 222                         level--;
 223
 224                 if (!path->nodes[level]) {
 225                         ret = 0;
 226                         goto out;
 227                 }
 228         }
 229
 230         while(1) {
 231                 wret = defrag_walk_down(trans, root, path, &level, cache_only,
 232                                         &last_ret);
 233                 if (wret > 0)
 234                         break;
 235                 if (wret < 0)
 236                         ret = wret;
 237
 238                 wret = defrag_walk_up(trans, root, path, &level, cache_only);
 239                 if (wret > 0)
 240                         break;
 241                 if (wret < 0)
 242                         ret = wret;
 243                 else
 244                         ret = -EAGAIN;
 245                 break;
 246         }
 247         for (i = 0; i <= orig_level; i++) {
 248                 if (path->nodes[i]) {
 249                         free_extent_buffer(path->nodes[i]);
 250                         path->nodes[i] = NULL;
 251                 }
 252         }
 253 out:
 254         if (path)
 255                 btrfs_free_path(path);
 256         if (ret != -EAGAIN) {
 257                 memset(&root->defrag_progress, 0,
 258                        sizeof(root->defrag_progress));
 259         }
 260         return ret;
 261 }