blob: b2ae8e768b6c4f90a7fc2ae1408c770ec4e65507 [file] [log] [blame]
Chris Mason2e635a22007-03-21 11:12:56 -04001#include <linux/module.h>
Chris Masonfec577f2007-02-26 10:40:21 -05002#include "ctree.h"
3#include "disk-io.h"
4#include "print-tree.h"
Chris Masone089f052007-03-16 16:20:31 -04005#include "transaction.h"
Chris Masonfec577f2007-02-26 10:40:21 -05006
Chris Masone089f052007-03-16 16:20:31 -04007static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
8 *orig_root, u64 num_blocks, u64 search_start, u64
9 search_end, struct btrfs_key *ins);
10static int finish_current_insert(struct btrfs_trans_handle *trans, struct
11 btrfs_root *extent_root);
Chris Masone20d96d2007-03-22 12:13:20 -040012static int del_pending_extents(struct btrfs_trans_handle *trans, struct
13 btrfs_root *extent_root);
Chris Masonfec577f2007-02-26 10:40:21 -050014
Chris Masone089f052007-03-16 16:20:31 -040015static int inc_block_ref(struct btrfs_trans_handle *trans, struct btrfs_root
Chris Mason6407bf62007-03-27 06:33:00 -040016 *root, u64 blocknr, u64 num_blocks)
Chris Mason02217ed2007-03-02 16:08:05 -050017{
Chris Mason234b63a2007-03-13 10:46:10 -040018 struct btrfs_path path;
Chris Mason02217ed2007-03-02 16:08:05 -050019 int ret;
Chris Masone2fa7222007-03-12 16:22:34 -040020 struct btrfs_key key;
Chris Mason234b63a2007-03-13 10:46:10 -040021 struct btrfs_leaf *l;
22 struct btrfs_extent_item *item;
Chris Masone2fa7222007-03-12 16:22:34 -040023 struct btrfs_key ins;
Chris Masoncf27e1e2007-03-13 09:49:06 -040024 u32 refs;
Chris Mason037e6392007-03-07 11:50:24 -050025
Chris Mason9f5fae22007-03-20 14:38:32 -040026 find_free_extent(trans, root->fs_info->extent_root, 0, 0, (u64)-1,
27 &ins);
Chris Mason234b63a2007-03-13 10:46:10 -040028 btrfs_init_path(&path);
Chris Mason02217ed2007-03-02 16:08:05 -050029 key.objectid = blocknr;
30 key.flags = 0;
Chris Mason62e27492007-03-15 12:56:47 -040031 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
Chris Mason6407bf62007-03-27 06:33:00 -040032 key.offset = num_blocks;
Chris Mason9f5fae22007-03-20 14:38:32 -040033 ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, &path,
34 0, 1);
Chris Masona28ec192007-03-06 20:08:01 -050035 if (ret != 0)
36 BUG();
Chris Mason02217ed2007-03-02 16:08:05 -050037 BUG_ON(ret != 0);
Chris Masone20d96d2007-03-22 12:13:20 -040038 l = btrfs_buffer_leaf(path.nodes[0]);
Chris Mason4beb1b82007-03-14 10:31:29 -040039 item = btrfs_item_ptr(l, path.slots[0], struct btrfs_extent_item);
Chris Masoncf27e1e2007-03-13 09:49:06 -040040 refs = btrfs_extent_refs(item);
41 btrfs_set_extent_refs(item, refs + 1);
Chris Masond5719762007-03-23 10:01:08 -040042 mark_buffer_dirty(path.nodes[0]);
Chris Masona28ec192007-03-06 20:08:01 -050043
Chris Mason9f5fae22007-03-20 14:38:32 -040044 btrfs_release_path(root->fs_info->extent_root, &path);
45 finish_current_insert(trans, root->fs_info->extent_root);
Chris Masone20d96d2007-03-22 12:13:20 -040046 del_pending_extents(trans, root->fs_info->extent_root);
Chris Mason02217ed2007-03-02 16:08:05 -050047 return 0;
48}
49
Chris Masone089f052007-03-16 16:20:31 -040050static int lookup_block_ref(struct btrfs_trans_handle *trans, struct btrfs_root
Chris Mason6407bf62007-03-27 06:33:00 -040051 *root, u64 blocknr, u64 num_blocks, u32 *refs)
Chris Masona28ec192007-03-06 20:08:01 -050052{
Chris Mason234b63a2007-03-13 10:46:10 -040053 struct btrfs_path path;
Chris Masona28ec192007-03-06 20:08:01 -050054 int ret;
Chris Masone2fa7222007-03-12 16:22:34 -040055 struct btrfs_key key;
Chris Mason234b63a2007-03-13 10:46:10 -040056 struct btrfs_leaf *l;
57 struct btrfs_extent_item *item;
58 btrfs_init_path(&path);
Chris Masona28ec192007-03-06 20:08:01 -050059 key.objectid = blocknr;
Chris Mason6407bf62007-03-27 06:33:00 -040060 key.offset = num_blocks;
Chris Mason62e27492007-03-15 12:56:47 -040061 key.flags = 0;
62 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
Chris Mason9f5fae22007-03-20 14:38:32 -040063 ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, &path,
64 0, 0);
Chris Masona28ec192007-03-06 20:08:01 -050065 if (ret != 0)
66 BUG();
Chris Masone20d96d2007-03-22 12:13:20 -040067 l = btrfs_buffer_leaf(path.nodes[0]);
Chris Mason4beb1b82007-03-14 10:31:29 -040068 item = btrfs_item_ptr(l, path.slots[0], struct btrfs_extent_item);
Chris Masoncf27e1e2007-03-13 09:49:06 -040069 *refs = btrfs_extent_refs(item);
Chris Mason9f5fae22007-03-20 14:38:32 -040070 btrfs_release_path(root->fs_info->extent_root, &path);
Chris Masona28ec192007-03-06 20:08:01 -050071 return 0;
72}
73
Chris Masone089f052007-03-16 16:20:31 -040074int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
Chris Masone20d96d2007-03-22 12:13:20 -040075 struct buffer_head *buf)
Chris Mason02217ed2007-03-02 16:08:05 -050076{
77 u64 blocknr;
Chris Masone20d96d2007-03-22 12:13:20 -040078 struct btrfs_node *buf_node;
Chris Mason6407bf62007-03-27 06:33:00 -040079 struct btrfs_leaf *buf_leaf;
80 struct btrfs_disk_key *key;
81 struct btrfs_file_extent_item *fi;
Chris Mason02217ed2007-03-02 16:08:05 -050082 int i;
Chris Mason6407bf62007-03-27 06:33:00 -040083 int leaf;
84 int ret;
Chris Masona28ec192007-03-06 20:08:01 -050085
Chris Mason3768f362007-03-13 16:47:54 -040086 if (!root->ref_cows)
Chris Masona28ec192007-03-06 20:08:01 -050087 return 0;
Chris Masone20d96d2007-03-22 12:13:20 -040088 buf_node = btrfs_buffer_node(buf);
Chris Mason6407bf62007-03-27 06:33:00 -040089 leaf = btrfs_is_leaf(buf_node);
90 buf_leaf = btrfs_buffer_leaf(buf);
Chris Masone20d96d2007-03-22 12:13:20 -040091 for (i = 0; i < btrfs_header_nritems(&buf_node->header); i++) {
Chris Mason6407bf62007-03-27 06:33:00 -040092 if (leaf) {
93 key = &buf_leaf->items[i].key;
94 if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY)
95 continue;
96 fi = btrfs_item_ptr(buf_leaf, i,
97 struct btrfs_file_extent_item);
98 ret = inc_block_ref(trans, root,
99 btrfs_file_extent_disk_blocknr(fi),
100 btrfs_file_extent_disk_num_blocks(fi));
101 BUG_ON(ret);
102 } else {
103 blocknr = btrfs_node_blockptr(buf_node, i);
104 ret = inc_block_ref(trans, root, blocknr, 1);
105 BUG_ON(ret);
106 }
Chris Mason02217ed2007-03-02 16:08:05 -0500107 }
108 return 0;
109}
110
Chris Masone089f052007-03-16 16:20:31 -0400111int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans, struct
112 btrfs_root *root)
Chris Masona28ec192007-03-06 20:08:01 -0500113{
Chris Mason8ef97622007-03-26 10:15:30 -0400114 unsigned long gang[8];
Chris Mason88fd1462007-03-16 08:56:18 -0400115 u64 first = 0;
Chris Masona28ec192007-03-06 20:08:01 -0500116 int ret;
117 int i;
Chris Mason8ef97622007-03-26 10:15:30 -0400118 struct radix_tree_root *pinned_radix = &root->fs_info->pinned_radix;
Chris Masona28ec192007-03-06 20:08:01 -0500119
120 while(1) {
Chris Mason8ef97622007-03-26 10:15:30 -0400121 ret = find_first_radix_bit(pinned_radix, gang,
122 ARRAY_SIZE(gang));
Chris Masona28ec192007-03-06 20:08:01 -0500123 if (!ret)
124 break;
Chris Mason88fd1462007-03-16 08:56:18 -0400125 if (!first)
Chris Mason8ef97622007-03-26 10:15:30 -0400126 first = gang[0];
Chris Mason0579da42007-03-07 16:15:30 -0500127 for (i = 0; i < ret; i++) {
Chris Mason8ef97622007-03-26 10:15:30 -0400128 clear_radix_bit(pinned_radix, gang[i]);
Chris Mason0579da42007-03-07 16:15:30 -0500129 }
Chris Masona28ec192007-03-06 20:08:01 -0500130 }
Chris Masond5719762007-03-23 10:01:08 -0400131 if (root->fs_info->last_insert.objectid > first)
132 root->fs_info->last_insert.objectid = first;
Chris Mason9f5fae22007-03-20 14:38:32 -0400133 root->fs_info->last_insert.offset = 0;
Chris Masona28ec192007-03-06 20:08:01 -0500134 return 0;
135}
136
Chris Masone089f052007-03-16 16:20:31 -0400137static int finish_current_insert(struct btrfs_trans_handle *trans, struct
138 btrfs_root *extent_root)
Chris Mason037e6392007-03-07 11:50:24 -0500139{
Chris Masone2fa7222007-03-12 16:22:34 -0400140 struct btrfs_key ins;
Chris Mason234b63a2007-03-13 10:46:10 -0400141 struct btrfs_extent_item extent_item;
Chris Mason037e6392007-03-07 11:50:24 -0500142 int i;
143 int ret;
Chris Mason1261ec42007-03-20 20:35:03 -0400144 u64 super_blocks_used;
145 struct btrfs_fs_info *info = extent_root->fs_info;
Chris Mason037e6392007-03-07 11:50:24 -0500146
Chris Masoncf27e1e2007-03-13 09:49:06 -0400147 btrfs_set_extent_refs(&extent_item, 1);
148 btrfs_set_extent_owner(&extent_item,
Chris Masone20d96d2007-03-22 12:13:20 -0400149 btrfs_header_parentid(btrfs_buffer_header(extent_root->node)));
Chris Mason037e6392007-03-07 11:50:24 -0500150 ins.offset = 1;
151 ins.flags = 0;
Chris Mason62e27492007-03-15 12:56:47 -0400152 btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
Chris Mason037e6392007-03-07 11:50:24 -0500153
Chris Mason9f5fae22007-03-20 14:38:32 -0400154 for (i = 0; i < extent_root->fs_info->current_insert.flags; i++) {
155 ins.objectid = extent_root->fs_info->current_insert.objectid +
156 i;
Chris Mason1261ec42007-03-20 20:35:03 -0400157 super_blocks_used = btrfs_super_blocks_used(info->disk_super);
158 btrfs_set_super_blocks_used(info->disk_super,
159 super_blocks_used + 1);
Chris Masone089f052007-03-16 16:20:31 -0400160 ret = btrfs_insert_item(trans, extent_root, &ins, &extent_item,
161 sizeof(extent_item));
Chris Mason037e6392007-03-07 11:50:24 -0500162 BUG_ON(ret);
163 }
Chris Mason9f5fae22007-03-20 14:38:32 -0400164 extent_root->fs_info->current_insert.offset = 0;
Chris Mason037e6392007-03-07 11:50:24 -0500165 return 0;
166}
167
Chris Mason8ef97622007-03-26 10:15:30 -0400168static int pin_down_block(struct btrfs_root *root, u64 blocknr, int pending)
Chris Masone20d96d2007-03-22 12:13:20 -0400169{
170 int err;
Chris Mason78fae272007-03-25 11:35:08 -0400171 struct btrfs_header *header;
Chris Mason8ef97622007-03-26 10:15:30 -0400172 struct buffer_head *bh;
Chris Mason78fae272007-03-25 11:35:08 -0400173
Chris Masonf4b9aa82007-03-27 11:05:53 -0400174 if (!pending) {
Chris Masond98237b2007-03-28 13:57:48 -0400175 bh = btrfs_find_tree_block(root, blocknr);
176 if (bh && buffer_uptodate(bh)) {
Chris Masonf4b9aa82007-03-27 11:05:53 -0400177 header = btrfs_buffer_header(bh);
178 if (btrfs_header_generation(header) ==
179 root->fs_info->running_transaction->transid) {
180 brelse(bh);
181 return 0;
182 }
Chris Mason8ef97622007-03-26 10:15:30 -0400183 brelse(bh);
Chris Mason8ef97622007-03-26 10:15:30 -0400184 }
Chris Mason8ef97622007-03-26 10:15:30 -0400185 err = set_radix_bit(&root->fs_info->pinned_radix, blocknr);
Chris Masonf4b9aa82007-03-27 11:05:53 -0400186 } else {
187 err = set_radix_bit(&root->fs_info->pending_del_radix, blocknr);
188 }
Chris Mason8ef97622007-03-26 10:15:30 -0400189 BUG_ON(err);
Chris Masone20d96d2007-03-22 12:13:20 -0400190 return 0;
191}
192
Chris Masona28ec192007-03-06 20:08:01 -0500193/*
194 * remove an extent from the root, returns 0 on success
195 */
Chris Masone089f052007-03-16 16:20:31 -0400196static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
Chris Mason78fae272007-03-25 11:35:08 -0400197 *root, u64 blocknr, u64 num_blocks, int pin)
Chris Masona28ec192007-03-06 20:08:01 -0500198{
Chris Mason234b63a2007-03-13 10:46:10 -0400199 struct btrfs_path path;
Chris Masone2fa7222007-03-12 16:22:34 -0400200 struct btrfs_key key;
Chris Mason1261ec42007-03-20 20:35:03 -0400201 struct btrfs_fs_info *info = root->fs_info;
202 struct btrfs_root *extent_root = info->extent_root;
Chris Masona28ec192007-03-06 20:08:01 -0500203 int ret;
Chris Mason234b63a2007-03-13 10:46:10 -0400204 struct btrfs_extent_item *ei;
Chris Masone2fa7222007-03-12 16:22:34 -0400205 struct btrfs_key ins;
Chris Masoncf27e1e2007-03-13 09:49:06 -0400206 u32 refs;
Chris Mason037e6392007-03-07 11:50:24 -0500207
Chris Masona28ec192007-03-06 20:08:01 -0500208 key.objectid = blocknr;
209 key.flags = 0;
Chris Mason62e27492007-03-15 12:56:47 -0400210 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
Chris Masona28ec192007-03-06 20:08:01 -0500211 key.offset = num_blocks;
212
Chris Masone089f052007-03-16 16:20:31 -0400213 find_free_extent(trans, root, 0, 0, (u64)-1, &ins);
Chris Mason234b63a2007-03-13 10:46:10 -0400214 btrfs_init_path(&path);
Chris Masone089f052007-03-16 16:20:31 -0400215 ret = btrfs_search_slot(trans, extent_root, &key, &path, -1, 1);
Chris Masona28ec192007-03-06 20:08:01 -0500216 if (ret) {
Chris Mason2e635a22007-03-21 11:12:56 -0400217 printk("failed to find %Lu\n", key.objectid);
Chris Mason234b63a2007-03-13 10:46:10 -0400218 btrfs_print_tree(extent_root, extent_root->node);
Chris Mason2e635a22007-03-21 11:12:56 -0400219 printk("failed to find %Lu\n", key.objectid);
Chris Masona28ec192007-03-06 20:08:01 -0500220 BUG();
221 }
Chris Masone20d96d2007-03-22 12:13:20 -0400222 ei = btrfs_item_ptr(btrfs_buffer_leaf(path.nodes[0]), path.slots[0],
Chris Mason123abc82007-03-14 14:14:43 -0400223 struct btrfs_extent_item);
Chris Masona28ec192007-03-06 20:08:01 -0500224 BUG_ON(ei->refs == 0);
Chris Masoncf27e1e2007-03-13 09:49:06 -0400225 refs = btrfs_extent_refs(ei) - 1;
226 btrfs_set_extent_refs(ei, refs);
Chris Masonf4b9aa82007-03-27 11:05:53 -0400227 mark_buffer_dirty(path.nodes[0]);
Chris Masoncf27e1e2007-03-13 09:49:06 -0400228 if (refs == 0) {
Chris Mason1261ec42007-03-20 20:35:03 -0400229 u64 super_blocks_used;
Chris Mason78fae272007-03-25 11:35:08 -0400230
231 if (pin) {
Chris Mason8ef97622007-03-26 10:15:30 -0400232 ret = pin_down_block(root, blocknr, 0);
Chris Mason78fae272007-03-25 11:35:08 -0400233 BUG_ON(ret);
234 }
235
Chris Mason1261ec42007-03-20 20:35:03 -0400236 super_blocks_used = btrfs_super_blocks_used(info->disk_super);
237 btrfs_set_super_blocks_used(info->disk_super,
238 super_blocks_used - num_blocks);
Chris Masone089f052007-03-16 16:20:31 -0400239 ret = btrfs_del_item(trans, extent_root, &path);
Chris Mason78fae272007-03-25 11:35:08 -0400240 if (extent_root->fs_info->last_insert.objectid > blocknr)
Chris Mason9f5fae22007-03-20 14:38:32 -0400241 extent_root->fs_info->last_insert.objectid = blocknr;
Chris Masona28ec192007-03-06 20:08:01 -0500242 if (ret)
243 BUG();
244 }
Chris Mason234b63a2007-03-13 10:46:10 -0400245 btrfs_release_path(extent_root, &path);
Chris Masone089f052007-03-16 16:20:31 -0400246 finish_current_insert(trans, extent_root);
Chris Masona28ec192007-03-06 20:08:01 -0500247 return ret;
248}
249
250/*
Chris Masonfec577f2007-02-26 10:40:21 -0500251 * find all the blocks marked as pending in the radix tree and remove
252 * them from the extent map
253 */
Chris Masone089f052007-03-16 16:20:31 -0400254static int del_pending_extents(struct btrfs_trans_handle *trans, struct
255 btrfs_root *extent_root)
Chris Masonfec577f2007-02-26 10:40:21 -0500256{
257 int ret;
Chris Masone20d96d2007-03-22 12:13:20 -0400258 int wret;
259 int err = 0;
Chris Mason8ef97622007-03-26 10:15:30 -0400260 unsigned long gang[4];
Chris Masonfec577f2007-02-26 10:40:21 -0500261 int i;
Chris Mason8ef97622007-03-26 10:15:30 -0400262 struct radix_tree_root *pending_radix;
263 struct radix_tree_root *pinned_radix;
264
265 pending_radix = &extent_root->fs_info->pending_del_radix;
266 pinned_radix = &extent_root->fs_info->pinned_radix;
Chris Masonfec577f2007-02-26 10:40:21 -0500267
268 while(1) {
Chris Mason8ef97622007-03-26 10:15:30 -0400269 ret = find_first_radix_bit(pending_radix, gang,
270 ARRAY_SIZE(gang));
Chris Masonfec577f2007-02-26 10:40:21 -0500271 if (!ret)
272 break;
273 for (i = 0; i < ret; i++) {
Chris Mason8ef97622007-03-26 10:15:30 -0400274 wret = set_radix_bit(pinned_radix, gang[i]);
275 BUG_ON(wret);
276 wret = clear_radix_bit(pending_radix, gang[i]);
277 BUG_ON(wret);
Chris Masond5719762007-03-23 10:01:08 -0400278 wret = __free_extent(trans, extent_root,
Chris Mason8ef97622007-03-26 10:15:30 -0400279 gang[i], 1, 0);
Chris Masone20d96d2007-03-22 12:13:20 -0400280 if (wret)
281 err = wret;
Chris Masonfec577f2007-02-26 10:40:21 -0500282 }
283 }
Chris Masone20d96d2007-03-22 12:13:20 -0400284 return err;
Chris Masonfec577f2007-02-26 10:40:21 -0500285}
286
287/*
288 * remove an extent from the root, returns 0 on success
289 */
Chris Masone089f052007-03-16 16:20:31 -0400290int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
291 *root, u64 blocknr, u64 num_blocks, int pin)
Chris Masonfec577f2007-02-26 10:40:21 -0500292{
Chris Mason9f5fae22007-03-20 14:38:32 -0400293 struct btrfs_root *extent_root = root->fs_info->extent_root;
Chris Masonfec577f2007-02-26 10:40:21 -0500294 int pending_ret;
295 int ret;
Chris Masona28ec192007-03-06 20:08:01 -0500296
297 if (root == extent_root) {
Chris Mason8ef97622007-03-26 10:15:30 -0400298 pin_down_block(root, blocknr, 1);
Chris Masona28ec192007-03-06 20:08:01 -0500299 return 0;
300 }
Chris Mason78fae272007-03-25 11:35:08 -0400301 ret = __free_extent(trans, root, blocknr, num_blocks, pin);
Chris Masone20d96d2007-03-22 12:13:20 -0400302 pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
Chris Masonfec577f2007-02-26 10:40:21 -0500303 return ret ? ret : pending_ret;
304}
305
306/*
307 * walks the btree of allocated extents and find a hole of a given size.
308 * The key ins is changed to record the hole:
309 * ins->objectid == block start
Chris Mason62e27492007-03-15 12:56:47 -0400310 * ins->flags = BTRFS_EXTENT_ITEM_KEY
Chris Masonfec577f2007-02-26 10:40:21 -0500311 * ins->offset == number of blocks
312 * Any available blocks before search_start are skipped.
313 */
Chris Masone089f052007-03-16 16:20:31 -0400314static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
315 *orig_root, u64 num_blocks, u64 search_start, u64
316 search_end, struct btrfs_key *ins)
Chris Masonfec577f2007-02-26 10:40:21 -0500317{
Chris Mason234b63a2007-03-13 10:46:10 -0400318 struct btrfs_path path;
Chris Masone2fa7222007-03-12 16:22:34 -0400319 struct btrfs_key key;
Chris Masonfec577f2007-02-26 10:40:21 -0500320 int ret;
321 u64 hole_size = 0;
322 int slot = 0;
Chris Masone20d96d2007-03-22 12:13:20 -0400323 u64 last_block = 0;
Chris Mason037e6392007-03-07 11:50:24 -0500324 u64 test_block;
Chris Masonfec577f2007-02-26 10:40:21 -0500325 int start_found;
Chris Mason234b63a2007-03-13 10:46:10 -0400326 struct btrfs_leaf *l;
Chris Mason9f5fae22007-03-20 14:38:32 -0400327 struct btrfs_root * root = orig_root->fs_info->extent_root;
Chris Mason0579da42007-03-07 16:15:30 -0500328 int total_needed = num_blocks;
Chris Masone20d96d2007-03-22 12:13:20 -0400329 int level;
Chris Masonfec577f2007-02-26 10:40:21 -0500330
Chris Masone20d96d2007-03-22 12:13:20 -0400331 level = btrfs_header_level(btrfs_buffer_header(root->node));
332 total_needed += (level + 1) * 3;
Chris Mason9f5fae22007-03-20 14:38:32 -0400333 if (root->fs_info->last_insert.objectid > search_start)
334 search_start = root->fs_info->last_insert.objectid;
Chris Mason62e27492007-03-15 12:56:47 -0400335
336 ins->flags = 0;
337 btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
338
Chris Masonfec577f2007-02-26 10:40:21 -0500339check_failed:
Chris Mason234b63a2007-03-13 10:46:10 -0400340 btrfs_init_path(&path);
Chris Masonfec577f2007-02-26 10:40:21 -0500341 ins->objectid = search_start;
342 ins->offset = 0;
Chris Masonfec577f2007-02-26 10:40:21 -0500343 start_found = 0;
Chris Masone089f052007-03-16 16:20:31 -0400344 ret = btrfs_search_slot(trans, root, ins, &path, 0, 0);
Chris Mason0f70abe2007-02-28 16:46:22 -0500345 if (ret < 0)
346 goto error;
Chris Masonaa5d6be2007-02-28 16:35:06 -0500347
Chris Mason0579da42007-03-07 16:15:30 -0500348 if (path.slots[0] > 0)
349 path.slots[0]--;
350
Chris Masonfec577f2007-02-26 10:40:21 -0500351 while (1) {
Chris Masone20d96d2007-03-22 12:13:20 -0400352 l = btrfs_buffer_leaf(path.nodes[0]);
Chris Masonfec577f2007-02-26 10:40:21 -0500353 slot = path.slots[0];
Chris Mason7518a232007-03-12 12:01:18 -0400354 if (slot >= btrfs_header_nritems(&l->header)) {
Chris Mason234b63a2007-03-13 10:46:10 -0400355 ret = btrfs_next_leaf(root, &path);
Chris Masonfec577f2007-02-26 10:40:21 -0500356 if (ret == 0)
357 continue;
Chris Mason0f70abe2007-02-28 16:46:22 -0500358 if (ret < 0)
359 goto error;
Chris Masonfec577f2007-02-26 10:40:21 -0500360 if (!start_found) {
361 ins->objectid = search_start;
Chris Mason037e6392007-03-07 11:50:24 -0500362 ins->offset = (u64)-1;
Chris Masonfec577f2007-02-26 10:40:21 -0500363 start_found = 1;
364 goto check_pending;
365 }
366 ins->objectid = last_block > search_start ?
367 last_block : search_start;
Chris Mason037e6392007-03-07 11:50:24 -0500368 ins->offset = (u64)-1;
Chris Masonfec577f2007-02-26 10:40:21 -0500369 goto check_pending;
370 }
Chris Masone2fa7222007-03-12 16:22:34 -0400371 btrfs_disk_key_to_cpu(&key, &l->items[slot].key);
372 if (key.objectid >= search_start) {
Chris Masonfec577f2007-02-26 10:40:21 -0500373 if (start_found) {
Chris Mason0579da42007-03-07 16:15:30 -0500374 if (last_block < search_start)
375 last_block = search_start;
Chris Masone2fa7222007-03-12 16:22:34 -0400376 hole_size = key.objectid - last_block;
Chris Mason037e6392007-03-07 11:50:24 -0500377 if (hole_size > total_needed) {
Chris Masonfec577f2007-02-26 10:40:21 -0500378 ins->objectid = last_block;
Chris Mason037e6392007-03-07 11:50:24 -0500379 ins->offset = hole_size;
Chris Masonfec577f2007-02-26 10:40:21 -0500380 goto check_pending;
381 }
Chris Mason0579da42007-03-07 16:15:30 -0500382 }
Chris Masonfec577f2007-02-26 10:40:21 -0500383 }
Chris Mason0579da42007-03-07 16:15:30 -0500384 start_found = 1;
Chris Masone2fa7222007-03-12 16:22:34 -0400385 last_block = key.objectid + key.offset;
Chris Masonfec577f2007-02-26 10:40:21 -0500386 path.slots[0]++;
387 }
388 // FIXME -ENOSPC
389check_pending:
390 /* we have to make sure we didn't find an extent that has already
391 * been allocated by the map tree or the original allocation
392 */
Chris Mason234b63a2007-03-13 10:46:10 -0400393 btrfs_release_path(root, &path);
Chris Masonfec577f2007-02-26 10:40:21 -0500394 BUG_ON(ins->objectid < search_start);
Chris Mason037e6392007-03-07 11:50:24 -0500395 for (test_block = ins->objectid;
396 test_block < ins->objectid + total_needed; test_block++) {
Chris Mason8ef97622007-03-26 10:15:30 -0400397 if (test_radix_bit(&root->fs_info->pinned_radix,
Chris Mason9f5fae22007-03-20 14:38:32 -0400398 test_block)) {
Chris Mason037e6392007-03-07 11:50:24 -0500399 search_start = test_block + 1;
Chris Masonfec577f2007-02-26 10:40:21 -0500400 goto check_failed;
401 }
402 }
Chris Mason9f5fae22007-03-20 14:38:32 -0400403 BUG_ON(root->fs_info->current_insert.offset);
404 root->fs_info->current_insert.offset = total_needed - num_blocks;
405 root->fs_info->current_insert.objectid = ins->objectid + num_blocks;
406 root->fs_info->current_insert.flags = 0;
407 root->fs_info->last_insert.objectid = ins->objectid;
Chris Mason037e6392007-03-07 11:50:24 -0500408 ins->offset = num_blocks;
Chris Masonfec577f2007-02-26 10:40:21 -0500409 return 0;
Chris Mason0f70abe2007-02-28 16:46:22 -0500410error:
Chris Mason234b63a2007-03-13 10:46:10 -0400411 btrfs_release_path(root, &path);
Chris Mason0f70abe2007-02-28 16:46:22 -0500412 return ret;
Chris Masonfec577f2007-02-26 10:40:21 -0500413}
414
415/*
Chris Masonfec577f2007-02-26 10:40:21 -0500416 * finds a free extent and does all the dirty work required for allocation
417 * returns the key for the extent through ins, and a tree buffer for
418 * the first block of the extent through buf.
419 *
420 * returns 0 if everything worked, non-zero otherwise.
421 */
Chris Masondee26a92007-03-26 16:00:06 -0400422int btrfs_alloc_extent(struct btrfs_trans_handle *trans, struct btrfs_root
Chris Masone089f052007-03-16 16:20:31 -0400423 *root, u64 num_blocks, u64 search_start, u64
424 search_end, u64 owner, struct btrfs_key *ins)
Chris Masonfec577f2007-02-26 10:40:21 -0500425{
426 int ret;
427 int pending_ret;
Chris Mason1261ec42007-03-20 20:35:03 -0400428 u64 super_blocks_used;
429 struct btrfs_fs_info *info = root->fs_info;
430 struct btrfs_root *extent_root = info->extent_root;
Chris Mason234b63a2007-03-13 10:46:10 -0400431 struct btrfs_extent_item extent_item;
Chris Mason037e6392007-03-07 11:50:24 -0500432
Chris Masoncf27e1e2007-03-13 09:49:06 -0400433 btrfs_set_extent_refs(&extent_item, 1);
434 btrfs_set_extent_owner(&extent_item, owner);
Chris Masonfec577f2007-02-26 10:40:21 -0500435
Chris Mason037e6392007-03-07 11:50:24 -0500436 if (root == extent_root) {
Chris Mason9f5fae22007-03-20 14:38:32 -0400437 BUG_ON(extent_root->fs_info->current_insert.offset == 0);
Chris Mason037e6392007-03-07 11:50:24 -0500438 BUG_ON(num_blocks != 1);
Chris Mason9f5fae22007-03-20 14:38:32 -0400439 BUG_ON(extent_root->fs_info->current_insert.flags ==
440 extent_root->fs_info->current_insert.offset);
Chris Mason037e6392007-03-07 11:50:24 -0500441 ins->offset = 1;
Chris Mason9f5fae22007-03-20 14:38:32 -0400442 ins->objectid = extent_root->fs_info->current_insert.objectid +
443 extent_root->fs_info->current_insert.flags++;
Chris Masonfec577f2007-02-26 10:40:21 -0500444 return 0;
445 }
Chris Masone089f052007-03-16 16:20:31 -0400446 ret = find_free_extent(trans, root, num_blocks, search_start,
Chris Mason037e6392007-03-07 11:50:24 -0500447 search_end, ins);
448 if (ret)
449 return ret;
Chris Masonfec577f2007-02-26 10:40:21 -0500450
Chris Mason1261ec42007-03-20 20:35:03 -0400451 super_blocks_used = btrfs_super_blocks_used(info->disk_super);
452 btrfs_set_super_blocks_used(info->disk_super, super_blocks_used +
453 num_blocks);
Chris Masone089f052007-03-16 16:20:31 -0400454 ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
455 sizeof(extent_item));
Chris Mason037e6392007-03-07 11:50:24 -0500456
Chris Masone089f052007-03-16 16:20:31 -0400457 finish_current_insert(trans, extent_root);
Chris Masone20d96d2007-03-22 12:13:20 -0400458 pending_ret = del_pending_extents(trans, extent_root);
Chris Mason037e6392007-03-07 11:50:24 -0500459 if (ret)
460 return ret;
461 if (pending_ret)
462 return pending_ret;
463 return 0;
Chris Masonfec577f2007-02-26 10:40:21 -0500464}
465
466/*
467 * helper function to allocate a block for a given tree
468 * returns the tree buffer or NULL.
469 */
Chris Masone20d96d2007-03-22 12:13:20 -0400470struct buffer_head *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
Chris Masone089f052007-03-16 16:20:31 -0400471 struct btrfs_root *root)
Chris Masonfec577f2007-02-26 10:40:21 -0500472{
Chris Masone2fa7222007-03-12 16:22:34 -0400473 struct btrfs_key ins;
Chris Masonfec577f2007-02-26 10:40:21 -0500474 int ret;
Chris Masone20d96d2007-03-22 12:13:20 -0400475 struct buffer_head *buf;
Chris Masonfec577f2007-02-26 10:40:21 -0500476
Chris Masondee26a92007-03-26 16:00:06 -0400477 ret = btrfs_alloc_extent(trans, root, 1, 0, (unsigned long)-1,
Chris Masone20d96d2007-03-22 12:13:20 -0400478 btrfs_header_parentid(btrfs_buffer_header(root->node)), &ins);
Chris Masonfec577f2007-02-26 10:40:21 -0500479 if (ret) {
480 BUG();
481 return NULL;
482 }
Chris Masond98237b2007-03-28 13:57:48 -0400483 buf = btrfs_find_create_tree_block(root, ins.objectid);
Chris Masondf2ce342007-03-23 11:00:45 -0400484 set_buffer_uptodate(buf);
Chris Masonfec577f2007-02-26 10:40:21 -0500485 return buf;
486}
Chris Masona28ec192007-03-06 20:08:01 -0500487
Chris Mason6407bf62007-03-27 06:33:00 -0400488static int drop_leaf_ref(struct btrfs_trans_handle *trans,
489 struct btrfs_root *root, struct buffer_head *cur)
490{
491 struct btrfs_disk_key *key;
492 struct btrfs_leaf *leaf;
493 struct btrfs_file_extent_item *fi;
494 int i;
495 int nritems;
496 int ret;
497
498 BUG_ON(!btrfs_is_leaf(btrfs_buffer_node(cur)));
499 leaf = btrfs_buffer_leaf(cur);
500 nritems = btrfs_header_nritems(&leaf->header);
501 for (i = 0; i < nritems; i++) {
502 key = &leaf->items[i].key;
503 if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY)
504 continue;
505 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
506 /*
507 * FIXME make sure to insert a trans record that
508 * repeats the snapshot del on crash
509 */
510 ret = btrfs_free_extent(trans, root,
511 btrfs_file_extent_disk_blocknr(fi),
512 btrfs_file_extent_disk_num_blocks(fi),
513 0);
514 BUG_ON(ret);
515 }
516 return 0;
517}
518
Chris Mason9aca1d52007-03-13 11:09:37 -0400519/*
520 * helper function for drop_snapshot, this walks down the tree dropping ref
521 * counts as it goes.
522 */
Chris Masone089f052007-03-16 16:20:31 -0400523static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
524 *root, struct btrfs_path *path, int *level)
Chris Mason20524f02007-03-10 06:35:47 -0500525{
Chris Masone20d96d2007-03-22 12:13:20 -0400526 struct buffer_head *next;
527 struct buffer_head *cur;
Chris Mason20524f02007-03-10 06:35:47 -0500528 u64 blocknr;
529 int ret;
530 u32 refs;
531
Chris Masone20d96d2007-03-22 12:13:20 -0400532 ret = lookup_block_ref(trans, root, path->nodes[*level]->b_blocknr,
Chris Mason6407bf62007-03-27 06:33:00 -0400533 1, &refs);
Chris Mason20524f02007-03-10 06:35:47 -0500534 BUG_ON(ret);
535 if (refs > 1)
536 goto out;
Chris Mason9aca1d52007-03-13 11:09:37 -0400537 /*
538 * walk down to the last node level and free all the leaves
539 */
Chris Mason6407bf62007-03-27 06:33:00 -0400540 while(*level >= 0) {
Chris Mason20524f02007-03-10 06:35:47 -0500541 cur = path->nodes[*level];
Chris Mason7518a232007-03-12 12:01:18 -0400542 if (path->slots[*level] >=
Chris Masone20d96d2007-03-22 12:13:20 -0400543 btrfs_header_nritems(btrfs_buffer_header(cur)))
Chris Mason20524f02007-03-10 06:35:47 -0500544 break;
Chris Mason6407bf62007-03-27 06:33:00 -0400545 if (*level == 0) {
546 ret = drop_leaf_ref(trans, root, cur);
547 BUG_ON(ret);
548 break;
549 }
Chris Masone20d96d2007-03-22 12:13:20 -0400550 blocknr = btrfs_node_blockptr(btrfs_buffer_node(cur),
551 path->slots[*level]);
Chris Mason6407bf62007-03-27 06:33:00 -0400552 ret = lookup_block_ref(trans, root, blocknr, 1, &refs);
553 BUG_ON(ret);
554 if (refs != 1) {
Chris Mason20524f02007-03-10 06:35:47 -0500555 path->slots[*level]++;
Chris Masone089f052007-03-16 16:20:31 -0400556 ret = btrfs_free_extent(trans, root, blocknr, 1, 1);
Chris Mason20524f02007-03-10 06:35:47 -0500557 BUG_ON(ret);
558 continue;
559 }
Chris Mason20524f02007-03-10 06:35:47 -0500560 next = read_tree_block(root, blocknr);
Chris Mason83e15a22007-03-12 09:03:27 -0400561 if (path->nodes[*level-1])
Chris Mason234b63a2007-03-13 10:46:10 -0400562 btrfs_block_release(root, path->nodes[*level-1]);
Chris Mason20524f02007-03-10 06:35:47 -0500563 path->nodes[*level-1] = next;
Chris Masone20d96d2007-03-22 12:13:20 -0400564 *level = btrfs_header_level(btrfs_buffer_header(next));
Chris Mason20524f02007-03-10 06:35:47 -0500565 path->slots[*level] = 0;
566 }
567out:
Chris Mason6407bf62007-03-27 06:33:00 -0400568 ret = btrfs_free_extent(trans, root,
569 path->nodes[*level]->b_blocknr, 1, 1);
Chris Mason234b63a2007-03-13 10:46:10 -0400570 btrfs_block_release(root, path->nodes[*level]);
Chris Mason20524f02007-03-10 06:35:47 -0500571 path->nodes[*level] = NULL;
572 *level += 1;
573 BUG_ON(ret);
574 return 0;
575}
576
Chris Mason9aca1d52007-03-13 11:09:37 -0400577/*
578 * helper for dropping snapshots. This walks back up the tree in the path
579 * to find the first node higher up where we haven't yet gone through
580 * all the slots
581 */
Chris Masone089f052007-03-16 16:20:31 -0400582static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root
583 *root, struct btrfs_path *path, int *level)
Chris Mason20524f02007-03-10 06:35:47 -0500584{
585 int i;
586 int slot;
587 int ret;
Chris Mason234b63a2007-03-13 10:46:10 -0400588 for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
Chris Mason20524f02007-03-10 06:35:47 -0500589 slot = path->slots[i];
Chris Masone20d96d2007-03-22 12:13:20 -0400590 if (slot < btrfs_header_nritems(
591 btrfs_buffer_header(path->nodes[i])) - 1) {
Chris Mason20524f02007-03-10 06:35:47 -0500592 path->slots[i]++;
593 *level = i;
594 return 0;
595 } else {
Chris Masone089f052007-03-16 16:20:31 -0400596 ret = btrfs_free_extent(trans, root,
Chris Masone20d96d2007-03-22 12:13:20 -0400597 path->nodes[*level]->b_blocknr,
Chris Masone089f052007-03-16 16:20:31 -0400598 1, 1);
Chris Mason6407bf62007-03-27 06:33:00 -0400599 BUG_ON(ret);
Chris Mason234b63a2007-03-13 10:46:10 -0400600 btrfs_block_release(root, path->nodes[*level]);
Chris Mason83e15a22007-03-12 09:03:27 -0400601 path->nodes[*level] = NULL;
Chris Mason20524f02007-03-10 06:35:47 -0500602 *level = i + 1;
Chris Mason20524f02007-03-10 06:35:47 -0500603 }
604 }
605 return 1;
606}
607
Chris Mason9aca1d52007-03-13 11:09:37 -0400608/*
609 * drop the reference count on the tree rooted at 'snap'. This traverses
610 * the tree freeing any blocks that have a ref count of zero after being
611 * decremented.
612 */
Chris Masone089f052007-03-16 16:20:31 -0400613int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
Chris Masone20d96d2007-03-22 12:13:20 -0400614 *root, struct buffer_head *snap)
Chris Mason20524f02007-03-10 06:35:47 -0500615{
Chris Mason3768f362007-03-13 16:47:54 -0400616 int ret = 0;
Chris Mason9aca1d52007-03-13 11:09:37 -0400617 int wret;
Chris Mason20524f02007-03-10 06:35:47 -0500618 int level;
Chris Mason234b63a2007-03-13 10:46:10 -0400619 struct btrfs_path path;
Chris Mason20524f02007-03-10 06:35:47 -0500620 int i;
621 int orig_level;
622
Chris Mason234b63a2007-03-13 10:46:10 -0400623 btrfs_init_path(&path);
Chris Mason20524f02007-03-10 06:35:47 -0500624
Chris Masone20d96d2007-03-22 12:13:20 -0400625 level = btrfs_header_level(btrfs_buffer_header(snap));
Chris Mason20524f02007-03-10 06:35:47 -0500626 orig_level = level;
627 path.nodes[level] = snap;
628 path.slots[level] = 0;
629 while(1) {
Chris Masone089f052007-03-16 16:20:31 -0400630 wret = walk_down_tree(trans, root, &path, &level);
Chris Mason9aca1d52007-03-13 11:09:37 -0400631 if (wret > 0)
Chris Mason20524f02007-03-10 06:35:47 -0500632 break;
Chris Mason9aca1d52007-03-13 11:09:37 -0400633 if (wret < 0)
634 ret = wret;
635
Chris Masone089f052007-03-16 16:20:31 -0400636 wret = walk_up_tree(trans, root, &path, &level);
Chris Mason9aca1d52007-03-13 11:09:37 -0400637 if (wret > 0)
Chris Mason20524f02007-03-10 06:35:47 -0500638 break;
Chris Mason9aca1d52007-03-13 11:09:37 -0400639 if (wret < 0)
640 ret = wret;
Chris Mason20524f02007-03-10 06:35:47 -0500641 }
Chris Mason83e15a22007-03-12 09:03:27 -0400642 for (i = 0; i <= orig_level; i++) {
643 if (path.nodes[i]) {
Chris Mason234b63a2007-03-13 10:46:10 -0400644 btrfs_block_release(root, path.nodes[i]);
Chris Mason83e15a22007-03-12 09:03:27 -0400645 }
Chris Mason20524f02007-03-10 06:35:47 -0500646 }
Chris Mason9aca1d52007-03-13 11:09:37 -0400647 return ret;
Chris Mason20524f02007-03-10 06:35:47 -0500648}