blob: 688aa861a9281c09ed807d8845e18f773b7bc759 [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 Mason5caf2a02007-04-02 11:20:42 -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 Mason5caf2a02007-04-02 11:20:42 -040028 path = btrfs_alloc_path();
29 BUG_ON(!path);
30 btrfs_init_path(path);
Chris Mason02217ed2007-03-02 16:08:05 -050031 key.objectid = blocknr;
32 key.flags = 0;
Chris Mason62e27492007-03-15 12:56:47 -040033 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
Chris Mason6407bf62007-03-27 06:33:00 -040034 key.offset = num_blocks;
Chris Mason5caf2a02007-04-02 11:20:42 -040035 ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
Chris Mason9f5fae22007-03-20 14:38:32 -040036 0, 1);
Chris Masona28ec192007-03-06 20:08:01 -050037 if (ret != 0)
38 BUG();
Chris Mason02217ed2007-03-02 16:08:05 -050039 BUG_ON(ret != 0);
Chris Mason5caf2a02007-04-02 11:20:42 -040040 l = btrfs_buffer_leaf(path->nodes[0]);
41 item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
Chris Masoncf27e1e2007-03-13 09:49:06 -040042 refs = btrfs_extent_refs(item);
43 btrfs_set_extent_refs(item, refs + 1);
Chris Mason5caf2a02007-04-02 11:20:42 -040044 btrfs_mark_buffer_dirty(path->nodes[0]);
Chris Masona28ec192007-03-06 20:08:01 -050045
Chris Mason5caf2a02007-04-02 11:20:42 -040046 btrfs_release_path(root->fs_info->extent_root, path);
47 btrfs_free_path(path);
Chris Mason9f5fae22007-03-20 14:38:32 -040048 finish_current_insert(trans, root->fs_info->extent_root);
Chris Masone20d96d2007-03-22 12:13:20 -040049 del_pending_extents(trans, root->fs_info->extent_root);
Chris Mason02217ed2007-03-02 16:08:05 -050050 return 0;
51}
52
Chris Masone089f052007-03-16 16:20:31 -040053static int lookup_block_ref(struct btrfs_trans_handle *trans, struct btrfs_root
Chris Mason6407bf62007-03-27 06:33:00 -040054 *root, u64 blocknr, u64 num_blocks, u32 *refs)
Chris Masona28ec192007-03-06 20:08:01 -050055{
Chris Mason5caf2a02007-04-02 11:20:42 -040056 struct btrfs_path *path;
Chris Masona28ec192007-03-06 20:08:01 -050057 int ret;
Chris Masone2fa7222007-03-12 16:22:34 -040058 struct btrfs_key key;
Chris Mason234b63a2007-03-13 10:46:10 -040059 struct btrfs_leaf *l;
60 struct btrfs_extent_item *item;
Chris Mason5caf2a02007-04-02 11:20:42 -040061
62 path = btrfs_alloc_path();
63 btrfs_init_path(path);
Chris Masona28ec192007-03-06 20:08:01 -050064 key.objectid = blocknr;
Chris Mason6407bf62007-03-27 06:33:00 -040065 key.offset = num_blocks;
Chris Mason62e27492007-03-15 12:56:47 -040066 key.flags = 0;
67 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
Chris Mason5caf2a02007-04-02 11:20:42 -040068 ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
Chris Mason9f5fae22007-03-20 14:38:32 -040069 0, 0);
Chris Masona28ec192007-03-06 20:08:01 -050070 if (ret != 0)
71 BUG();
Chris Mason5caf2a02007-04-02 11:20:42 -040072 l = btrfs_buffer_leaf(path->nodes[0]);
73 item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
Chris Masoncf27e1e2007-03-13 09:49:06 -040074 *refs = btrfs_extent_refs(item);
Chris Mason5caf2a02007-04-02 11:20:42 -040075 btrfs_release_path(root->fs_info->extent_root, path);
76 btrfs_free_path(path);
Chris Masona28ec192007-03-06 20:08:01 -050077 return 0;
78}
79
Chris Masone089f052007-03-16 16:20:31 -040080int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
Chris Masone20d96d2007-03-22 12:13:20 -040081 struct buffer_head *buf)
Chris Mason02217ed2007-03-02 16:08:05 -050082{
83 u64 blocknr;
Chris Masone20d96d2007-03-22 12:13:20 -040084 struct btrfs_node *buf_node;
Chris Mason6407bf62007-03-27 06:33:00 -040085 struct btrfs_leaf *buf_leaf;
86 struct btrfs_disk_key *key;
87 struct btrfs_file_extent_item *fi;
Chris Mason02217ed2007-03-02 16:08:05 -050088 int i;
Chris Mason6407bf62007-03-27 06:33:00 -040089 int leaf;
90 int ret;
Chris Masona28ec192007-03-06 20:08:01 -050091
Chris Mason3768f362007-03-13 16:47:54 -040092 if (!root->ref_cows)
Chris Masona28ec192007-03-06 20:08:01 -050093 return 0;
Chris Masone20d96d2007-03-22 12:13:20 -040094 buf_node = btrfs_buffer_node(buf);
Chris Mason6407bf62007-03-27 06:33:00 -040095 leaf = btrfs_is_leaf(buf_node);
96 buf_leaf = btrfs_buffer_leaf(buf);
Chris Masone20d96d2007-03-22 12:13:20 -040097 for (i = 0; i < btrfs_header_nritems(&buf_node->header); i++) {
Chris Mason6407bf62007-03-27 06:33:00 -040098 if (leaf) {
99 key = &buf_leaf->items[i].key;
100 if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY)
101 continue;
102 fi = btrfs_item_ptr(buf_leaf, i,
103 struct btrfs_file_extent_item);
104 ret = inc_block_ref(trans, root,
105 btrfs_file_extent_disk_blocknr(fi),
106 btrfs_file_extent_disk_num_blocks(fi));
107 BUG_ON(ret);
108 } else {
109 blocknr = btrfs_node_blockptr(buf_node, i);
110 ret = inc_block_ref(trans, root, blocknr, 1);
111 BUG_ON(ret);
112 }
Chris Mason02217ed2007-03-02 16:08:05 -0500113 }
114 return 0;
115}
116
Chris Masone089f052007-03-16 16:20:31 -0400117int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans, struct
118 btrfs_root *root)
Chris Masona28ec192007-03-06 20:08:01 -0500119{
Chris Mason8ef97622007-03-26 10:15:30 -0400120 unsigned long gang[8];
Chris Mason88fd1462007-03-16 08:56:18 -0400121 u64 first = 0;
Chris Masona28ec192007-03-06 20:08:01 -0500122 int ret;
123 int i;
Chris Mason8ef97622007-03-26 10:15:30 -0400124 struct radix_tree_root *pinned_radix = &root->fs_info->pinned_radix;
Chris Masona28ec192007-03-06 20:08:01 -0500125
126 while(1) {
Chris Mason8ef97622007-03-26 10:15:30 -0400127 ret = find_first_radix_bit(pinned_radix, gang,
128 ARRAY_SIZE(gang));
Chris Masona28ec192007-03-06 20:08:01 -0500129 if (!ret)
130 break;
Chris Mason88fd1462007-03-16 08:56:18 -0400131 if (!first)
Chris Mason8ef97622007-03-26 10:15:30 -0400132 first = gang[0];
Chris Mason0579da42007-03-07 16:15:30 -0500133 for (i = 0; i < ret; i++) {
Chris Mason8ef97622007-03-26 10:15:30 -0400134 clear_radix_bit(pinned_radix, gang[i]);
Chris Mason0579da42007-03-07 16:15:30 -0500135 }
Chris Masona28ec192007-03-06 20:08:01 -0500136 }
Chris Masond5719762007-03-23 10:01:08 -0400137 if (root->fs_info->last_insert.objectid > first)
138 root->fs_info->last_insert.objectid = first;
Chris Mason9f5fae22007-03-20 14:38:32 -0400139 root->fs_info->last_insert.offset = 0;
Chris Masona28ec192007-03-06 20:08:01 -0500140 return 0;
141}
142
Chris Masone089f052007-03-16 16:20:31 -0400143static int finish_current_insert(struct btrfs_trans_handle *trans, struct
144 btrfs_root *extent_root)
Chris Mason037e6392007-03-07 11:50:24 -0500145{
Chris Masone2fa7222007-03-12 16:22:34 -0400146 struct btrfs_key ins;
Chris Mason234b63a2007-03-13 10:46:10 -0400147 struct btrfs_extent_item extent_item;
Chris Mason037e6392007-03-07 11:50:24 -0500148 int i;
149 int ret;
Chris Mason1261ec42007-03-20 20:35:03 -0400150 u64 super_blocks_used;
151 struct btrfs_fs_info *info = extent_root->fs_info;
Chris Mason037e6392007-03-07 11:50:24 -0500152
Chris Masoncf27e1e2007-03-13 09:49:06 -0400153 btrfs_set_extent_refs(&extent_item, 1);
154 btrfs_set_extent_owner(&extent_item,
Chris Masone20d96d2007-03-22 12:13:20 -0400155 btrfs_header_parentid(btrfs_buffer_header(extent_root->node)));
Chris Mason037e6392007-03-07 11:50:24 -0500156 ins.offset = 1;
157 ins.flags = 0;
Chris Mason62e27492007-03-15 12:56:47 -0400158 btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
Chris Mason037e6392007-03-07 11:50:24 -0500159
Chris Mason9f5fae22007-03-20 14:38:32 -0400160 for (i = 0; i < extent_root->fs_info->current_insert.flags; i++) {
161 ins.objectid = extent_root->fs_info->current_insert.objectid +
162 i;
Chris Mason1261ec42007-03-20 20:35:03 -0400163 super_blocks_used = btrfs_super_blocks_used(info->disk_super);
164 btrfs_set_super_blocks_used(info->disk_super,
165 super_blocks_used + 1);
Chris Masone089f052007-03-16 16:20:31 -0400166 ret = btrfs_insert_item(trans, extent_root, &ins, &extent_item,
167 sizeof(extent_item));
Chris Mason037e6392007-03-07 11:50:24 -0500168 BUG_ON(ret);
169 }
Chris Mason9f5fae22007-03-20 14:38:32 -0400170 extent_root->fs_info->current_insert.offset = 0;
Chris Mason037e6392007-03-07 11:50:24 -0500171 return 0;
172}
173
Chris Mason8ef97622007-03-26 10:15:30 -0400174static int pin_down_block(struct btrfs_root *root, u64 blocknr, int pending)
Chris Masone20d96d2007-03-22 12:13:20 -0400175{
176 int err;
Chris Mason78fae272007-03-25 11:35:08 -0400177 struct btrfs_header *header;
Chris Mason8ef97622007-03-26 10:15:30 -0400178 struct buffer_head *bh;
Chris Mason78fae272007-03-25 11:35:08 -0400179
Chris Masonf4b9aa82007-03-27 11:05:53 -0400180 if (!pending) {
Chris Masond98237b2007-03-28 13:57:48 -0400181 bh = btrfs_find_tree_block(root, blocknr);
Chris Mason2c90e5d2007-04-02 10:50:19 -0400182 if (bh) {
183 if (buffer_uptodate(bh)) {
184 u64 transid =
185 root->fs_info->running_transaction->transid;
186 header = btrfs_buffer_header(bh);
187 if (btrfs_header_generation(header) ==
188 transid) {
189 btrfs_block_release(root, bh);
190 return 0;
191 }
Chris Masonf4b9aa82007-03-27 11:05:53 -0400192 }
Chris Masond6025572007-03-30 14:27:56 -0400193 btrfs_block_release(root, bh);
Chris Mason8ef97622007-03-26 10:15:30 -0400194 }
Chris Mason8ef97622007-03-26 10:15:30 -0400195 err = set_radix_bit(&root->fs_info->pinned_radix, blocknr);
Chris Masonf4b9aa82007-03-27 11:05:53 -0400196 } else {
197 err = set_radix_bit(&root->fs_info->pending_del_radix, blocknr);
198 }
Chris Mason8ef97622007-03-26 10:15:30 -0400199 BUG_ON(err);
Chris Masone20d96d2007-03-22 12:13:20 -0400200 return 0;
201}
202
Chris Masona28ec192007-03-06 20:08:01 -0500203/*
204 * remove an extent from the root, returns 0 on success
205 */
Chris Masone089f052007-03-16 16:20:31 -0400206static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
Chris Mason78fae272007-03-25 11:35:08 -0400207 *root, u64 blocknr, u64 num_blocks, int pin)
Chris Masona28ec192007-03-06 20:08:01 -0500208{
Chris Mason5caf2a02007-04-02 11:20:42 -0400209 struct btrfs_path *path;
Chris Masone2fa7222007-03-12 16:22:34 -0400210 struct btrfs_key key;
Chris Mason1261ec42007-03-20 20:35:03 -0400211 struct btrfs_fs_info *info = root->fs_info;
212 struct btrfs_root *extent_root = info->extent_root;
Chris Masona28ec192007-03-06 20:08:01 -0500213 int ret;
Chris Mason234b63a2007-03-13 10:46:10 -0400214 struct btrfs_extent_item *ei;
Chris Masone2fa7222007-03-12 16:22:34 -0400215 struct btrfs_key ins;
Chris Masoncf27e1e2007-03-13 09:49:06 -0400216 u32 refs;
Chris Mason037e6392007-03-07 11:50:24 -0500217
Chris Masona28ec192007-03-06 20:08:01 -0500218 key.objectid = blocknr;
219 key.flags = 0;
Chris Mason62e27492007-03-15 12:56:47 -0400220 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
Chris Masona28ec192007-03-06 20:08:01 -0500221 key.offset = num_blocks;
222
Chris Masone089f052007-03-16 16:20:31 -0400223 find_free_extent(trans, root, 0, 0, (u64)-1, &ins);
Chris Mason5caf2a02007-04-02 11:20:42 -0400224 path = btrfs_alloc_path();
225 BUG_ON(!path);
226 btrfs_init_path(path);
227 ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
Chris Masona28ec192007-03-06 20:08:01 -0500228 if (ret) {
Chris Mason2e635a22007-03-21 11:12:56 -0400229 printk("failed to find %Lu\n", key.objectid);
Chris Mason234b63a2007-03-13 10:46:10 -0400230 btrfs_print_tree(extent_root, extent_root->node);
Chris Mason2e635a22007-03-21 11:12:56 -0400231 printk("failed to find %Lu\n", key.objectid);
Chris Masona28ec192007-03-06 20:08:01 -0500232 BUG();
233 }
Chris Mason5caf2a02007-04-02 11:20:42 -0400234 ei = btrfs_item_ptr(btrfs_buffer_leaf(path->nodes[0]), path->slots[0],
Chris Mason123abc82007-03-14 14:14:43 -0400235 struct btrfs_extent_item);
Chris Masona28ec192007-03-06 20:08:01 -0500236 BUG_ON(ei->refs == 0);
Chris Masoncf27e1e2007-03-13 09:49:06 -0400237 refs = btrfs_extent_refs(ei) - 1;
238 btrfs_set_extent_refs(ei, refs);
Chris Mason5caf2a02007-04-02 11:20:42 -0400239 btrfs_mark_buffer_dirty(path->nodes[0]);
Chris Masoncf27e1e2007-03-13 09:49:06 -0400240 if (refs == 0) {
Chris Mason1261ec42007-03-20 20:35:03 -0400241 u64 super_blocks_used;
Chris Mason78fae272007-03-25 11:35:08 -0400242
243 if (pin) {
Chris Mason8ef97622007-03-26 10:15:30 -0400244 ret = pin_down_block(root, blocknr, 0);
Chris Mason78fae272007-03-25 11:35:08 -0400245 BUG_ON(ret);
246 }
247
Chris Mason1261ec42007-03-20 20:35:03 -0400248 super_blocks_used = btrfs_super_blocks_used(info->disk_super);
249 btrfs_set_super_blocks_used(info->disk_super,
250 super_blocks_used - num_blocks);
Chris Mason5caf2a02007-04-02 11:20:42 -0400251 ret = btrfs_del_item(trans, extent_root, path);
Chris Masona28ec192007-03-06 20:08:01 -0500252 if (ret)
253 BUG();
254 }
Chris Mason5caf2a02007-04-02 11:20:42 -0400255 btrfs_release_path(extent_root, path);
256 btrfs_free_path(path);
Chris Masone089f052007-03-16 16:20:31 -0400257 finish_current_insert(trans, extent_root);
Chris Masona28ec192007-03-06 20:08:01 -0500258 return ret;
259}
260
261/*
Chris Masonfec577f2007-02-26 10:40:21 -0500262 * find all the blocks marked as pending in the radix tree and remove
263 * them from the extent map
264 */
Chris Masone089f052007-03-16 16:20:31 -0400265static int del_pending_extents(struct btrfs_trans_handle *trans, struct
266 btrfs_root *extent_root)
Chris Masonfec577f2007-02-26 10:40:21 -0500267{
268 int ret;
Chris Masone20d96d2007-03-22 12:13:20 -0400269 int wret;
270 int err = 0;
Chris Mason8ef97622007-03-26 10:15:30 -0400271 unsigned long gang[4];
Chris Masonfec577f2007-02-26 10:40:21 -0500272 int i;
Chris Mason8ef97622007-03-26 10:15:30 -0400273 struct radix_tree_root *pending_radix;
274 struct radix_tree_root *pinned_radix;
275
276 pending_radix = &extent_root->fs_info->pending_del_radix;
277 pinned_radix = &extent_root->fs_info->pinned_radix;
Chris Masonfec577f2007-02-26 10:40:21 -0500278
279 while(1) {
Chris Mason8ef97622007-03-26 10:15:30 -0400280 ret = find_first_radix_bit(pending_radix, gang,
281 ARRAY_SIZE(gang));
Chris Masonfec577f2007-02-26 10:40:21 -0500282 if (!ret)
283 break;
284 for (i = 0; i < ret; i++) {
Chris Mason8ef97622007-03-26 10:15:30 -0400285 wret = set_radix_bit(pinned_radix, gang[i]);
286 BUG_ON(wret);
287 wret = clear_radix_bit(pending_radix, gang[i]);
288 BUG_ON(wret);
Chris Masond5719762007-03-23 10:01:08 -0400289 wret = __free_extent(trans, extent_root,
Chris Mason8ef97622007-03-26 10:15:30 -0400290 gang[i], 1, 0);
Chris Masone20d96d2007-03-22 12:13:20 -0400291 if (wret)
292 err = wret;
Chris Masonfec577f2007-02-26 10:40:21 -0500293 }
294 }
Chris Masone20d96d2007-03-22 12:13:20 -0400295 return err;
Chris Masonfec577f2007-02-26 10:40:21 -0500296}
297
298/*
299 * remove an extent from the root, returns 0 on success
300 */
Chris Masone089f052007-03-16 16:20:31 -0400301int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
302 *root, u64 blocknr, u64 num_blocks, int pin)
Chris Masonfec577f2007-02-26 10:40:21 -0500303{
Chris Mason9f5fae22007-03-20 14:38:32 -0400304 struct btrfs_root *extent_root = root->fs_info->extent_root;
Chris Masonfec577f2007-02-26 10:40:21 -0500305 int pending_ret;
306 int ret;
Chris Masona28ec192007-03-06 20:08:01 -0500307
308 if (root == extent_root) {
Chris Mason8ef97622007-03-26 10:15:30 -0400309 pin_down_block(root, blocknr, 1);
Chris Masona28ec192007-03-06 20:08:01 -0500310 return 0;
311 }
Chris Mason78fae272007-03-25 11:35:08 -0400312 ret = __free_extent(trans, root, blocknr, num_blocks, pin);
Chris Masone20d96d2007-03-22 12:13:20 -0400313 pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
Chris Masonfec577f2007-02-26 10:40:21 -0500314 return ret ? ret : pending_ret;
315}
316
317/*
318 * walks the btree of allocated extents and find a hole of a given size.
319 * The key ins is changed to record the hole:
320 * ins->objectid == block start
Chris Mason62e27492007-03-15 12:56:47 -0400321 * ins->flags = BTRFS_EXTENT_ITEM_KEY
Chris Masonfec577f2007-02-26 10:40:21 -0500322 * ins->offset == number of blocks
323 * Any available blocks before search_start are skipped.
324 */
Chris Masone089f052007-03-16 16:20:31 -0400325static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
326 *orig_root, u64 num_blocks, u64 search_start, u64
327 search_end, struct btrfs_key *ins)
Chris Masonfec577f2007-02-26 10:40:21 -0500328{
Chris Mason5caf2a02007-04-02 11:20:42 -0400329 struct btrfs_path *path;
Chris Masone2fa7222007-03-12 16:22:34 -0400330 struct btrfs_key key;
Chris Masonfec577f2007-02-26 10:40:21 -0500331 int ret;
332 u64 hole_size = 0;
333 int slot = 0;
Chris Masone20d96d2007-03-22 12:13:20 -0400334 u64 last_block = 0;
Chris Mason037e6392007-03-07 11:50:24 -0500335 u64 test_block;
Chris Masonfec577f2007-02-26 10:40:21 -0500336 int start_found;
Chris Mason234b63a2007-03-13 10:46:10 -0400337 struct btrfs_leaf *l;
Chris Mason9f5fae22007-03-20 14:38:32 -0400338 struct btrfs_root * root = orig_root->fs_info->extent_root;
Chris Mason0579da42007-03-07 16:15:30 -0500339 int total_needed = num_blocks;
Chris Masone20d96d2007-03-22 12:13:20 -0400340 int level;
Chris Masonfec577f2007-02-26 10:40:21 -0500341
Chris Masonb1a4d962007-04-04 15:27:52 -0400342 path = btrfs_alloc_path();
343 ins->flags = 0;
344 btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
345
Chris Masone20d96d2007-03-22 12:13:20 -0400346 level = btrfs_header_level(btrfs_buffer_header(root->node));
347 total_needed += (level + 1) * 3;
Chris Masonb1a4d962007-04-04 15:27:52 -0400348 if (root->fs_info->last_insert.objectid == 0 && search_end == (u64)-1) {
349 struct btrfs_disk_key *last_key;
350 btrfs_init_path(path);
351 ins->objectid = (u64)-1;
352 ins->offset = (u64)-1;
353 ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
354 if (ret < 0)
355 goto error;
356 BUG_ON(ret == 0);
357 if (path->slots[0] > 0)
358 path->slots[0]--;
359 l = btrfs_buffer_leaf(path->nodes[0]);
360 last_key = &l->items[path->slots[0]].key;
361 search_start = btrfs_disk_key_objectid(last_key);
362 }
Chris Mason9f5fae22007-03-20 14:38:32 -0400363 if (root->fs_info->last_insert.objectid > search_start)
364 search_start = root->fs_info->last_insert.objectid;
Chris Mason62e27492007-03-15 12:56:47 -0400365
Chris Mason5caf2a02007-04-02 11:20:42 -0400366 path = btrfs_alloc_path();
Chris Mason62e27492007-03-15 12:56:47 -0400367
Chris Masonfec577f2007-02-26 10:40:21 -0500368check_failed:
Chris Mason5caf2a02007-04-02 11:20:42 -0400369 btrfs_init_path(path);
Chris Masonfec577f2007-02-26 10:40:21 -0500370 ins->objectid = search_start;
371 ins->offset = 0;
Chris Masonfec577f2007-02-26 10:40:21 -0500372 start_found = 0;
Chris Mason5caf2a02007-04-02 11:20:42 -0400373 ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
Chris Mason0f70abe2007-02-28 16:46:22 -0500374 if (ret < 0)
375 goto error;
Chris Masonaa5d6be2007-02-28 16:35:06 -0500376
Chris Mason5caf2a02007-04-02 11:20:42 -0400377 if (path->slots[0] > 0)
378 path->slots[0]--;
Chris Mason0579da42007-03-07 16:15:30 -0500379
Chris Masonfec577f2007-02-26 10:40:21 -0500380 while (1) {
Chris Mason5caf2a02007-04-02 11:20:42 -0400381 l = btrfs_buffer_leaf(path->nodes[0]);
382 slot = path->slots[0];
Chris Mason7518a232007-03-12 12:01:18 -0400383 if (slot >= btrfs_header_nritems(&l->header)) {
Chris Mason5caf2a02007-04-02 11:20:42 -0400384 ret = btrfs_next_leaf(root, path);
Chris Masonfec577f2007-02-26 10:40:21 -0500385 if (ret == 0)
386 continue;
Chris Mason0f70abe2007-02-28 16:46:22 -0500387 if (ret < 0)
388 goto error;
Chris Masonfec577f2007-02-26 10:40:21 -0500389 if (!start_found) {
390 ins->objectid = search_start;
Chris Mason037e6392007-03-07 11:50:24 -0500391 ins->offset = (u64)-1;
Chris Masonfec577f2007-02-26 10:40:21 -0500392 start_found = 1;
393 goto check_pending;
394 }
395 ins->objectid = last_block > search_start ?
396 last_block : search_start;
Chris Mason037e6392007-03-07 11:50:24 -0500397 ins->offset = (u64)-1;
Chris Masonfec577f2007-02-26 10:40:21 -0500398 goto check_pending;
399 }
Chris Masone2fa7222007-03-12 16:22:34 -0400400 btrfs_disk_key_to_cpu(&key, &l->items[slot].key);
401 if (key.objectid >= search_start) {
Chris Masonfec577f2007-02-26 10:40:21 -0500402 if (start_found) {
Chris Mason0579da42007-03-07 16:15:30 -0500403 if (last_block < search_start)
404 last_block = search_start;
Chris Masone2fa7222007-03-12 16:22:34 -0400405 hole_size = key.objectid - last_block;
Chris Mason037e6392007-03-07 11:50:24 -0500406 if (hole_size > total_needed) {
Chris Masonfec577f2007-02-26 10:40:21 -0500407 ins->objectid = last_block;
Chris Mason037e6392007-03-07 11:50:24 -0500408 ins->offset = hole_size;
Chris Masonfec577f2007-02-26 10:40:21 -0500409 goto check_pending;
410 }
Chris Mason0579da42007-03-07 16:15:30 -0500411 }
Chris Masonfec577f2007-02-26 10:40:21 -0500412 }
Chris Mason0579da42007-03-07 16:15:30 -0500413 start_found = 1;
Chris Masone2fa7222007-03-12 16:22:34 -0400414 last_block = key.objectid + key.offset;
Chris Mason5caf2a02007-04-02 11:20:42 -0400415 path->slots[0]++;
Chris Masonfec577f2007-02-26 10:40:21 -0500416 }
417 // FIXME -ENOSPC
418check_pending:
419 /* we have to make sure we didn't find an extent that has already
420 * been allocated by the map tree or the original allocation
421 */
Chris Mason5caf2a02007-04-02 11:20:42 -0400422 btrfs_release_path(root, path);
Chris Masonfec577f2007-02-26 10:40:21 -0500423 BUG_ON(ins->objectid < search_start);
Chris Mason037e6392007-03-07 11:50:24 -0500424 for (test_block = ins->objectid;
425 test_block < ins->objectid + total_needed; test_block++) {
Chris Mason8ef97622007-03-26 10:15:30 -0400426 if (test_radix_bit(&root->fs_info->pinned_radix,
Chris Mason9f5fae22007-03-20 14:38:32 -0400427 test_block)) {
Chris Mason037e6392007-03-07 11:50:24 -0500428 search_start = test_block + 1;
Chris Masonfec577f2007-02-26 10:40:21 -0500429 goto check_failed;
430 }
431 }
Chris Mason9f5fae22007-03-20 14:38:32 -0400432 BUG_ON(root->fs_info->current_insert.offset);
433 root->fs_info->current_insert.offset = total_needed - num_blocks;
434 root->fs_info->current_insert.objectid = ins->objectid + num_blocks;
435 root->fs_info->current_insert.flags = 0;
436 root->fs_info->last_insert.objectid = ins->objectid;
Chris Mason037e6392007-03-07 11:50:24 -0500437 ins->offset = num_blocks;
Chris Mason5caf2a02007-04-02 11:20:42 -0400438 btrfs_free_path(path);
Chris Masonfec577f2007-02-26 10:40:21 -0500439 return 0;
Chris Mason0f70abe2007-02-28 16:46:22 -0500440error:
Chris Mason5caf2a02007-04-02 11:20:42 -0400441 btrfs_release_path(root, path);
442 btrfs_free_path(path);
Chris Mason0f70abe2007-02-28 16:46:22 -0500443 return ret;
Chris Masonfec577f2007-02-26 10:40:21 -0500444}
445
446/*
Chris Masonfec577f2007-02-26 10:40:21 -0500447 * finds a free extent and does all the dirty work required for allocation
448 * returns the key for the extent through ins, and a tree buffer for
449 * the first block of the extent through buf.
450 *
451 * returns 0 if everything worked, non-zero otherwise.
452 */
Chris Masondee26a92007-03-26 16:00:06 -0400453int btrfs_alloc_extent(struct btrfs_trans_handle *trans, struct btrfs_root
Chris Masone089f052007-03-16 16:20:31 -0400454 *root, u64 num_blocks, u64 search_start, u64
455 search_end, u64 owner, struct btrfs_key *ins)
Chris Masonfec577f2007-02-26 10:40:21 -0500456{
457 int ret;
458 int pending_ret;
Chris Mason1261ec42007-03-20 20:35:03 -0400459 u64 super_blocks_used;
460 struct btrfs_fs_info *info = root->fs_info;
461 struct btrfs_root *extent_root = info->extent_root;
Chris Mason234b63a2007-03-13 10:46:10 -0400462 struct btrfs_extent_item extent_item;
Chris Mason037e6392007-03-07 11:50:24 -0500463
Chris Masoncf27e1e2007-03-13 09:49:06 -0400464 btrfs_set_extent_refs(&extent_item, 1);
465 btrfs_set_extent_owner(&extent_item, owner);
Chris Masonfec577f2007-02-26 10:40:21 -0500466
Chris Mason037e6392007-03-07 11:50:24 -0500467 if (root == extent_root) {
Chris Mason9f5fae22007-03-20 14:38:32 -0400468 BUG_ON(extent_root->fs_info->current_insert.offset == 0);
Chris Mason037e6392007-03-07 11:50:24 -0500469 BUG_ON(num_blocks != 1);
Chris Mason9f5fae22007-03-20 14:38:32 -0400470 BUG_ON(extent_root->fs_info->current_insert.flags ==
471 extent_root->fs_info->current_insert.offset);
Chris Mason037e6392007-03-07 11:50:24 -0500472 ins->offset = 1;
Chris Mason9f5fae22007-03-20 14:38:32 -0400473 ins->objectid = extent_root->fs_info->current_insert.objectid +
474 extent_root->fs_info->current_insert.flags++;
Chris Masonfec577f2007-02-26 10:40:21 -0500475 return 0;
476 }
Chris Masone089f052007-03-16 16:20:31 -0400477 ret = find_free_extent(trans, root, num_blocks, search_start,
Chris Mason037e6392007-03-07 11:50:24 -0500478 search_end, ins);
479 if (ret)
480 return ret;
Chris Masonfec577f2007-02-26 10:40:21 -0500481
Chris Mason1261ec42007-03-20 20:35:03 -0400482 super_blocks_used = btrfs_super_blocks_used(info->disk_super);
483 btrfs_set_super_blocks_used(info->disk_super, super_blocks_used +
484 num_blocks);
Chris Masone089f052007-03-16 16:20:31 -0400485 ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
486 sizeof(extent_item));
Chris Mason037e6392007-03-07 11:50:24 -0500487
Chris Masone089f052007-03-16 16:20:31 -0400488 finish_current_insert(trans, extent_root);
Chris Masone20d96d2007-03-22 12:13:20 -0400489 pending_ret = del_pending_extents(trans, extent_root);
Chris Mason037e6392007-03-07 11:50:24 -0500490 if (ret)
491 return ret;
492 if (pending_ret)
493 return pending_ret;
494 return 0;
Chris Masonfec577f2007-02-26 10:40:21 -0500495}
496
497/*
498 * helper function to allocate a block for a given tree
499 * returns the tree buffer or NULL.
500 */
Chris Masone20d96d2007-03-22 12:13:20 -0400501struct buffer_head *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
Chris Masone089f052007-03-16 16:20:31 -0400502 struct btrfs_root *root)
Chris Masonfec577f2007-02-26 10:40:21 -0500503{
Chris Masone2fa7222007-03-12 16:22:34 -0400504 struct btrfs_key ins;
Chris Masonfec577f2007-02-26 10:40:21 -0500505 int ret;
Chris Masone20d96d2007-03-22 12:13:20 -0400506 struct buffer_head *buf;
Chris Masonfec577f2007-02-26 10:40:21 -0500507
Chris Masondee26a92007-03-26 16:00:06 -0400508 ret = btrfs_alloc_extent(trans, root, 1, 0, (unsigned long)-1,
Chris Masone20d96d2007-03-22 12:13:20 -0400509 btrfs_header_parentid(btrfs_buffer_header(root->node)), &ins);
Chris Masonfec577f2007-02-26 10:40:21 -0500510 if (ret) {
511 BUG();
512 return NULL;
513 }
Chris Masond98237b2007-03-28 13:57:48 -0400514 buf = btrfs_find_create_tree_block(root, ins.objectid);
Chris Masondf2ce342007-03-23 11:00:45 -0400515 set_buffer_uptodate(buf);
Chris Masonfec577f2007-02-26 10:40:21 -0500516 return buf;
517}
Chris Masona28ec192007-03-06 20:08:01 -0500518
Chris Mason6407bf62007-03-27 06:33:00 -0400519static int drop_leaf_ref(struct btrfs_trans_handle *trans,
520 struct btrfs_root *root, struct buffer_head *cur)
521{
522 struct btrfs_disk_key *key;
523 struct btrfs_leaf *leaf;
524 struct btrfs_file_extent_item *fi;
525 int i;
526 int nritems;
527 int ret;
528
529 BUG_ON(!btrfs_is_leaf(btrfs_buffer_node(cur)));
530 leaf = btrfs_buffer_leaf(cur);
531 nritems = btrfs_header_nritems(&leaf->header);
532 for (i = 0; i < nritems; i++) {
533 key = &leaf->items[i].key;
534 if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY)
535 continue;
536 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
537 /*
538 * FIXME make sure to insert a trans record that
539 * repeats the snapshot del on crash
540 */
541 ret = btrfs_free_extent(trans, root,
542 btrfs_file_extent_disk_blocknr(fi),
543 btrfs_file_extent_disk_num_blocks(fi),
544 0);
545 BUG_ON(ret);
546 }
547 return 0;
548}
549
Chris Mason9aca1d52007-03-13 11:09:37 -0400550/*
551 * helper function for drop_snapshot, this walks down the tree dropping ref
552 * counts as it goes.
553 */
Chris Masone089f052007-03-16 16:20:31 -0400554static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
555 *root, struct btrfs_path *path, int *level)
Chris Mason20524f02007-03-10 06:35:47 -0500556{
Chris Masone20d96d2007-03-22 12:13:20 -0400557 struct buffer_head *next;
558 struct buffer_head *cur;
Chris Mason20524f02007-03-10 06:35:47 -0500559 u64 blocknr;
560 int ret;
561 u32 refs;
562
Chris Mason5caf2a02007-04-02 11:20:42 -0400563 WARN_ON(*level < 0);
564 WARN_ON(*level >= BTRFS_MAX_LEVEL);
Chris Masone20d96d2007-03-22 12:13:20 -0400565 ret = lookup_block_ref(trans, root, path->nodes[*level]->b_blocknr,
Chris Mason6407bf62007-03-27 06:33:00 -0400566 1, &refs);
Chris Mason20524f02007-03-10 06:35:47 -0500567 BUG_ON(ret);
568 if (refs > 1)
569 goto out;
Chris Mason9aca1d52007-03-13 11:09:37 -0400570 /*
571 * walk down to the last node level and free all the leaves
572 */
Chris Mason6407bf62007-03-27 06:33:00 -0400573 while(*level >= 0) {
Chris Mason5caf2a02007-04-02 11:20:42 -0400574 WARN_ON(*level < 0);
575 WARN_ON(*level >= BTRFS_MAX_LEVEL);
Chris Mason20524f02007-03-10 06:35:47 -0500576 cur = path->nodes[*level];
Chris Mason2c90e5d2007-04-02 10:50:19 -0400577 if (btrfs_header_level(btrfs_buffer_header(cur)) != *level)
578 WARN_ON(1);
Chris Mason7518a232007-03-12 12:01:18 -0400579 if (path->slots[*level] >=
Chris Masone20d96d2007-03-22 12:13:20 -0400580 btrfs_header_nritems(btrfs_buffer_header(cur)))
Chris Mason20524f02007-03-10 06:35:47 -0500581 break;
Chris Mason6407bf62007-03-27 06:33:00 -0400582 if (*level == 0) {
583 ret = drop_leaf_ref(trans, root, cur);
584 BUG_ON(ret);
585 break;
586 }
Chris Masone20d96d2007-03-22 12:13:20 -0400587 blocknr = btrfs_node_blockptr(btrfs_buffer_node(cur),
588 path->slots[*level]);
Chris Mason6407bf62007-03-27 06:33:00 -0400589 ret = lookup_block_ref(trans, root, blocknr, 1, &refs);
590 BUG_ON(ret);
591 if (refs != 1) {
Chris Mason20524f02007-03-10 06:35:47 -0500592 path->slots[*level]++;
Chris Masone089f052007-03-16 16:20:31 -0400593 ret = btrfs_free_extent(trans, root, blocknr, 1, 1);
Chris Mason20524f02007-03-10 06:35:47 -0500594 BUG_ON(ret);
595 continue;
596 }
Chris Mason20524f02007-03-10 06:35:47 -0500597 next = read_tree_block(root, blocknr);
Chris Mason5caf2a02007-04-02 11:20:42 -0400598 WARN_ON(*level <= 0);
Chris Mason83e15a22007-03-12 09:03:27 -0400599 if (path->nodes[*level-1])
Chris Mason234b63a2007-03-13 10:46:10 -0400600 btrfs_block_release(root, path->nodes[*level-1]);
Chris Mason20524f02007-03-10 06:35:47 -0500601 path->nodes[*level-1] = next;
Chris Masone20d96d2007-03-22 12:13:20 -0400602 *level = btrfs_header_level(btrfs_buffer_header(next));
Chris Mason20524f02007-03-10 06:35:47 -0500603 path->slots[*level] = 0;
604 }
605out:
Chris Mason5caf2a02007-04-02 11:20:42 -0400606 WARN_ON(*level < 0);
607 WARN_ON(*level >= BTRFS_MAX_LEVEL);
Chris Mason6407bf62007-03-27 06:33:00 -0400608 ret = btrfs_free_extent(trans, root,
609 path->nodes[*level]->b_blocknr, 1, 1);
Chris Mason234b63a2007-03-13 10:46:10 -0400610 btrfs_block_release(root, path->nodes[*level]);
Chris Mason20524f02007-03-10 06:35:47 -0500611 path->nodes[*level] = NULL;
612 *level += 1;
613 BUG_ON(ret);
614 return 0;
615}
616
Chris Mason9aca1d52007-03-13 11:09:37 -0400617/*
618 * helper for dropping snapshots. This walks back up the tree in the path
619 * to find the first node higher up where we haven't yet gone through
620 * all the slots
621 */
Chris Masone089f052007-03-16 16:20:31 -0400622static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root
623 *root, struct btrfs_path *path, int *level)
Chris Mason20524f02007-03-10 06:35:47 -0500624{
625 int i;
626 int slot;
627 int ret;
Chris Mason234b63a2007-03-13 10:46:10 -0400628 for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
Chris Mason20524f02007-03-10 06:35:47 -0500629 slot = path->slots[i];
Chris Masone20d96d2007-03-22 12:13:20 -0400630 if (slot < btrfs_header_nritems(
631 btrfs_buffer_header(path->nodes[i])) - 1) {
Chris Mason20524f02007-03-10 06:35:47 -0500632 path->slots[i]++;
633 *level = i;
634 return 0;
635 } else {
Chris Masone089f052007-03-16 16:20:31 -0400636 ret = btrfs_free_extent(trans, root,
Chris Masone20d96d2007-03-22 12:13:20 -0400637 path->nodes[*level]->b_blocknr,
Chris Masone089f052007-03-16 16:20:31 -0400638 1, 1);
Chris Mason6407bf62007-03-27 06:33:00 -0400639 BUG_ON(ret);
Chris Mason234b63a2007-03-13 10:46:10 -0400640 btrfs_block_release(root, path->nodes[*level]);
Chris Mason83e15a22007-03-12 09:03:27 -0400641 path->nodes[*level] = NULL;
Chris Mason20524f02007-03-10 06:35:47 -0500642 *level = i + 1;
Chris Mason20524f02007-03-10 06:35:47 -0500643 }
644 }
645 return 1;
646}
647
Chris Mason9aca1d52007-03-13 11:09:37 -0400648/*
649 * drop the reference count on the tree rooted at 'snap'. This traverses
650 * the tree freeing any blocks that have a ref count of zero after being
651 * decremented.
652 */
Chris Masone089f052007-03-16 16:20:31 -0400653int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
Chris Masone20d96d2007-03-22 12:13:20 -0400654 *root, struct buffer_head *snap)
Chris Mason20524f02007-03-10 06:35:47 -0500655{
Chris Mason3768f362007-03-13 16:47:54 -0400656 int ret = 0;
Chris Mason9aca1d52007-03-13 11:09:37 -0400657 int wret;
Chris Mason20524f02007-03-10 06:35:47 -0500658 int level;
Chris Mason5caf2a02007-04-02 11:20:42 -0400659 struct btrfs_path *path;
Chris Mason20524f02007-03-10 06:35:47 -0500660 int i;
661 int orig_level;
662
Chris Mason5caf2a02007-04-02 11:20:42 -0400663 path = btrfs_alloc_path();
664 BUG_ON(!path);
665 btrfs_init_path(path);
Chris Mason20524f02007-03-10 06:35:47 -0500666
Chris Masone20d96d2007-03-22 12:13:20 -0400667 level = btrfs_header_level(btrfs_buffer_header(snap));
Chris Mason20524f02007-03-10 06:35:47 -0500668 orig_level = level;
Chris Mason5caf2a02007-04-02 11:20:42 -0400669 path->nodes[level] = snap;
670 path->slots[level] = 0;
Chris Mason20524f02007-03-10 06:35:47 -0500671 while(1) {
Chris Mason5caf2a02007-04-02 11:20:42 -0400672 wret = walk_down_tree(trans, root, path, &level);
Chris Mason9aca1d52007-03-13 11:09:37 -0400673 if (wret > 0)
Chris Mason20524f02007-03-10 06:35:47 -0500674 break;
Chris Mason9aca1d52007-03-13 11:09:37 -0400675 if (wret < 0)
676 ret = wret;
677
Chris Mason5caf2a02007-04-02 11:20:42 -0400678 wret = walk_up_tree(trans, root, path, &level);
Chris Mason9aca1d52007-03-13 11:09:37 -0400679 if (wret > 0)
Chris Mason20524f02007-03-10 06:35:47 -0500680 break;
Chris Mason9aca1d52007-03-13 11:09:37 -0400681 if (wret < 0)
682 ret = wret;
Chris Mason20524f02007-03-10 06:35:47 -0500683 }
Chris Mason83e15a22007-03-12 09:03:27 -0400684 for (i = 0; i <= orig_level; i++) {
Chris Mason5caf2a02007-04-02 11:20:42 -0400685 if (path->nodes[i]) {
686 btrfs_block_release(root, path->nodes[i]);
Chris Mason83e15a22007-03-12 09:03:27 -0400687 }
Chris Mason20524f02007-03-10 06:35:47 -0500688 }
Chris Mason5caf2a02007-04-02 11:20:42 -0400689 btrfs_free_path(path);
Chris Mason9aca1d52007-03-13 11:09:37 -0400690 return ret;
Chris Mason20524f02007-03-10 06:35:47 -0500691}