extent-tree.c (e089f05c18ab36ed5fa7e2319052e03ab800d518) extent-tree.c (9f5fae2fe6dc35b46bf56183f11398451851cb3f)
1#include <stdio.h>
2#include <stdlib.h>
3#include "kerncompat.h"
4#include "radix-tree.h"
5#include "ctree.h"
6#include "disk-io.h"
7#include "print-tree.h"
8#include "transaction.h"

--- 21 unchanged lines hidden (view full) ---

30 struct btrfs_path path;
31 int ret;
32 struct btrfs_key key;
33 struct btrfs_leaf *l;
34 struct btrfs_extent_item *item;
35 struct btrfs_key ins;
36 u32 refs;
37
1#include <stdio.h>
2#include <stdlib.h>
3#include "kerncompat.h"
4#include "radix-tree.h"
5#include "ctree.h"
6#include "disk-io.h"
7#include "print-tree.h"
8#include "transaction.h"

--- 21 unchanged lines hidden (view full) ---

30 struct btrfs_path path;
31 int ret;
32 struct btrfs_key key;
33 struct btrfs_leaf *l;
34 struct btrfs_extent_item *item;
35 struct btrfs_key ins;
36 u32 refs;
37
38 find_free_extent(trans, root->extent_root, 0, 0, (u64)-1, &ins);
38 find_free_extent(trans, root->fs_info->extent_root, 0, 0, (u64)-1,
39 &ins);
39 btrfs_init_path(&path);
40 key.objectid = blocknr;
41 key.flags = 0;
42 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
43 key.offset = 1;
40 btrfs_init_path(&path);
41 key.objectid = blocknr;
42 key.flags = 0;
43 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
44 key.offset = 1;
44 ret = btrfs_search_slot(trans, root->extent_root, &key, &path, 0, 1);
45 ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, &path,
46 0, 1);
45 if (ret != 0)
46 BUG();
47 BUG_ON(ret != 0);
48 l = &path.nodes[0]->leaf;
49 item = btrfs_item_ptr(l, path.slots[0], struct btrfs_extent_item);
50 refs = btrfs_extent_refs(item);
51 btrfs_set_extent_refs(item, refs + 1);
52
53 BUG_ON(list_empty(&path.nodes[0]->dirty));
47 if (ret != 0)
48 BUG();
49 BUG_ON(ret != 0);
50 l = &path.nodes[0]->leaf;
51 item = btrfs_item_ptr(l, path.slots[0], struct btrfs_extent_item);
52 refs = btrfs_extent_refs(item);
53 btrfs_set_extent_refs(item, refs + 1);
54
55 BUG_ON(list_empty(&path.nodes[0]->dirty));
54 btrfs_release_path(root->extent_root, &path);
55 finish_current_insert(trans, root->extent_root);
56 run_pending(trans, root->extent_root);
56 btrfs_release_path(root->fs_info->extent_root, &path);
57 finish_current_insert(trans, root->fs_info->extent_root);
58 run_pending(trans, root->fs_info->extent_root);
57 return 0;
58}
59
60static int lookup_block_ref(struct btrfs_trans_handle *trans, struct btrfs_root
61 *root, u64 blocknr, u32 *refs)
62{
63 struct btrfs_path path;
64 int ret;
65 struct btrfs_key key;
66 struct btrfs_leaf *l;
67 struct btrfs_extent_item *item;
68 btrfs_init_path(&path);
69 key.objectid = blocknr;
70 key.offset = 1;
71 key.flags = 0;
72 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
59 return 0;
60}
61
62static int lookup_block_ref(struct btrfs_trans_handle *trans, struct btrfs_root
63 *root, u64 blocknr, u32 *refs)
64{
65 struct btrfs_path path;
66 int ret;
67 struct btrfs_key key;
68 struct btrfs_leaf *l;
69 struct btrfs_extent_item *item;
70 btrfs_init_path(&path);
71 key.objectid = blocknr;
72 key.offset = 1;
73 key.flags = 0;
74 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
73 ret = btrfs_search_slot(trans, root->extent_root, &key, &path, 0, 0);
75 ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, &path,
76 0, 0);
74 if (ret != 0)
75 BUG();
76 l = &path.nodes[0]->leaf;
77 item = btrfs_item_ptr(l, path.slots[0], struct btrfs_extent_item);
78 *refs = btrfs_extent_refs(item);
77 if (ret != 0)
78 BUG();
79 l = &path.nodes[0]->leaf;
80 item = btrfs_item_ptr(l, path.slots[0], struct btrfs_extent_item);
81 *refs = btrfs_extent_refs(item);
79 btrfs_release_path(root->extent_root, &path);
82 btrfs_release_path(root->fs_info->extent_root, &path);
80 return 0;
81}
82
83int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
84 struct btrfs_buffer *buf)
85{
86 u64 blocknr;
87 int i;

--- 14 unchanged lines hidden (view full) ---

102 btrfs_root *root)
103{
104 unsigned long gang[8];
105 u64 first = 0;
106 int ret;
107 int i;
108
109 while(1) {
83 return 0;
84}
85
86int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
87 struct btrfs_buffer *buf)
88{
89 u64 blocknr;
90 int i;

--- 14 unchanged lines hidden (view full) ---

105 btrfs_root *root)
106{
107 unsigned long gang[8];
108 u64 first = 0;
109 int ret;
110 int i;
111
112 while(1) {
110 ret = radix_tree_gang_lookup(&root->pinned_radix,
111 (void **)gang, 0,
112 ARRAY_SIZE(gang));
113 ret = radix_tree_gang_lookup(&root->fs_info->pinned_radix,
114 (void **)gang, 0,
115 ARRAY_SIZE(gang));
113 if (!ret)
114 break;
115 if (!first)
116 first = gang[0];
117 for (i = 0; i < ret; i++) {
116 if (!ret)
117 break;
118 if (!first)
119 first = gang[0];
120 for (i = 0; i < ret; i++) {
118 radix_tree_delete(&root->pinned_radix, gang[i]);
121 radix_tree_delete(&root->fs_info->pinned_radix,
122 gang[i]);
119 }
120 }
123 }
124 }
121 root->last_insert.objectid = first;
122 root->last_insert.offset = 0;
125 root->fs_info->last_insert.objectid = first;
126 root->fs_info->last_insert.offset = 0;
123 return 0;
124}
125
126static int finish_current_insert(struct btrfs_trans_handle *trans, struct
127 btrfs_root *extent_root)
128{
129 struct btrfs_key ins;
130 struct btrfs_extent_item extent_item;
131 int i;
132 int ret;
133
134 btrfs_set_extent_refs(&extent_item, 1);
135 btrfs_set_extent_owner(&extent_item,
136 btrfs_header_parentid(&extent_root->node->node.header));
137 ins.offset = 1;
138 ins.flags = 0;
139 btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
140
127 return 0;
128}
129
130static int finish_current_insert(struct btrfs_trans_handle *trans, struct
131 btrfs_root *extent_root)
132{
133 struct btrfs_key ins;
134 struct btrfs_extent_item extent_item;
135 int i;
136 int ret;
137
138 btrfs_set_extent_refs(&extent_item, 1);
139 btrfs_set_extent_owner(&extent_item,
140 btrfs_header_parentid(&extent_root->node->node.header));
141 ins.offset = 1;
142 ins.flags = 0;
143 btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
144
141 for (i = 0; i < extent_root->current_insert.flags; i++) {
142 ins.objectid = extent_root->current_insert.objectid + i;
145 for (i = 0; i < extent_root->fs_info->current_insert.flags; i++) {
146 ins.objectid = extent_root->fs_info->current_insert.objectid +
147 i;
143 ret = btrfs_insert_item(trans, extent_root, &ins, &extent_item,
144 sizeof(extent_item));
145 BUG_ON(ret);
146 }
148 ret = btrfs_insert_item(trans, extent_root, &ins, &extent_item,
149 sizeof(extent_item));
150 BUG_ON(ret);
151 }
147 extent_root->current_insert.offset = 0;
152 extent_root->fs_info->current_insert.offset = 0;
148 return 0;
149}
150
151/*
152 * remove an extent from the root, returns 0 on success
153 */
154static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
155 *root, u64 blocknr, u64 num_blocks, int pin)
156{
157 struct btrfs_path path;
158 struct btrfs_key key;
153 return 0;
154}
155
156/*
157 * remove an extent from the root, returns 0 on success
158 */
159static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
160 *root, u64 blocknr, u64 num_blocks, int pin)
161{
162 struct btrfs_path path;
163 struct btrfs_key key;
159 struct btrfs_root *extent_root = root->extent_root;
164 struct btrfs_root *extent_root = root->fs_info->extent_root;
160 int ret;
161 struct btrfs_extent_item *ei;
162 struct btrfs_key ins;
163 u32 refs;
164
165 BUG_ON(pin && num_blocks != 1);
166 key.objectid = blocknr;
167 key.flags = 0;

--- 13 unchanged lines hidden (view full) ---

181 struct btrfs_extent_item);
182 BUG_ON(ei->refs == 0);
183 refs = btrfs_extent_refs(ei) - 1;
184 btrfs_set_extent_refs(ei, refs);
185 if (refs == 0) {
186 if (pin) {
187 int err;
188 radix_tree_preload(GFP_KERNEL);
165 int ret;
166 struct btrfs_extent_item *ei;
167 struct btrfs_key ins;
168 u32 refs;
169
170 BUG_ON(pin && num_blocks != 1);
171 key.objectid = blocknr;
172 key.flags = 0;

--- 13 unchanged lines hidden (view full) ---

186 struct btrfs_extent_item);
187 BUG_ON(ei->refs == 0);
188 refs = btrfs_extent_refs(ei) - 1;
189 btrfs_set_extent_refs(ei, refs);
190 if (refs == 0) {
191 if (pin) {
192 int err;
193 radix_tree_preload(GFP_KERNEL);
189 err = radix_tree_insert(&extent_root->pinned_radix,
190 blocknr, (void *)blocknr);
194 err = radix_tree_insert(
195 &extent_root->fs_info->pinned_radix,
196 blocknr, (void *)blocknr);
191 BUG_ON(err);
192 radix_tree_preload_end();
193 }
194 ret = btrfs_del_item(trans, extent_root, &path);
197 BUG_ON(err);
198 radix_tree_preload_end();
199 }
200 ret = btrfs_del_item(trans, extent_root, &path);
195 if (!pin && extent_root->last_insert.objectid > blocknr)
196 extent_root->last_insert.objectid = blocknr;
201 if (!pin && extent_root->fs_info->last_insert.objectid >
202 blocknr)
203 extent_root->fs_info->last_insert.objectid = blocknr;
197 if (ret)
198 BUG();
199 }
200 btrfs_release_path(extent_root, &path);
201 finish_current_insert(trans, extent_root);
202 return ret;
203}
204

--- 4 unchanged lines hidden (view full) ---

209static int del_pending_extents(struct btrfs_trans_handle *trans, struct
210 btrfs_root *extent_root)
211{
212 int ret;
213 struct btrfs_buffer *gang[4];
214 int i;
215
216 while(1) {
204 if (ret)
205 BUG();
206 }
207 btrfs_release_path(extent_root, &path);
208 finish_current_insert(trans, extent_root);
209 return ret;
210}
211

--- 4 unchanged lines hidden (view full) ---

216static int del_pending_extents(struct btrfs_trans_handle *trans, struct
217 btrfs_root *extent_root)
218{
219 int ret;
220 struct btrfs_buffer *gang[4];
221 int i;
222
223 while(1) {
217 ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix,
218 (void **)gang, 0,
219 ARRAY_SIZE(gang),
220 CTREE_EXTENT_PENDING_DEL);
224 ret = radix_tree_gang_lookup_tag(
225 &extent_root->fs_info->cache_radix,
226 (void **)gang, 0,
227 ARRAY_SIZE(gang),
228 CTREE_EXTENT_PENDING_DEL);
221 if (!ret)
222 break;
223 for (i = 0; i < ret; i++) {
224 ret = __free_extent(trans, extent_root,
225 gang[i]->blocknr, 1, 1);
229 if (!ret)
230 break;
231 for (i = 0; i < ret; i++) {
232 ret = __free_extent(trans, extent_root,
233 gang[i]->blocknr, 1, 1);
226 radix_tree_tag_clear(&extent_root->cache_radix,
227 gang[i]->blocknr,
228 CTREE_EXTENT_PENDING_DEL);
234 radix_tree_tag_clear(&extent_root->fs_info->cache_radix,
235 gang[i]->blocknr,
236 CTREE_EXTENT_PENDING_DEL);
229 btrfs_block_release(extent_root, gang[i]);
230 }
231 }
232 return 0;
233}
234
235static int run_pending(struct btrfs_trans_handle *trans, struct btrfs_root
236 *extent_root)
237{
237 btrfs_block_release(extent_root, gang[i]);
238 }
239 }
240 return 0;
241}
242
243static int run_pending(struct btrfs_trans_handle *trans, struct btrfs_root
244 *extent_root)
245{
238 while(radix_tree_tagged(&extent_root->cache_radix,
239 CTREE_EXTENT_PENDING_DEL))
246 while(radix_tree_tagged(&extent_root->fs_info->cache_radix,
247 CTREE_EXTENT_PENDING_DEL))
240 del_pending_extents(trans, extent_root);
241 return 0;
242}
243
244
245/*
246 * remove an extent from the root, returns 0 on success
247 */
248int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
249 *root, u64 blocknr, u64 num_blocks, int pin)
250{
248 del_pending_extents(trans, extent_root);
249 return 0;
250}
251
252
253/*
254 * remove an extent from the root, returns 0 on success
255 */
256int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
257 *root, u64 blocknr, u64 num_blocks, int pin)
258{
251 struct btrfs_root *extent_root = root->extent_root;
259 struct btrfs_root *extent_root = root->fs_info->extent_root;
252 struct btrfs_buffer *t;
253 int pending_ret;
254 int ret;
255
256 if (root == extent_root) {
257 t = find_tree_block(root, blocknr);
260 struct btrfs_buffer *t;
261 int pending_ret;
262 int ret;
263
264 if (root == extent_root) {
265 t = find_tree_block(root, blocknr);
258 radix_tree_tag_set(&root->cache_radix, blocknr,
266 radix_tree_tag_set(&root->fs_info->cache_radix, blocknr,
259 CTREE_EXTENT_PENDING_DEL);
260 return 0;
261 }
262 ret = __free_extent(trans, root, blocknr, num_blocks, pin);
267 CTREE_EXTENT_PENDING_DEL);
268 return 0;
269 }
270 ret = __free_extent(trans, root, blocknr, num_blocks, pin);
263 pending_ret = run_pending(trans, root->extent_root);
271 pending_ret = run_pending(trans, root->fs_info->extent_root);
264 return ret ? ret : pending_ret;
265}
266
267/*
268 * walks the btree of allocated extents and find a hole of a given size.
269 * The key ins is changed to record the hole:
270 * ins->objectid == block start
271 * ins->flags = BTRFS_EXTENT_ITEM_KEY

--- 8 unchanged lines hidden (view full) ---

280 struct btrfs_key key;
281 int ret;
282 u64 hole_size = 0;
283 int slot = 0;
284 u64 last_block;
285 u64 test_block;
286 int start_found;
287 struct btrfs_leaf *l;
272 return ret ? ret : pending_ret;
273}
274
275/*
276 * walks the btree of allocated extents and find a hole of a given size.
277 * The key ins is changed to record the hole:
278 * ins->objectid == block start
279 * ins->flags = BTRFS_EXTENT_ITEM_KEY

--- 8 unchanged lines hidden (view full) ---

288 struct btrfs_key key;
289 int ret;
290 u64 hole_size = 0;
291 int slot = 0;
292 u64 last_block;
293 u64 test_block;
294 int start_found;
295 struct btrfs_leaf *l;
288 struct btrfs_root * root = orig_root->extent_root;
296 struct btrfs_root * root = orig_root->fs_info->extent_root;
289 int total_needed = num_blocks;
290
291 total_needed += (btrfs_header_level(&root->node->node.header) + 1) * 3;
297 int total_needed = num_blocks;
298
299 total_needed += (btrfs_header_level(&root->node->node.header) + 1) * 3;
292 if (root->last_insert.objectid > search_start)
293 search_start = root->last_insert.objectid;
300 if (root->fs_info->last_insert.objectid > search_start)
301 search_start = root->fs_info->last_insert.objectid;
294
295 ins->flags = 0;
296 btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
297
298check_failed:
299 btrfs_init_path(&path);
300 ins->objectid = search_start;
301 ins->offset = 0;

--- 46 unchanged lines hidden (view full) ---

348check_pending:
349 /* we have to make sure we didn't find an extent that has already
350 * been allocated by the map tree or the original allocation
351 */
352 btrfs_release_path(root, &path);
353 BUG_ON(ins->objectid < search_start);
354 for (test_block = ins->objectid;
355 test_block < ins->objectid + total_needed; test_block++) {
302
303 ins->flags = 0;
304 btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
305
306check_failed:
307 btrfs_init_path(&path);
308 ins->objectid = search_start;
309 ins->offset = 0;

--- 46 unchanged lines hidden (view full) ---

356check_pending:
357 /* we have to make sure we didn't find an extent that has already
358 * been allocated by the map tree or the original allocation
359 */
360 btrfs_release_path(root, &path);
361 BUG_ON(ins->objectid < search_start);
362 for (test_block = ins->objectid;
363 test_block < ins->objectid + total_needed; test_block++) {
356 if (radix_tree_lookup(&root->pinned_radix, test_block)) {
364 if (radix_tree_lookup(&root->fs_info->pinned_radix,
365 test_block)) {
357 search_start = test_block + 1;
358 goto check_failed;
359 }
360 }
366 search_start = test_block + 1;
367 goto check_failed;
368 }
369 }
361 BUG_ON(root->current_insert.offset);
362 root->current_insert.offset = total_needed - num_blocks;
363 root->current_insert.objectid = ins->objectid + num_blocks;
364 root->current_insert.flags = 0;
365 root->last_insert.objectid = ins->objectid;
370 BUG_ON(root->fs_info->current_insert.offset);
371 root->fs_info->current_insert.offset = total_needed - num_blocks;
372 root->fs_info->current_insert.objectid = ins->objectid + num_blocks;
373 root->fs_info->current_insert.flags = 0;
374 root->fs_info->last_insert.objectid = ins->objectid;
366 ins->offset = num_blocks;
367 return 0;
368error:
369 btrfs_release_path(root, &path);
370 return ret;
371}
372
373/*

--- 4 unchanged lines hidden (view full) ---

378 * returns 0 if everything worked, non-zero otherwise.
379 */
380static int alloc_extent(struct btrfs_trans_handle *trans, struct btrfs_root
381 *root, u64 num_blocks, u64 search_start, u64
382 search_end, u64 owner, struct btrfs_key *ins)
383{
384 int ret;
385 int pending_ret;
375 ins->offset = num_blocks;
376 return 0;
377error:
378 btrfs_release_path(root, &path);
379 return ret;
380}
381
382/*

--- 4 unchanged lines hidden (view full) ---

387 * returns 0 if everything worked, non-zero otherwise.
388 */
389static int alloc_extent(struct btrfs_trans_handle *trans, struct btrfs_root
390 *root, u64 num_blocks, u64 search_start, u64
391 search_end, u64 owner, struct btrfs_key *ins)
392{
393 int ret;
394 int pending_ret;
386 struct btrfs_root *extent_root = root->extent_root;
395 struct btrfs_root *extent_root = root->fs_info->extent_root;
387 struct btrfs_extent_item extent_item;
388
389 btrfs_set_extent_refs(&extent_item, 1);
390 btrfs_set_extent_owner(&extent_item, owner);
391
392 if (root == extent_root) {
396 struct btrfs_extent_item extent_item;
397
398 btrfs_set_extent_refs(&extent_item, 1);
399 btrfs_set_extent_owner(&extent_item, owner);
400
401 if (root == extent_root) {
393 BUG_ON(extent_root->current_insert.offset == 0);
402 BUG_ON(extent_root->fs_info->current_insert.offset == 0);
394 BUG_ON(num_blocks != 1);
403 BUG_ON(num_blocks != 1);
395 BUG_ON(extent_root->current_insert.flags ==
396 extent_root->current_insert.offset);
404 BUG_ON(extent_root->fs_info->current_insert.flags ==
405 extent_root->fs_info->current_insert.offset);
397 ins->offset = 1;
406 ins->offset = 1;
398 ins->objectid = extent_root->current_insert.objectid +
399 extent_root->current_insert.flags++;
407 ins->objectid = extent_root->fs_info->current_insert.objectid +
408 extent_root->fs_info->current_insert.flags++;
400 return 0;
401 }
402 ret = find_free_extent(trans, root, num_blocks, search_start,
403 search_end, ins);
404 if (ret)
405 return ret;
406
407 ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,

--- 158 unchanged lines hidden --- 		409 return 0;
410 }
411 ret = find_free_extent(trans, root, num_blocks, search_start,
412 search_end, ins);
413 if (ret)
414 return ret;
415
416 ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,

--- 158 unchanged lines hidden ---