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 int btrfs_inc_extent_ref(struct btrfs_trans_handle
*trans
,
16 struct btrfs_root
*root
,
17 u64 blocknr
, u64 num_blocks
)
19 struct btrfs_path
*path
;
23 struct btrfs_extent_item
*item
;
27 find_free_extent(trans
, root
->fs_info
->extent_root
, 0, 0, (u64
)-1,
29 path
= btrfs_alloc_path();
31 btrfs_init_path(path
);
32 key
.objectid
= blocknr
;
34 btrfs_set_key_type(&key
, BTRFS_EXTENT_ITEM_KEY
);
35 key
.offset
= num_blocks
;
36 ret
= btrfs_search_slot(trans
, root
->fs_info
->extent_root
, &key
, path
,
39 printk("can't find block %Lu %Lu\n", blocknr
, num_blocks
);
43 l
= btrfs_buffer_leaf(path
->nodes
[0]);
44 item
= btrfs_item_ptr(l
, path
->slots
[0], struct btrfs_extent_item
);
45 refs
= btrfs_extent_refs(item
);
46 btrfs_set_extent_refs(item
, refs
+ 1);
47 btrfs_mark_buffer_dirty(path
->nodes
[0]);
49 btrfs_release_path(root
->fs_info
->extent_root
, path
);
50 btrfs_free_path(path
);
51 finish_current_insert(trans
, root
->fs_info
->extent_root
);
52 del_pending_extents(trans
, root
->fs_info
->extent_root
);
56 static int lookup_extent_ref(struct btrfs_trans_handle
*trans
,
57 struct btrfs_root
*root
, u64 blocknr
,
58 u64 num_blocks
, u32
*refs
)
60 struct btrfs_path
*path
;
64 struct btrfs_extent_item
*item
;
66 path
= btrfs_alloc_path();
67 btrfs_init_path(path
);
68 key
.objectid
= blocknr
;
69 key
.offset
= num_blocks
;
71 btrfs_set_key_type(&key
, BTRFS_EXTENT_ITEM_KEY
);
72 ret
= btrfs_search_slot(trans
, root
->fs_info
->extent_root
, &key
, path
,
76 l
= btrfs_buffer_leaf(path
->nodes
[0]);
77 item
= btrfs_item_ptr(l
, path
->slots
[0], struct btrfs_extent_item
);
78 *refs
= btrfs_extent_refs(item
);
79 btrfs_release_path(root
->fs_info
->extent_root
, path
);
80 btrfs_free_path(path
);
84 int btrfs_inc_root_ref(struct btrfs_trans_handle
*trans
,
85 struct btrfs_root
*root
)
87 return btrfs_inc_extent_ref(trans
, root
, bh_blocknr(root
->node
), 1);
90 int btrfs_inc_ref(struct btrfs_trans_handle
*trans
, struct btrfs_root
*root
,
91 struct buffer_head
*buf
)
94 struct btrfs_node
*buf_node
;
95 struct btrfs_leaf
*buf_leaf
;
96 struct btrfs_disk_key
*key
;
97 struct btrfs_file_extent_item
*fi
;
104 buf_node
= btrfs_buffer_node(buf
);
105 leaf
= btrfs_is_leaf(buf_node
);
106 buf_leaf
= btrfs_buffer_leaf(buf
);
107 for (i
= 0; i
< btrfs_header_nritems(&buf_node
->header
); i
++) {
109 key
= &buf_leaf
->items
[i
].key
;
110 if (btrfs_disk_key_type(key
) != BTRFS_EXTENT_DATA_KEY
)
112 fi
= btrfs_item_ptr(buf_leaf
, i
,
113 struct btrfs_file_extent_item
);
114 if (btrfs_file_extent_type(fi
) ==
115 BTRFS_FILE_EXTENT_INLINE
)
117 ret
= btrfs_inc_extent_ref(trans
, root
,
118 btrfs_file_extent_disk_blocknr(fi
),
119 btrfs_file_extent_disk_num_blocks(fi
));
122 blocknr
= btrfs_node_blockptr(buf_node
, i
);
123 ret
= btrfs_inc_extent_ref(trans
, root
, blocknr
, 1);
130 int btrfs_finish_extent_commit(struct btrfs_trans_handle
*trans
, struct
133 unsigned long gang
[8];
137 struct radix_tree_root
*pinned_radix
= &root
->fs_info
->pinned_radix
;
140 ret
= find_first_radix_bit(pinned_radix
, gang
,
146 for (i
= 0; i
< ret
; i
++) {
147 clear_radix_bit(pinned_radix
, gang
[i
]);
150 if (root
->fs_info
->last_insert
.objectid
> first
)
151 root
->fs_info
->last_insert
.objectid
= first
;
152 root
->fs_info
->last_insert
.offset
= 0;
156 static int finish_current_insert(struct btrfs_trans_handle
*trans
, struct
157 btrfs_root
*extent_root
)
159 struct btrfs_key ins
;
160 struct btrfs_extent_item extent_item
;
163 u64 super_blocks_used
;
164 struct btrfs_fs_info
*info
= extent_root
->fs_info
;
166 btrfs_set_extent_refs(&extent_item
, 1);
169 btrfs_set_key_type(&ins
, BTRFS_EXTENT_ITEM_KEY
);
170 btrfs_set_extent_owner(&extent_item
, extent_root
->root_key
.objectid
);
172 for (i
= 0; i
< extent_root
->fs_info
->current_insert
.flags
; i
++) {
173 ins
.objectid
= extent_root
->fs_info
->current_insert
.objectid
+
175 super_blocks_used
= btrfs_super_blocks_used(info
->disk_super
);
176 btrfs_set_super_blocks_used(info
->disk_super
,
177 super_blocks_used
+ 1);
178 ret
= btrfs_insert_item(trans
, extent_root
, &ins
, &extent_item
,
179 sizeof(extent_item
));
182 extent_root
->fs_info
->current_insert
.offset
= 0;
186 static int pin_down_block(struct btrfs_root
*root
, u64 blocknr
, int pending
)
189 struct btrfs_header
*header
;
190 struct buffer_head
*bh
;
193 bh
= btrfs_find_tree_block(root
, blocknr
);
195 if (buffer_uptodate(bh
)) {
197 root
->fs_info
->running_transaction
->transid
;
198 header
= btrfs_buffer_header(bh
);
199 if (btrfs_header_generation(header
) ==
201 btrfs_block_release(root
, bh
);
205 btrfs_block_release(root
, bh
);
207 err
= set_radix_bit(&root
->fs_info
->pinned_radix
, blocknr
);
209 err
= set_radix_bit(&root
->fs_info
->pending_del_radix
, blocknr
);
216 * remove an extent from the root, returns 0 on success
218 static int __free_extent(struct btrfs_trans_handle
*trans
, struct btrfs_root
219 *root
, u64 blocknr
, u64 num_blocks
, int pin
)
221 struct btrfs_path
*path
;
222 struct btrfs_key key
;
223 struct btrfs_fs_info
*info
= root
->fs_info
;
224 struct btrfs_root
*extent_root
= info
->extent_root
;
226 struct btrfs_extent_item
*ei
;
227 struct btrfs_key ins
;
230 key
.objectid
= blocknr
;
232 btrfs_set_key_type(&key
, BTRFS_EXTENT_ITEM_KEY
);
233 key
.offset
= num_blocks
;
235 find_free_extent(trans
, root
, 0, 0, (u64
)-1, &ins
);
236 path
= btrfs_alloc_path();
238 btrfs_init_path(path
);
240 ret
= btrfs_search_slot(trans
, extent_root
, &key
, path
, -1, 1);
242 printk("failed to find %Lu\n", key
.objectid
);
243 btrfs_print_tree(extent_root
, extent_root
->node
);
244 printk("failed to find %Lu\n", key
.objectid
);
247 ei
= btrfs_item_ptr(btrfs_buffer_leaf(path
->nodes
[0]), path
->slots
[0],
248 struct btrfs_extent_item
);
249 BUG_ON(ei
->refs
== 0);
250 refs
= btrfs_extent_refs(ei
) - 1;
251 btrfs_set_extent_refs(ei
, refs
);
252 btrfs_mark_buffer_dirty(path
->nodes
[0]);
254 u64 super_blocks_used
;
257 ret
= pin_down_block(root
, blocknr
, 0);
261 super_blocks_used
= btrfs_super_blocks_used(info
->disk_super
);
262 btrfs_set_super_blocks_used(info
->disk_super
,
263 super_blocks_used
- num_blocks
);
264 ret
= btrfs_del_item(trans
, extent_root
, path
);
268 btrfs_release_path(extent_root
, path
);
269 btrfs_free_path(path
);
270 finish_current_insert(trans
, extent_root
);
275 * find all the blocks marked as pending in the radix tree and remove
276 * them from the extent map
278 static int del_pending_extents(struct btrfs_trans_handle
*trans
, struct
279 btrfs_root
*extent_root
)
284 unsigned long gang
[4];
286 struct radix_tree_root
*pending_radix
;
287 struct radix_tree_root
*pinned_radix
;
289 pending_radix
= &extent_root
->fs_info
->pending_del_radix
;
290 pinned_radix
= &extent_root
->fs_info
->pinned_radix
;
293 ret
= find_first_radix_bit(pending_radix
, gang
,
297 for (i
= 0; i
< ret
; i
++) {
298 wret
= set_radix_bit(pinned_radix
, gang
[i
]);
300 wret
= clear_radix_bit(pending_radix
, gang
[i
]);
302 wret
= __free_extent(trans
, extent_root
,
312 * remove an extent from the root, returns 0 on success
314 int btrfs_free_extent(struct btrfs_trans_handle
*trans
, struct btrfs_root
315 *root
, u64 blocknr
, u64 num_blocks
, int pin
)
317 struct btrfs_root
*extent_root
= root
->fs_info
->extent_root
;
321 if (root
== extent_root
) {
322 pin_down_block(root
, blocknr
, 1);
325 ret
= __free_extent(trans
, root
, blocknr
, num_blocks
, pin
);
326 pending_ret
= del_pending_extents(trans
, root
->fs_info
->extent_root
);
327 return ret
? ret
: pending_ret
;
331 * walks the btree of allocated extents and find a hole of a given size.
332 * The key ins is changed to record the hole:
333 * ins->objectid == block start
334 * ins->flags = BTRFS_EXTENT_ITEM_KEY
335 * ins->offset == number of blocks
336 * Any available blocks before search_start are skipped.
338 static int find_free_extent(struct btrfs_trans_handle
*trans
, struct btrfs_root
339 *orig_root
, u64 num_blocks
, u64 search_start
, u64
340 search_end
, struct btrfs_key
*ins
)
342 struct btrfs_path
*path
;
343 struct btrfs_key key
;
350 struct btrfs_leaf
*l
;
351 struct btrfs_root
* root
= orig_root
->fs_info
->extent_root
;
352 int total_needed
= num_blocks
;
355 path
= btrfs_alloc_path();
357 btrfs_set_key_type(ins
, BTRFS_EXTENT_ITEM_KEY
);
359 level
= btrfs_header_level(btrfs_buffer_header(root
->node
));
360 total_needed
+= (level
+ 2) * 3;
361 if (root
->fs_info
->last_insert
.objectid
== 0 && search_end
== (u64
)-1) {
362 struct btrfs_disk_key
*last_key
;
363 btrfs_init_path(path
);
364 ins
->objectid
= (u64
)-1;
365 ins
->offset
= (u64
)-1;
366 ret
= btrfs_search_slot(trans
, root
, ins
, path
, 0, 0);
370 if (path
->slots
[0] > 0)
372 l
= btrfs_buffer_leaf(path
->nodes
[0]);
373 last_key
= &l
->items
[path
->slots
[0]].key
;
374 search_start
= btrfs_disk_key_objectid(last_key
);
376 if (root
->fs_info
->last_insert
.objectid
> search_start
)
377 search_start
= root
->fs_info
->last_insert
.objectid
;
380 btrfs_init_path(path
);
381 ins
->objectid
= search_start
;
384 ret
= btrfs_search_slot(trans
, root
, ins
, path
, 0, 0);
388 if (path
->slots
[0] > 0)
392 l
= btrfs_buffer_leaf(path
->nodes
[0]);
393 slot
= path
->slots
[0];
394 if (slot
>= btrfs_header_nritems(&l
->header
)) {
395 ret
= btrfs_next_leaf(root
, path
);
401 ins
->objectid
= search_start
;
402 ins
->offset
= (u64
)-1;
406 ins
->objectid
= last_block
> search_start
?
407 last_block
: search_start
;
408 ins
->offset
= (u64
)-1;
411 btrfs_disk_key_to_cpu(&key
, &l
->items
[slot
].key
);
412 if (key
.objectid
>= search_start
) {
414 if (last_block
< search_start
)
415 last_block
= search_start
;
416 hole_size
= key
.objectid
- last_block
;
417 if (hole_size
> total_needed
) {
418 ins
->objectid
= last_block
;
419 ins
->offset
= hole_size
;
425 last_block
= key
.objectid
+ key
.offset
;
430 /* we have to make sure we didn't find an extent that has already
431 * been allocated by the map tree or the original allocation
433 btrfs_release_path(root
, path
);
434 BUG_ON(ins
->objectid
< search_start
);
435 for (test_block
= ins
->objectid
;
436 test_block
< ins
->objectid
+ total_needed
; test_block
++) {
437 if (test_radix_bit(&root
->fs_info
->pinned_radix
,
439 search_start
= test_block
+ 1;
443 BUG_ON(root
->fs_info
->current_insert
.offset
);
444 root
->fs_info
->current_insert
.offset
= total_needed
- num_blocks
;
445 root
->fs_info
->current_insert
.objectid
= ins
->objectid
+ num_blocks
;
446 root
->fs_info
->current_insert
.flags
= 0;
447 root
->fs_info
->last_insert
.objectid
= ins
->objectid
;
448 ins
->offset
= num_blocks
;
449 btrfs_free_path(path
);
452 btrfs_release_path(root
, path
);
453 btrfs_free_path(path
);
458 * finds a free extent and does all the dirty work required for allocation
459 * returns the key for the extent through ins, and a tree buffer for
460 * the first block of the extent through buf.
462 * returns 0 if everything worked, non-zero otherwise.
464 int btrfs_alloc_extent(struct btrfs_trans_handle
*trans
,
465 struct btrfs_root
*root
, u64 owner
,
466 u64 num_blocks
, u64 search_start
,
467 u64 search_end
, struct btrfs_key
*ins
)
471 u64 super_blocks_used
;
472 struct btrfs_fs_info
*info
= root
->fs_info
;
473 struct btrfs_root
*extent_root
= info
->extent_root
;
474 struct btrfs_extent_item extent_item
;
476 btrfs_set_extent_refs(&extent_item
, 1);
477 btrfs_set_extent_owner(&extent_item
, owner
);
479 if (root
== extent_root
) {
480 BUG_ON(extent_root
->fs_info
->current_insert
.offset
== 0);
481 BUG_ON(num_blocks
!= 1);
482 BUG_ON(extent_root
->fs_info
->current_insert
.flags
==
483 extent_root
->fs_info
->current_insert
.offset
);
485 ins
->objectid
= extent_root
->fs_info
->current_insert
.objectid
+
486 extent_root
->fs_info
->current_insert
.flags
++;
489 ret
= find_free_extent(trans
, root
, num_blocks
, search_start
,
494 super_blocks_used
= btrfs_super_blocks_used(info
->disk_super
);
495 btrfs_set_super_blocks_used(info
->disk_super
, super_blocks_used
+
497 ret
= btrfs_insert_item(trans
, extent_root
, ins
, &extent_item
,
498 sizeof(extent_item
));
500 finish_current_insert(trans
, extent_root
);
501 pending_ret
= del_pending_extents(trans
, extent_root
);
510 * helper function to allocate a block for a given tree
511 * returns the tree buffer or NULL.
513 struct buffer_head
*btrfs_alloc_free_block(struct btrfs_trans_handle
*trans
,
514 struct btrfs_root
*root
)
516 struct btrfs_key ins
;
518 struct buffer_head
*buf
;
520 ret
= btrfs_alloc_extent(trans
, root
, root
->root_key
.objectid
,
521 1, 0, (unsigned long)-1, &ins
);
526 buf
= btrfs_find_create_tree_block(root
, ins
.objectid
);
527 set_buffer_uptodate(buf
);
531 static int drop_leaf_ref(struct btrfs_trans_handle
*trans
,
532 struct btrfs_root
*root
, struct buffer_head
*cur
)
534 struct btrfs_disk_key
*key
;
535 struct btrfs_leaf
*leaf
;
536 struct btrfs_file_extent_item
*fi
;
541 BUG_ON(!btrfs_is_leaf(btrfs_buffer_node(cur
)));
542 leaf
= btrfs_buffer_leaf(cur
);
543 nritems
= btrfs_header_nritems(&leaf
->header
);
544 for (i
= 0; i
< nritems
; i
++) {
545 key
= &leaf
->items
[i
].key
;
546 if (btrfs_disk_key_type(key
) != BTRFS_EXTENT_DATA_KEY
)
548 fi
= btrfs_item_ptr(leaf
, i
, struct btrfs_file_extent_item
);
549 if (btrfs_file_extent_type(fi
) == BTRFS_FILE_EXTENT_INLINE
)
552 * FIXME make sure to insert a trans record that
553 * repeats the snapshot del on crash
555 ret
= btrfs_free_extent(trans
, root
,
556 btrfs_file_extent_disk_blocknr(fi
),
557 btrfs_file_extent_disk_num_blocks(fi
),
565 * helper function for drop_snapshot, this walks down the tree dropping ref
568 static int walk_down_tree(struct btrfs_trans_handle
*trans
, struct btrfs_root
569 *root
, struct btrfs_path
*path
, int *level
)
571 struct buffer_head
*next
;
572 struct buffer_head
*cur
;
578 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
579 ret
= lookup_extent_ref(trans
, root
, bh_blocknr(path
->nodes
[*level
]),
585 * walk down to the last node level and free all the leaves
589 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
590 cur
= path
->nodes
[*level
];
591 if (btrfs_header_level(btrfs_buffer_header(cur
)) != *level
)
593 if (path
->slots
[*level
] >=
594 btrfs_header_nritems(btrfs_buffer_header(cur
)))
597 ret
= drop_leaf_ref(trans
, root
, cur
);
601 blocknr
= btrfs_node_blockptr(btrfs_buffer_node(cur
),
602 path
->slots
[*level
]);
603 ret
= lookup_extent_ref(trans
, root
, blocknr
, 1, &refs
);
606 path
->slots
[*level
]++;
607 ret
= btrfs_free_extent(trans
, root
, blocknr
, 1, 1);
611 next
= read_tree_block(root
, blocknr
);
612 WARN_ON(*level
<= 0);
613 if (path
->nodes
[*level
-1])
614 btrfs_block_release(root
, path
->nodes
[*level
-1]);
615 path
->nodes
[*level
-1] = next
;
616 *level
= btrfs_header_level(btrfs_buffer_header(next
));
617 path
->slots
[*level
] = 0;
621 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
622 ret
= btrfs_free_extent(trans
, root
,
623 bh_blocknr(path
->nodes
[*level
]), 1, 1);
624 btrfs_block_release(root
, path
->nodes
[*level
]);
625 path
->nodes
[*level
] = NULL
;
632 * helper for dropping snapshots. This walks back up the tree in the path
633 * to find the first node higher up where we haven't yet gone through
636 static int walk_up_tree(struct btrfs_trans_handle
*trans
, struct btrfs_root
637 *root
, struct btrfs_path
*path
, int *level
)
642 for(i
= *level
; i
< BTRFS_MAX_LEVEL
- 1 && path
->nodes
[i
]; i
++) {
643 slot
= path
->slots
[i
];
644 if (slot
< btrfs_header_nritems(
645 btrfs_buffer_header(path
->nodes
[i
])) - 1) {
650 ret
= btrfs_free_extent(trans
, root
,
651 bh_blocknr(path
->nodes
[*level
]),
654 btrfs_block_release(root
, path
->nodes
[*level
]);
655 path
->nodes
[*level
] = NULL
;
663 * drop the reference count on the tree rooted at 'snap'. This traverses
664 * the tree freeing any blocks that have a ref count of zero after being
667 int btrfs_drop_snapshot(struct btrfs_trans_handle
*trans
, struct btrfs_root
668 *root
, struct buffer_head
*snap
)
673 struct btrfs_path
*path
;
677 path
= btrfs_alloc_path();
679 btrfs_init_path(path
);
681 level
= btrfs_header_level(btrfs_buffer_header(snap
));
683 path
->nodes
[level
] = snap
;
684 path
->slots
[level
] = 0;
686 wret
= walk_down_tree(trans
, root
, path
, &level
);
692 wret
= walk_up_tree(trans
, root
, path
, &level
);
698 for (i
= 0; i
<= orig_level
; i
++) {
699 if (path
->nodes
[i
]) {
700 btrfs_block_release(root
, path
->nodes
[i
]);
703 btrfs_free_path(path
);