blob: b02355a7b143e4ce82ef5f73b70ed2695430fd3b [file] [log] [blame]
Chris Mason6702ed42007-08-07 16:15:09 -04001/*
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
25static void reada_defrag(struct btrfs_root *root,
Chris Mason5f39d392007-10-15 16:14:19 -040026 struct extent_buffer *node)
Chris Mason6702ed42007-08-07 16:15:09 -040027{
28 int i;
29 u32 nritems;
Chris Masondb945352007-10-15 16:15:53 -040030 u64 bytenr;
31 u32 blocksize;
Chris Mason6702ed42007-08-07 16:15:09 -040032 int ret;
33
Chris Masondb945352007-10-15 16:15:53 -040034 blocksize = btrfs_level_size(root, btrfs_header_level(node) - 1);
Chris Mason5f39d392007-10-15 16:14:19 -040035 nritems = btrfs_header_nritems(node);
Chris Mason6702ed42007-08-07 16:15:09 -040036 for (i = 0; i < nritems; i++) {
Chris Masondb945352007-10-15 16:15:53 -040037 bytenr = btrfs_node_blockptr(node, i);
38 ret = readahead_tree_block(root, bytenr, blocksize);
Chris Mason6702ed42007-08-07 16:15:09 -040039 if (ret)
40 break;
41 }
42}
43
44static int defrag_walk_down(struct btrfs_trans_handle *trans,
45 struct btrfs_root *root,
46 struct btrfs_path *path, int *level,
Chris Masone9d0b132007-08-10 14:06:19 -040047 int cache_only, u64 *last_ret)
Chris Mason6702ed42007-08-07 16:15:09 -040048{
Chris Mason5f39d392007-10-15 16:14:19 -040049 struct extent_buffer *next;
50 struct extent_buffer *cur;
Chris Masondb945352007-10-15 16:15:53 -040051 u64 bytenr;
Chris Mason6702ed42007-08-07 16:15:09 -040052 int ret = 0;
Chris Masone9d0b132007-08-10 14:06:19 -040053 int is_extent = 0;
Chris Mason6702ed42007-08-07 16:15:09 -040054
55 WARN_ON(*level < 0);
56 WARN_ON(*level >= BTRFS_MAX_LEVEL);
57
Chris Masone9d0b132007-08-10 14:06:19 -040058 if (root->fs_info->extent_root == root)
59 is_extent = 1;
60
Chris Mason6702ed42007-08-07 16:15:09 -040061 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)
Chris Mason5f39d392007-10-15 16:14:19 -040067 reada_defrag(root, cur);
Chris Mason6702ed42007-08-07 16:15:09 -040068
Chris Mason5f39d392007-10-15 16:14:19 -040069 if (btrfs_header_level(cur) != *level)
Chris Mason6702ed42007-08-07 16:15:09 -040070 WARN_ON(1);
71
72 if (path->slots[*level] >=
Chris Mason5f39d392007-10-15 16:14:19 -040073 btrfs_header_nritems(cur))
Chris Mason6702ed42007-08-07 16:15:09 -040074 break;
75
76 if (*level == 1) {
77 ret = btrfs_realloc_node(trans, root,
78 path->nodes[*level],
Chris Masona6b6e752007-10-15 16:22:39 -040079 path->slots[*level],
80 cache_only, last_ret,
81 &root->defrag_progress);
Chris Masone9d0b132007-08-10 14:06:19 -040082 if (is_extent)
83 btrfs_extent_post_op(trans, root);
84
Chris Mason6702ed42007-08-07 16:15:09 -040085 break;
86 }
Chris Masondb945352007-10-15 16:15:53 -040087 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
Chris Mason6702ed42007-08-07 16:15:09 -040088
89 if (cache_only) {
Chris Masondb945352007-10-15 16:15:53 -040090 next = btrfs_find_tree_block(root, bytenr,
91 btrfs_level_size(root, *level - 1));
Chris Masoncf786e72007-10-15 16:22:11 -040092 if (!next || !btrfs_buffer_uptodate(next) ||
93 !btrfs_buffer_defrag(next)) {
Chris Mason5f39d392007-10-15 16:14:19 -040094 free_extent_buffer(next);
Chris Mason6702ed42007-08-07 16:15:09 -040095 path->slots[*level]++;
96 continue;
97 }
98 } else {
Chris Masondb945352007-10-15 16:15:53 -040099 next = read_tree_block(root, bytenr,
100 btrfs_level_size(root, *level - 1));
Chris Mason6702ed42007-08-07 16:15:09 -0400101 }
102 ret = btrfs_cow_block(trans, root, next, path->nodes[*level],
103 path->slots[*level], &next);
104 BUG_ON(ret);
Chris Masone9d0b132007-08-10 14:06:19 -0400105 if (is_extent)
106 btrfs_extent_post_op(trans, root);
107
Chris Mason6702ed42007-08-07 16:15:09 -0400108 WARN_ON(*level <= 0);
109 if (path->nodes[*level-1])
Chris Mason5f39d392007-10-15 16:14:19 -0400110 free_extent_buffer(path->nodes[*level-1]);
Chris Mason6702ed42007-08-07 16:15:09 -0400111 path->nodes[*level-1] = next;
Chris Mason5f39d392007-10-15 16:14:19 -0400112 *level = btrfs_header_level(next);
Chris Mason6702ed42007-08-07 16:15:09 -0400113 path->slots[*level] = 0;
114 }
115 WARN_ON(*level < 0);
116 WARN_ON(*level >= BTRFS_MAX_LEVEL);
Chris Mason6b800532007-10-15 16:17:34 -0400117
118 btrfs_clear_buffer_defrag(path->nodes[*level]);
Chris Mason6b800532007-10-15 16:17:34 -0400119
Chris Mason5f39d392007-10-15 16:14:19 -0400120 free_extent_buffer(path->nodes[*level]);
Chris Mason6702ed42007-08-07 16:15:09 -0400121 path->nodes[*level] = NULL;
122 *level += 1;
Chris Masona6b6e752007-10-15 16:22:39 -0400123 WARN_ON(ret && ret != -EAGAIN);
124 return ret;
Chris Mason6702ed42007-08-07 16:15:09 -0400125}
126
127static int defrag_walk_up(struct btrfs_trans_handle *trans,
128 struct btrfs_root *root,
129 struct btrfs_path *path, int *level,
130 int cache_only)
131{
132 int i;
133 int slot;
Chris Mason5f39d392007-10-15 16:14:19 -0400134 struct extent_buffer *node;
Chris Mason6702ed42007-08-07 16:15:09 -0400135
136 for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
137 slot = path->slots[i];
Chris Mason5f39d392007-10-15 16:14:19 -0400138 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
Chris Mason6702ed42007-08-07 16:15:09 -0400139 path->slots[i]++;
140 *level = i;
Chris Mason5f39d392007-10-15 16:14:19 -0400141 node = path->nodes[i];
Chris Mason6702ed42007-08-07 16:15:09 -0400142 WARN_ON(i == 0);
Chris Mason5f39d392007-10-15 16:14:19 -0400143 btrfs_node_key_to_cpu(node, &root->defrag_progress,
144 path->slots[i]);
Chris Mason6702ed42007-08-07 16:15:09 -0400145 root->defrag_level = i;
146 return 0;
147 } else {
Chris Mason6b800532007-10-15 16:17:34 -0400148 btrfs_clear_buffer_defrag(path->nodes[*level]);
Chris Mason5f39d392007-10-15 16:14:19 -0400149 free_extent_buffer(path->nodes[*level]);
Chris Mason6702ed42007-08-07 16:15:09 -0400150 path->nodes[*level] = NULL;
151 *level = i + 1;
152 }
153 }
154 return 1;
155}
156
157int btrfs_defrag_leaves(struct btrfs_trans_handle *trans,
158 struct btrfs_root *root, int cache_only)
159{
160 struct btrfs_path *path = NULL;
Chris Mason5f39d392007-10-15 16:14:19 -0400161 struct extent_buffer *tmp;
Chris Mason6702ed42007-08-07 16:15:09 -0400162 int ret = 0;
163 int wret;
164 int level;
165 int orig_level;
166 int i;
Chris Masone9d0b132007-08-10 14:06:19 -0400167 int is_extent = 0;
168 u64 last_ret = 0;
Chris Mason6702ed42007-08-07 16:15:09 -0400169
Chris Masone9d0b132007-08-10 14:06:19 -0400170 if (root->fs_info->extent_root == root)
171 is_extent = 1;
172
173 if (root->ref_cows == 0 && !is_extent)
Chris Mason6702ed42007-08-07 16:15:09 -0400174 goto out;
Chris Mason5f39d392007-10-15 16:14:19 -0400175
Chris Mason6702ed42007-08-07 16:15:09 -0400176 path = btrfs_alloc_path();
177 if (!path)
178 return -ENOMEM;
179
Chris Mason5f39d392007-10-15 16:14:19 -0400180 level = btrfs_header_level(root->node);
Chris Mason6702ed42007-08-07 16:15:09 -0400181 orig_level = level;
Chris Mason0f1ebbd2007-10-15 16:19:46 -0400182
Chris Mason6702ed42007-08-07 16:15:09 -0400183 if (level == 0) {
184 goto out;
185 }
Chris Mason0f1ebbd2007-10-15 16:19:46 -0400186
Chris Mason6702ed42007-08-07 16:15:09 -0400187 if (root->defrag_progress.objectid == 0) {
Chris Mason5f39d392007-10-15 16:14:19 -0400188 extent_buffer_get(root->node);
Chris Mason6702ed42007-08-07 16:15:09 -0400189 ret = btrfs_cow_block(trans, root, root->node, NULL, 0, &tmp);
190 BUG_ON(ret);
Chris Mason6702ed42007-08-07 16:15:09 -0400191 path->nodes[level] = root->node;
192 path->slots[level] = 0;
Chris Masone9d0b132007-08-10 14:06:19 -0400193 if (is_extent)
194 btrfs_extent_post_op(trans, root);
Chris Mason6702ed42007-08-07 16:15:09 -0400195 } else {
196 level = root->defrag_level;
197 path->lowest_level = level;
198 wret = btrfs_search_slot(trans, root, &root->defrag_progress,
199 path, 0, 1);
200
Chris Masone9d0b132007-08-10 14:06:19 -0400201 if (is_extent)
202 btrfs_extent_post_op(trans, root);
Chris Mason5f39d392007-10-15 16:14:19 -0400203
Chris Mason6702ed42007-08-07 16:15:09 -0400204 if (wret < 0) {
205 ret = wret;
206 goto out;
207 }
Chris Mason5f39d392007-10-15 16:14:19 -0400208
Chris Mason6702ed42007-08-07 16:15:09 -0400209 while(level > 0 && !path->nodes[level])
210 level--;
Chris Mason5f39d392007-10-15 16:14:19 -0400211
Chris Mason6702ed42007-08-07 16:15:09 -0400212 if (!path->nodes[level]) {
213 ret = 0;
214 goto out;
215 }
216 }
217
218 while(1) {
Chris Masone9d0b132007-08-10 14:06:19 -0400219 wret = defrag_walk_down(trans, root, path, &level, cache_only,
220 &last_ret);
Chris Mason6702ed42007-08-07 16:15:09 -0400221 if (wret > 0)
222 break;
223 if (wret < 0)
224 ret = wret;
225
226 wret = defrag_walk_up(trans, root, path, &level, cache_only);
227 if (wret > 0)
228 break;
229 if (wret < 0)
230 ret = wret;
Chris Mason409eb952007-08-08 20:17:12 -0400231 ret = -EAGAIN;
232 break;
Chris Mason6702ed42007-08-07 16:15:09 -0400233 }
234 for (i = 0; i <= orig_level; i++) {
235 if (path->nodes[i]) {
Chris Mason5f39d392007-10-15 16:14:19 -0400236 free_extent_buffer(path->nodes[i]);
Chris Mason0f827312007-10-15 16:18:56 -0400237 path->nodes[i] = NULL;
Chris Mason6702ed42007-08-07 16:15:09 -0400238 }
239 }
240out:
241 if (path)
242 btrfs_free_path(path);
243 if (ret != -EAGAIN) {
244 memset(&root->defrag_progress, 0,
245 sizeof(root->defrag_progress));
246 }
247 return ret;
248}