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
->extent_tree_insert_nr
; i
++) {
173 ins
.objectid
= extent_root
->fs_info
->extent_tree_insert
[i
];
174 super_blocks_used
= btrfs_super_blocks_used(info
->disk_super
);
175 btrfs_set_super_blocks_used(info
->disk_super
,
176 super_blocks_used
+ 1);
177 ret
= btrfs_insert_item(trans
, extent_root
, &ins
, &extent_item
,
178 sizeof(extent_item
));
181 extent_root
->fs_info
->extent_tree_insert_nr
= 0;
182 extent_root
->fs_info
->extent_tree_prealloc_nr
= 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 struct btrfs_fs_info
*info
= root
->fs_info
;
353 int total_needed
= num_blocks
;
355 int fill_prealloc
= 0;
358 path
= btrfs_alloc_path();
360 btrfs_set_key_type(ins
, BTRFS_EXTENT_ITEM_KEY
);
362 level
= btrfs_header_level(btrfs_buffer_header(root
->node
));
363 if (num_blocks
== 0) {
366 total_needed
= min(level
+ 2, BTRFS_MAX_LEVEL
) * 3;
368 if (info
->last_insert
.objectid
== 0 && search_end
== (u64
)-1) {
369 struct btrfs_disk_key
*last_key
;
370 btrfs_init_path(path
);
371 ins
->objectid
= (u64
)-1;
372 ins
->offset
= (u64
)-1;
373 ret
= btrfs_search_slot(trans
, root
, ins
, path
, 0, 0);
377 if (path
->slots
[0] > 0)
379 l
= btrfs_buffer_leaf(path
->nodes
[0]);
380 last_key
= &l
->items
[path
->slots
[0]].key
;
381 search_start
= btrfs_disk_key_objectid(last_key
);
383 if (info
->last_insert
.objectid
> search_start
)
384 search_start
= info
->last_insert
.objectid
;
387 btrfs_init_path(path
);
388 ins
->objectid
= search_start
;
391 ret
= btrfs_search_slot(trans
, root
, ins
, path
, 0, 0);
395 if (path
->slots
[0] > 0)
399 l
= btrfs_buffer_leaf(path
->nodes
[0]);
400 slot
= path
->slots
[0];
401 if (slot
>= btrfs_header_nritems(&l
->header
)) {
403 info
->extent_tree_prealloc_nr
= 0;
406 ret
= btrfs_next_leaf(root
, path
);
412 ins
->objectid
= search_start
;
413 ins
->offset
= (u64
)-1 - search_start
;
417 ins
->objectid
= last_block
> search_start
?
418 last_block
: search_start
;
419 ins
->offset
= (u64
)-1 - ins
->objectid
;
422 btrfs_disk_key_to_cpu(&key
, &l
->items
[slot
].key
);
423 if (key
.objectid
>= search_start
) {
425 if (last_block
< search_start
)
426 last_block
= search_start
;
427 hole_size
= key
.objectid
- last_block
;
428 if (hole_size
> num_blocks
) {
429 ins
->objectid
= last_block
;
430 ins
->offset
= hole_size
;
436 last_block
= key
.objectid
+ key
.offset
;
441 /* we have to make sure we didn't find an extent that has already
442 * been allocated by the map tree or the original allocation
444 btrfs_release_path(root
, path
);
445 BUG_ON(ins
->objectid
< search_start
);
446 for (test_block
= ins
->objectid
;
447 test_block
< ins
->objectid
+ num_blocks
; test_block
++) {
448 if (test_radix_bit(&info
->pinned_radix
, test_block
)) {
449 search_start
= test_block
+ 1;
453 if (!fill_prealloc
&& info
->extent_tree_insert_nr
) {
455 info
->extent_tree_insert
[info
->extent_tree_insert_nr
- 1];
456 if (ins
->objectid
+ num_blocks
>
457 info
->extent_tree_insert
[0] &&
458 ins
->objectid
<= last
) {
459 search_start
= last
+ 1;
464 if (!fill_prealloc
&& info
->extent_tree_prealloc_nr
) {
466 info
->extent_tree_prealloc
[info
->extent_tree_prealloc_nr
- 1];
467 if (ins
->objectid
+ num_blocks
> first
&&
468 ins
->objectid
<= info
->extent_tree_prealloc
[0]) {
469 search_start
= info
->extent_tree_prealloc
[0] + 1;
476 test_block
= ins
->objectid
;
477 while(test_block
< ins
->objectid
+ ins
->offset
&&
478 total_found
< total_needed
) {
479 nr
= total_needed
- total_found
- 1;
481 root
->fs_info
->extent_tree_prealloc
[nr
] =
486 if (total_found
< total_needed
) {
487 search_start
= test_block
;
490 root
->fs_info
->extent_tree_prealloc_nr
= total_found
;
492 root
->fs_info
->last_insert
.objectid
= ins
->objectid
;
493 ins
->offset
= num_blocks
;
494 btrfs_free_path(path
);
497 btrfs_release_path(root
, path
);
498 btrfs_free_path(path
);
503 * finds a free extent and does all the dirty work required for allocation
504 * returns the key for the extent through ins, and a tree buffer for
505 * the first block of the extent through buf.
507 * returns 0 if everything worked, non-zero otherwise.
509 int btrfs_alloc_extent(struct btrfs_trans_handle
*trans
,
510 struct btrfs_root
*root
, u64 owner
,
511 u64 num_blocks
, u64 search_start
,
512 u64 search_end
, struct btrfs_key
*ins
)
516 u64 super_blocks_used
;
517 struct btrfs_fs_info
*info
= root
->fs_info
;
518 struct btrfs_root
*extent_root
= info
->extent_root
;
519 struct btrfs_extent_item extent_item
;
520 struct btrfs_key prealloc_key
;
522 btrfs_set_extent_refs(&extent_item
, 1);
523 btrfs_set_extent_owner(&extent_item
, owner
);
525 if (root
== extent_root
) {
527 BUG_ON(info
->extent_tree_prealloc_nr
== 0);
528 BUG_ON(num_blocks
!= 1);
530 info
->extent_tree_prealloc_nr
--;
531 nr
= info
->extent_tree_prealloc_nr
;
532 ins
->objectid
= info
->extent_tree_prealloc
[nr
];
533 info
->extent_tree_insert
[info
->extent_tree_insert_nr
++] =
537 /* do the real allocation */
538 ret
= find_free_extent(trans
, root
, num_blocks
, search_start
,
543 /* then do prealloc for the extent tree */
544 ret
= find_free_extent(trans
, root
, 0, ins
->objectid
+ ins
->offset
,
545 search_end
, &prealloc_key
);
549 super_blocks_used
= btrfs_super_blocks_used(info
->disk_super
);
550 btrfs_set_super_blocks_used(info
->disk_super
, super_blocks_used
+
552 ret
= btrfs_insert_item(trans
, extent_root
, ins
, &extent_item
,
553 sizeof(extent_item
));
555 finish_current_insert(trans
, extent_root
);
556 pending_ret
= del_pending_extents(trans
, extent_root
);
565 * helper function to allocate a block for a given tree
566 * returns the tree buffer or NULL.
568 struct buffer_head
*btrfs_alloc_free_block(struct btrfs_trans_handle
*trans
,
569 struct btrfs_root
*root
)
571 struct btrfs_key ins
;
573 struct buffer_head
*buf
;
575 ret
= btrfs_alloc_extent(trans
, root
, root
->root_key
.objectid
,
576 1, 0, (unsigned long)-1, &ins
);
581 buf
= btrfs_find_create_tree_block(root
, ins
.objectid
);
582 set_buffer_uptodate(buf
);
586 static int drop_leaf_ref(struct btrfs_trans_handle
*trans
,
587 struct btrfs_root
*root
, struct buffer_head
*cur
)
589 struct btrfs_disk_key
*key
;
590 struct btrfs_leaf
*leaf
;
591 struct btrfs_file_extent_item
*fi
;
596 BUG_ON(!btrfs_is_leaf(btrfs_buffer_node(cur
)));
597 leaf
= btrfs_buffer_leaf(cur
);
598 nritems
= btrfs_header_nritems(&leaf
->header
);
599 for (i
= 0; i
< nritems
; i
++) {
600 key
= &leaf
->items
[i
].key
;
601 if (btrfs_disk_key_type(key
) != BTRFS_EXTENT_DATA_KEY
)
603 fi
= btrfs_item_ptr(leaf
, i
, struct btrfs_file_extent_item
);
604 if (btrfs_file_extent_type(fi
) == BTRFS_FILE_EXTENT_INLINE
)
607 * FIXME make sure to insert a trans record that
608 * repeats the snapshot del on crash
610 ret
= btrfs_free_extent(trans
, root
,
611 btrfs_file_extent_disk_blocknr(fi
),
612 btrfs_file_extent_disk_num_blocks(fi
),
620 * helper function for drop_snapshot, this walks down the tree dropping ref
623 static int walk_down_tree(struct btrfs_trans_handle
*trans
, struct btrfs_root
624 *root
, struct btrfs_path
*path
, int *level
)
626 struct buffer_head
*next
;
627 struct buffer_head
*cur
;
633 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
634 ret
= lookup_extent_ref(trans
, root
, bh_blocknr(path
->nodes
[*level
]),
640 * walk down to the last node level and free all the leaves
644 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
645 cur
= path
->nodes
[*level
];
646 if (btrfs_header_level(btrfs_buffer_header(cur
)) != *level
)
648 if (path
->slots
[*level
] >=
649 btrfs_header_nritems(btrfs_buffer_header(cur
)))
652 ret
= drop_leaf_ref(trans
, root
, cur
);
656 blocknr
= btrfs_node_blockptr(btrfs_buffer_node(cur
),
657 path
->slots
[*level
]);
658 ret
= lookup_extent_ref(trans
, root
, blocknr
, 1, &refs
);
661 path
->slots
[*level
]++;
662 ret
= btrfs_free_extent(trans
, root
, blocknr
, 1, 1);
666 next
= read_tree_block(root
, blocknr
);
667 WARN_ON(*level
<= 0);
668 if (path
->nodes
[*level
-1])
669 btrfs_block_release(root
, path
->nodes
[*level
-1]);
670 path
->nodes
[*level
-1] = next
;
671 *level
= btrfs_header_level(btrfs_buffer_header(next
));
672 path
->slots
[*level
] = 0;
676 WARN_ON(*level
>= BTRFS_MAX_LEVEL
);
677 ret
= btrfs_free_extent(trans
, root
,
678 bh_blocknr(path
->nodes
[*level
]), 1, 1);
679 btrfs_block_release(root
, path
->nodes
[*level
]);
680 path
->nodes
[*level
] = NULL
;
687 * helper for dropping snapshots. This walks back up the tree in the path
688 * to find the first node higher up where we haven't yet gone through
691 static int walk_up_tree(struct btrfs_trans_handle
*trans
, struct btrfs_root
692 *root
, struct btrfs_path
*path
, int *level
)
697 for(i
= *level
; i
< BTRFS_MAX_LEVEL
- 1 && path
->nodes
[i
]; i
++) {
698 slot
= path
->slots
[i
];
699 if (slot
< btrfs_header_nritems(
700 btrfs_buffer_header(path
->nodes
[i
])) - 1) {
705 ret
= btrfs_free_extent(trans
, root
,
706 bh_blocknr(path
->nodes
[*level
]),
709 btrfs_block_release(root
, path
->nodes
[*level
]);
710 path
->nodes
[*level
] = NULL
;
718 * drop the reference count on the tree rooted at 'snap'. This traverses
719 * the tree freeing any blocks that have a ref count of zero after being
722 int btrfs_drop_snapshot(struct btrfs_trans_handle
*trans
, struct btrfs_root
723 *root
, struct buffer_head
*snap
)
728 struct btrfs_path
*path
;
732 path
= btrfs_alloc_path();
734 btrfs_init_path(path
);
736 level
= btrfs_header_level(btrfs_buffer_header(snap
));
738 path
->nodes
[level
] = snap
;
739 path
->slots
[level
] = 0;
741 wret
= walk_down_tree(trans
, root
, path
, &level
);
747 wret
= walk_up_tree(trans
, root
, path
, &level
);
753 for (i
= 0; i
<= orig_level
; i
++) {
754 if (path
->nodes
[i
]) {
755 btrfs_block_release(root
, path
->nodes
[i
]);
758 btrfs_free_path(path
);