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