1 #include <linux/module.h>
4 #include "print-tree.h"
5 #include "transaction.h"
7 static 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
);
10 static int finish_current_insert(struct btrfs_trans_handle
*trans
, struct
11 btrfs_root
*extent_root
);
12 static int del_pending_extents(struct btrfs_trans_handle
*trans
, struct
13 btrfs_root
*extent_root
);
15 static int inc_block_ref(struct btrfs_trans_handle
*trans
, struct btrfs_root
16 *root
, u64 blocknr
, u64 num_blocks
)
18 struct btrfs_path
*path
;
22 struct btrfs_extent_item
*item
;
26 find_free_extent(trans
, root
->fs_info
->extent_root
, 0, 0, (u64
)-1,
28 path
= btrfs_alloc_path();
30 btrfs_init_path(path
);
31 key
.objectid
= blocknr
;
33 btrfs_set_key_type(&key
, BTRFS_EXTENT_ITEM_KEY
);
34 key
.offset
= num_blocks
;
35 ret
= btrfs_search_slot(trans
, root
->fs_info
->extent_root
, &key
, path
,
40 l
= btrfs_buffer_leaf(path
->nodes
[0]);
41 item
= btrfs_item_ptr(l
, path
->slots
[0], struct btrfs_extent_item
);
42 refs
= btrfs_extent_refs(item
);
43 btrfs_set_extent_refs(item
, refs
+ 1);
44 btrfs_mark_buffer_dirty(path
->nodes
[0]);
46 btrfs_release_path(root
->fs_info
->extent_root
, path
);
47 btrfs_free_path(path
);
48 finish_current_insert(trans
, root
->fs_info
->extent_root
);
49 del_pending_extents(trans
, root
->fs_info
->extent_root
);
53 static int lookup_block_ref(struct btrfs_trans_handle
*trans
, struct btrfs_root
54 *root
, u64 blocknr
, u64 num_blocks
, u32
*refs
)
56 struct btrfs_path
*path
;
60 struct btrfs_extent_item
*item
;
62 path
= btrfs_alloc_path();
63 btrfs_init_path(path
);
64 key
.objectid
= blocknr
;
65 key
.offset
= num_blocks
;
67 btrfs_set_key_type(&key
, BTRFS_EXTENT_ITEM_KEY
);
68 ret
= btrfs_search_slot(trans
, root
->fs_info
->extent_root
, &key
, path
,
72 l
= btrfs_buffer_leaf(path
->nodes
[0]);
73 item
= btrfs_item_ptr(l
, path
->slots
[0], struct btrfs_extent_item
);
74 *refs
= btrfs_extent_refs(item
);
75 btrfs_release_path(root
->fs_info
->extent_root
, path
);
76 btrfs_free_path(path
);
80 int btrfs_inc_ref(struct btrfs_trans_handle
*trans
, struct btrfs_root
*root
,
81 struct buffer_head
*buf
)
84 struct btrfs_node
*buf_node
;
85 struct btrfs_leaf
*buf_leaf
;
86 struct btrfs_disk_key
*key
;
87 struct btrfs_file_extent_item
*fi
;
94 buf_node
= btrfs_buffer_node(buf
);
95 leaf
= btrfs_is_leaf(buf_node
);
96 buf_leaf
= btrfs_buffer_leaf(buf
);
97 for (i
= 0; i
< btrfs_header_nritems(&buf_node
->header
); i
++) {
99 key
= &buf_leaf
->items
[i
].key
;
100 if (btrfs_disk_key_type(key
) != BTRFS_EXTENT_DATA_KEY
)
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
));
109 blocknr
= btrfs_node_blockptr(buf_node
, i
);
110 ret
= inc_block_ref(trans
, root
, blocknr
, 1);
117 int btrfs_finish_extent_commit(struct btrfs_trans_handle
*trans
, struct
120 unsigned long gang
[8];
124 struct radix_tree_root
*pinned_radix
= &root
->fs_info
->pinned_radix
;
127 ret
= find_first_radix_bit(pinned_radix
, gang
,
133 for (i
= 0; i
< ret
; i
++) {
134 clear_radix_bit(pinned_radix
, gang
[i
]);
137 if (root
->fs_info
->last_insert
.objectid
> first
)
138 root
->fs_info
->last_insert
.objectid
= first
;
139 root
->fs_info
->last_insert
.offset
= 0;
143 static int finish_current_insert(struct btrfs_trans_handle
*trans
, struct
144 btrfs_root
*extent_root
)
146 struct btrfs_key ins
;
147 struct btrfs_extent_item extent_item
;
150 u64 super_blocks_used
;
151 struct btrfs_fs_info
*info
= extent_root
->fs_info
;
153 btrfs_set_extent_refs(&extent_item
, 1);
154 btrfs_set_extent_owner(&extent_item
,
155 btrfs_header_parentid(btrfs_buffer_header(extent_root
->node
)));
158 btrfs_set_key_type(&ins
, BTRFS_EXTENT_ITEM_KEY
);
160 for (i
= 0; i
< extent_root
->fs_info
->current_insert
.flags
; i
++) {
161 ins
.objectid
= extent_root
->fs_info
->current_insert
.objectid
+
163 super_blocks_used
= btrfs_super_blocks_used(info
->disk_super
);
164 btrfs_set_super_blocks_used(info
->disk_super
,
165 super_blocks_used
+ 1);
166 ret
= btrfs_insert_item(trans
, extent_root
, &ins
, &extent_item
,
167 sizeof(extent_item
));
170 extent_root
->fs_info
->current_insert
.offset
= 0;
174 static int pin_down_block(struct btrfs_root
*root
, u64 blocknr
, int pending
)
177 struct btrfs_header
*header
;
178 struct buffer_head
*bh
;
181 bh
= btrfs_find_tree_block(root
, blocknr
);
183 if (buffer_uptodate(bh
)) {
185 root
->fs_info
->running_transaction
->transid
;
186 header
= btrfs_buffer_header(bh
);
187 if (btrfs_header_generation(header
) ==
189 btrfs_block_release(root
, bh
);
193 btrfs_block_release(root
, bh
);
195 err
= set_radix_bit(&root
->fs_info
->pinned_radix
, blocknr
);
197 err
= set_radix_bit(&root
->fs_info
->pending_del_radix
, blocknr
);
204 * remove an extent from the root, returns 0 on success
206 static int __free_extent(struct btrfs_trans_handle
*trans
, struct btrfs_root
207 *root
, u64 blocknr
, u64 num_blocks
, int pin
)
209 struct btrfs_path
*path
;
210 struct btrfs_key key
;
211 struct btrfs_fs_info
*info
= root
->fs_info
;
212 struct btrfs_root
*extent_root
= info
->extent_root
;
214 struct btrfs_extent_item
*ei
;
215 struct btrfs_key ins
;
218 key
.objectid
= blocknr
;
220 btrfs_set_key_type(&key
, BTRFS_EXTENT_ITEM_KEY
);
221 key
.offset
= num_blocks
;
223 find_free_extent(trans
, root
, 0, 0, (u64
)-1, &ins
);
224 path
= btrfs_alloc_path();
226 btrfs_init_path(path
);
227 ret
= btrfs_search_slot(trans
, extent_root
, &key
, path
, -1, 1);
229 printk("failed to find %Lu\n", key
.objectid
);
230 btrfs_print_tree(extent_root
, extent_root
->node
);
231 printk("failed to find %Lu\n", key
.objectid
);
234 ei
= btrfs_item_ptr(btrfs_buffer_leaf(path
->nodes
[0]), path
->slots
[0],
235 struct btrfs_extent_item
);
236 BUG_ON(ei
->refs
== 0);
237 refs
= btrfs_extent_refs(ei
) - 1;
238 btrfs_set_extent_refs(ei
, refs
);
239 btrfs_mark_buffer_dirty(path
->nodes
[0]);
241 u64 super_blocks_used
;
244 ret
= pin_down_block(root
, blocknr
, 0);
248 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
);
251 ret
= btrfs_del_item(trans
, extent_root
, path
);
255 btrfs_release_path(extent_root
, path
);
256 btrfs_free_path(path
);
257 finish_current_insert(trans
, extent_root
);
262 * find all the blocks marked as pending in the radix tree and remove
263 * them from the extent map
265 static int del_pending_extents(struct btrfs_trans_handle
*trans
, struct
266 btrfs_root
*extent_root
)
271 unsigned long gang
[4];
273 struct radix_tree_root
*pending_radix
;
274 struct radix_tree_root
*pinned_radix
;
276 pending_radix
= &extent_root
->fs_info
->pending_del_radix
;
277 pinned_radix
= &extent_root
->fs_info
->pinned_radix
;
280 ret
= find_first_radix_bit(pending_radix
, gang
,
284 for (i
= 0; i
< ret
; i
++) {
285 wret
= set_radix_bit(pinned_radix
, gang
[i
]);
287 wret
= clear_radix_bit(pending_radix
, gang
[i
]);
289 wret
= __free_extent(trans
, extent_root
,
299 * remove an extent from the root, returns 0 on success
301 int btrfs_free_extent(struct btrfs_trans_handle
*trans
, struct btrfs_root
302 *root
, u64 blocknr
, u64 num_blocks
, int pin
)
304 struct btrfs_root
*extent_root
= root
->fs_info
->extent_root
;
308 if (root
== extent_root
) {
309 pin_down_block(root
, blocknr
, 1);
312 ret
= __free_extent(trans
, root
, blocknr
, num_blocks
, pin
);
313 pending_ret
= del_pending_extents(trans
, root
->fs_info
->extent_root
);
314 return ret
? ret
: pending_ret
;
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
321 * ins->flags = BTRFS_EXTENT_ITEM_KEY
322 * ins->offset == number of blocks
323 * Any available blocks before search_start are skipped.
325 static 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
)
329 struct btrfs_path
*path
;
330 struct btrfs_key key
;
337 struct btrfs_leaf
*l
;
338 struct btrfs_root
* root
= orig_root
->fs_info
->extent_root
;
339 int total_needed
= num_blocks
;
342 path
= btrfs_alloc_path();
344 btrfs_set_key_type(ins
, BTRFS_EXTENT_ITEM_KEY
);
346 level
= btrfs_header_level(btrfs_buffer_header(root
->node
));
347 total_needed
+= (level
+ 1) * 3;
348 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);
357 if (path
->slots
[0] > 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
);
363 if (root
->fs_info
->last_insert
.objectid
> search_start
)
364 search_start
= root
->fs_info
->last_insert
.objectid
;
366 path
= btrfs_alloc_path();
369 btrfs_init_path(path
);
370 ins
->objectid
= search_start
;
373 ret
= btrfs_search_slot(trans
, root
, ins
, path
, 0, 0);
377 if (path
->slots
[0] > 0)
381 l
= btrfs_buffer_leaf(path
->nodes
[0]);
382 slot
= path
->slots
[0];
383 if (slot
>= btrfs_header_nritems(&l
->header
)) {
384 ret
= btrfs_next_leaf(root
, path
);
390 ins
->objectid
= search_start
;
391 ins
->offset
= (u64
)-1;
395 ins
->objectid
= last_block
> search_start
?
396 last_block
: search_start
;
397 ins
->offset
= (u64
)-1;
400 btrfs_disk_key_to_cpu(&key
, &l
->items
[slot
].key
);
401 if (key
.objectid
>= search_start
) {
403 if (last_block
< search_start
)
404 last_block
= search_start
;
405 hole_size
= key
.objectid
- last_block
;
406 if (hole_size
> total_needed
) {
407 ins
->objectid
= last_block
;
408 ins
->offset
= hole_size
;
414 last_block
= key
.objectid
+ key
.offset
;
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
422 btrfs_release_path(root
, path
);
423 BUG_ON(ins
->objectid
< search_start
);
424 for (test_block
= ins
->objectid
;
425 test_block
< ins
->objectid
+ total_needed
; test_block
++) {
426 if (test_radix_bit(&root
->fs_info
->pinned_radix
,
428 search_start
= test_block
+ 1;
432 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
;
437 ins
->offset
= num_blocks
;
438 btrfs_free_path(path
);
441 btrfs_release_path(root
, path
);
442 btrfs_free_path(path
);
447 * 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.
451 * returns 0 if everything worked, non-zero otherwise.
453 int btrfs_alloc_extent(struct btrfs_trans_handle
*trans
, struct btrfs_root
454 *root
, u64 num_blocks
, u64 search_start
, u64
455 search_end
, u64 owner
, struct btrfs_key
*ins
)
459 u64 super_blocks_used
;
460 struct btrfs_fs_info
*info
= root
->fs_info
;
461 struct btrfs_root
*extent_root
= info
->extent_root
;
462 struct btrfs_extent_item extent_item
;
464 btrfs_set_extent_refs(&extent_item
, 1);
465 btrfs_set_extent_owner(&extent_item
, owner
);
467 if (root
== extent_root
) {
468 BUG_ON(extent_root
->fs_info
->current_insert
.offset
== 0);
469 BUG_ON(num_blocks
!= 1);
470 BUG_ON(extent_root
->fs_info
->current_insert
.flags
==
471 extent_root
->fs_info
->current_insert
.offset
);
473 ins
->objectid
= extent_root
->fs_info
->current_insert
.objectid
+
474 extent_root
->fs_info
->current_insert
.flags
++;
477 ret
= find_free_extent(trans
, root
, num_blocks
, search_start
,
482 super_blocks_used
= btrfs_super_blocks_used(info
->disk_super
);
483 btrfs_set_super_blocks_used(info
->disk_super
, super_blocks_used
+
485 ret
= btrfs_insert_item(trans
, extent_root
, ins
, &extent_item
,
486 sizeof(extent_item
));
488 finish_current_insert(trans
, extent_root
);
489 pending_ret
= del_pending_extents(trans
, extent_root
);
498 * helper function to allocate a block for a given tree
499 * returns the tree buffer or NULL.
501 struct buffer_head
*btrfs_alloc_free_block(struct btrfs_trans_handle
*trans
,
502 struct btrfs_root
*root
)
504 struct btrfs_key ins
;
506 struct buffer_head
*buf
;
508 ret
= btrfs_alloc_extent(trans
, root
, 1, 0, (unsigned long)-1,
509 btrfs_header_parentid(btrfs_buffer_header(root
->node
)), &ins
);
514 buf
= btrfs_find_create_tree_block(root
, ins
.objectid
);
515 set_buffer_uptodate(buf
);
519 static int drop_leaf_ref(struct btrfs_trans_handle
*trans
,
520 struct btrfs_root
*root
, struct buffer_head
*cur
)
522 struct btrfs_disk_key
*key
;
523 struct btrfs_leaf
*leaf
;
524 struct btrfs_file_extent_item
*fi
;
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
)
536 fi
= btrfs_item_ptr(leaf
, i
, struct btrfs_file_extent_item
);
538 * FIXME make sure to insert a trans record that
539 * repeats the snapshot del on crash
541 ret
= btrfs_free_extent(trans
, root
,
542 btrfs_file_extent_disk_blocknr(fi
),
543 btrfs_file_extent_disk_num_blocks(fi
),
551 * helper function for drop_snapshot, this walks down the tree dropping ref
554 static int walk_down_tree(struct btrfs_trans_handle
*trans
, struct btrfs_root
555 *root
, struct btrfs_path
*path
, int *level
)
557 struct buffer_head
*next
;
558 struct buffer_head
*cur
;
564 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
565 ret
= lookup_block_ref(trans
, root
, path
->nodes
[*level
]->b_blocknr
,
571 * walk down to the last node level and free all the leaves
575 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
576 cur
= path
->nodes
[*level
];
577 if (btrfs_header_level(btrfs_buffer_header(cur
)) != *level
)
579 if (path
->slots
[*level
] >=
580 btrfs_header_nritems(btrfs_buffer_header(cur
)))
583 ret
= drop_leaf_ref(trans
, root
, cur
);
587 blocknr
= btrfs_node_blockptr(btrfs_buffer_node(cur
),
588 path
->slots
[*level
]);
589 ret
= lookup_block_ref(trans
, root
, blocknr
, 1, &refs
);
592 path
->slots
[*level
]++;
593 ret
= btrfs_free_extent(trans
, root
, blocknr
, 1, 1);
597 next
= read_tree_block(root
, blocknr
);
598 WARN_ON(*level
<= 0);
599 if (path
->nodes
[*level
-1])
600 btrfs_block_release(root
, path
->nodes
[*level
-1]);
601 path
->nodes
[*level
-1] = next
;
602 *level
= btrfs_header_level(btrfs_buffer_header(next
));
603 path
->slots
[*level
] = 0;
607 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
608 ret
= btrfs_free_extent(trans
, root
,
609 path
->nodes
[*level
]->b_blocknr
, 1, 1);
610 btrfs_block_release(root
, path
->nodes
[*level
]);
611 path
->nodes
[*level
] = NULL
;
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
622 static int walk_up_tree(struct btrfs_trans_handle
*trans
, struct btrfs_root
623 *root
, struct btrfs_path
*path
, int *level
)
628 for(i
= *level
; i
< BTRFS_MAX_LEVEL
- 1 && path
->nodes
[i
]; i
++) {
629 slot
= path
->slots
[i
];
630 if (slot
< btrfs_header_nritems(
631 btrfs_buffer_header(path
->nodes
[i
])) - 1) {
636 ret
= btrfs_free_extent(trans
, root
,
637 path
->nodes
[*level
]->b_blocknr
,
640 btrfs_block_release(root
, path
->nodes
[*level
]);
641 path
->nodes
[*level
] = NULL
;
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
653 int btrfs_drop_snapshot(struct btrfs_trans_handle
*trans
, struct btrfs_root
654 *root
, struct buffer_head
*snap
)
659 struct btrfs_path
*path
;
663 path
= btrfs_alloc_path();
665 btrfs_init_path(path
);
667 level
= btrfs_header_level(btrfs_buffer_header(snap
));
669 path
->nodes
[level
] = snap
;
670 path
->slots
[level
] = 0;
672 wret
= walk_down_tree(trans
, root
, path
, &level
);
678 wret
= walk_up_tree(trans
, root
, path
, &level
);
684 for (i
= 0; i
<= orig_level
; i
++) {
685 if (path
->nodes
[i
]) {
686 btrfs_block_release(root
, path
->nodes
[i
]);
689 btrfs_free_path(path
);