2 * Copyright (C) 2007 Oracle. All rights reserved.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
21 #include "kerncompat.h"
22 #include "radix-tree.h"
25 #include "print-tree.h"
26 #include "transaction.h"
29 #define BLOCK_GROUP_DATA EXTENT_WRITEBACK
30 #define BLOCK_GROUP_METADATA EXTENT_UPTODATE
31 #define BLOCK_GROUP_DIRTY EXTENT_DIRTY
33 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
34 btrfs_root *extent_root);
35 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
36 btrfs_root *extent_root);
37 static int find_previous_extent(struct btrfs_root *root,
38 struct btrfs_path *path)
40 struct btrfs_key found_key;
41 struct extent_buffer *leaf;
45 if (path->slots[0] == 0) {
46 ret = btrfs_prev_leaf(root, path);
52 leaf = path->nodes[0];
53 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
54 if (found_key.type == BTRFS_EXTENT_ITEM_KEY)
59 static int cache_block_group(struct btrfs_root *root,
60 struct btrfs_block_group_cache *block_group)
62 struct btrfs_path *path;
65 struct extent_buffer *leaf;
66 struct extent_io_tree *free_space_cache;
76 root = root->fs_info->extent_root;
77 free_space_cache = &root->fs_info->free_space_cache;
79 if (block_group->cached)
82 path = btrfs_alloc_path();
87 first_free = block_group->key.objectid;
88 key.objectid = block_group->key.objectid;
90 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
91 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
94 ret = find_previous_extent(root, path);
98 leaf = path->nodes[0];
99 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
100 if (key.objectid + key.offset > first_free)
101 first_free = key.objectid + key.offset;
104 leaf = path->nodes[0];
105 slot = path->slots[0];
106 if (slot >= btrfs_header_nritems(leaf)) {
107 ret = btrfs_next_leaf(root, path);
116 btrfs_item_key_to_cpu(leaf, &key, slot);
117 if (key.objectid < block_group->key.objectid) {
120 if (key.objectid >= block_group->key.objectid +
121 block_group->key.offset) {
125 if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
130 if (key.objectid > last) {
131 hole_size = key.objectid - last;
132 set_extent_dirty(free_space_cache, last,
133 last + hole_size - 1,
136 last = key.objectid + key.offset;
144 if (block_group->key.objectid +
145 block_group->key.offset > last) {
146 hole_size = block_group->key.objectid +
147 block_group->key.offset - last;
148 set_extent_dirty(free_space_cache, last,
149 last + hole_size - 1, GFP_NOFS);
151 block_group->cached = 1;
153 btrfs_free_path(path);
157 struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
161 struct extent_io_tree *block_group_cache;
162 struct btrfs_block_group_cache *block_group = NULL;
168 block_group_cache = &info->block_group_cache;
169 ret = find_first_extent_bit(block_group_cache,
170 bytenr, &start, &end,
171 BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA);
175 ret = get_state_private(block_group_cache, start, &ptr);
179 block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
180 if (block_group->key.objectid <= bytenr && bytenr <
181 block_group->key.objectid + block_group->key.offset)
185 static u64 noinline find_search_start(struct btrfs_root *root,
186 struct btrfs_block_group_cache **cache_ret,
187 u64 search_start, int num, int data)
190 struct btrfs_block_group_cache *cache = *cache_ret;
201 ret = cache_block_group(root, cache);
205 last = max(search_start, cache->key.objectid);
208 ret = find_first_extent_bit(&root->fs_info->free_space_cache,
209 last, &start, &end, EXTENT_DIRTY);
216 start = max(last, start);
218 if (last - start < num) {
219 if (last == cache->key.objectid + cache->key.offset)
223 if (data != BTRFS_BLOCK_GROUP_MIXED &&
224 start + num > cache->key.objectid + cache->key.offset)
229 cache = btrfs_lookup_block_group(root->fs_info, search_start);
231 printk("Unable to find block group for %Lu\n",
239 last = cache->key.objectid + cache->key.offset;
241 cache = btrfs_lookup_block_group(root->fs_info, last);
247 data = BTRFS_BLOCK_GROUP_MIXED;
252 if (cache_miss && !cache->cached) {
253 cache_block_group(root, cache);
255 cache = btrfs_lookup_block_group(root->fs_info, last);
257 cache = btrfs_find_block_group(root, cache, last, data, 0);
265 static u64 div_factor(u64 num, int factor)
274 struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
275 struct btrfs_block_group_cache
276 *hint, u64 search_start,
279 struct btrfs_block_group_cache *cache;
280 struct extent_io_tree *block_group_cache;
281 struct btrfs_block_group_cache *found_group = NULL;
282 struct btrfs_fs_info *info = root->fs_info;
296 block_group_cache = &info->block_group_cache;
301 if (data == BTRFS_BLOCK_GROUP_MIXED) {
302 bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
305 bit = BLOCK_GROUP_DATA;
307 bit = BLOCK_GROUP_METADATA;
310 struct btrfs_block_group_cache *shint;
311 shint = btrfs_lookup_block_group(info, search_start);
312 if (shint && (shint->data == data ||
313 shint->data == BTRFS_BLOCK_GROUP_MIXED)) {
314 used = btrfs_block_group_used(&shint->item);
315 if (used + shint->pinned <
316 div_factor(shint->key.offset, factor)) {
321 if (hint && (hint->data == data ||
322 hint->data == BTRFS_BLOCK_GROUP_MIXED)) {
323 used = btrfs_block_group_used(&hint->item);
324 if (used + hint->pinned <
325 div_factor(hint->key.offset, factor)) {
328 last = hint->key.objectid + hint->key.offset;
332 hint_last = max(hint->key.objectid, search_start);
334 hint_last = search_start;
340 ret = find_first_extent_bit(block_group_cache, last,
345 ret = get_state_private(block_group_cache, start, &ptr);
349 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
350 last = cache->key.objectid + cache->key.offset;
351 used = btrfs_block_group_used(&cache->item);
354 free_check = cache->key.offset;
356 free_check = div_factor(cache->key.offset, factor);
357 if (used + cache->pinned < free_check) {
370 bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
378 static u64 hash_extent_ref(u64 root_objectid, u64 ref_generation,
379 u64 owner, u64 owner_offset)
381 u32 high_crc = ~(u32)0;
382 u32 low_crc = ~(u32)0;
385 lenum = cpu_to_le64(root_objectid);
386 high_crc = crc32c(high_crc, &lenum, sizeof(lenum));
387 lenum = cpu_to_le64(ref_generation);
388 low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
389 if (owner >= BTRFS_FIRST_FREE_OBJECTID) {
390 lenum = cpu_to_le64(owner);
391 low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
392 lenum = cpu_to_le64(owner_offset);
393 low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
395 return ((u64)high_crc << 32) | (u64)low_crc;
398 static int match_extent_ref(struct extent_buffer *leaf,
399 struct btrfs_extent_ref *disk_ref,
400 struct btrfs_extent_ref *cpu_ref)
405 if (cpu_ref->objectid)
406 len = sizeof(*cpu_ref);
408 len = 2 * sizeof(u64);
409 ret = memcmp_extent_buffer(leaf, cpu_ref, (unsigned long)disk_ref,
414 static int noinline lookup_extent_backref(struct btrfs_trans_handle *trans,
415 struct btrfs_root *root,
416 struct btrfs_path *path, u64 bytenr,
418 u64 ref_generation, u64 owner,
419 u64 owner_offset, int del)
422 struct btrfs_key key;
423 struct btrfs_key found_key;
424 struct btrfs_extent_ref ref;
425 struct extent_buffer *leaf;
426 struct btrfs_extent_ref *disk_ref;
430 btrfs_set_stack_ref_root(&ref, root_objectid);
431 btrfs_set_stack_ref_generation(&ref, ref_generation);
432 btrfs_set_stack_ref_objectid(&ref, owner);
433 btrfs_set_stack_ref_offset(&ref, owner_offset);
435 hash = hash_extent_ref(root_objectid, ref_generation, owner,
438 key.objectid = bytenr;
439 key.type = BTRFS_EXTENT_REF_KEY;
442 ret = btrfs_search_slot(trans, root, &key, path,
446 leaf = path->nodes[0];
448 u32 nritems = btrfs_header_nritems(leaf);
449 if (path->slots[0] >= nritems) {
450 ret2 = btrfs_next_leaf(root, path);
453 leaf = path->nodes[0];
455 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
456 if (found_key.objectid != bytenr ||
457 found_key.type != BTRFS_EXTENT_REF_KEY)
459 key.offset = found_key.offset;
461 btrfs_release_path(root, path);
465 disk_ref = btrfs_item_ptr(path->nodes[0],
467 struct btrfs_extent_ref);
468 if (match_extent_ref(path->nodes[0], disk_ref, &ref)) {
472 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
473 key.offset = found_key.offset + 1;
474 btrfs_release_path(root, path);
481 * Back reference rules. Back refs have three main goals:
483 * 1) differentiate between all holders of references to an extent so that
484 * when a reference is dropped we can make sure it was a valid reference
485 * before freeing the extent.
487 * 2) Provide enough information to quickly find the holders of an extent
488 * if we notice a given block is corrupted or bad.
490 * 3) Make it easy to migrate blocks for FS shrinking or storage pool
491 * maintenance. This is actually the same as #2, but with a slightly
492 * different use case.
494 * File extents can be referenced by:
496 * - multiple snapshots, subvolumes, or different generations in one subvol
497 * - different files inside a single subvolume (in theory, not implemented yet)
498 * - different offsets inside a file (bookend extents in file.c)
500 * The extent ref structure has fields for:
502 * - Objectid of the subvolume root
503 * - Generation number of the tree holding the reference
504 * - objectid of the file holding the reference
505 * - offset in the file corresponding to the key holding the reference
507 * When a file extent is allocated the fields are filled in:
508 * (root_key.objectid, trans->transid, inode objectid, offset in file)
510 * When a leaf is cow'd new references are added for every file extent found
511 * in the leaf. It looks the same as the create case, but trans->transid
512 * will be different when the block is cow'd.
514 * (root_key.objectid, trans->transid, inode objectid, offset in file)
516 * When a file extent is removed either during snapshot deletion or file
517 * truncation, the corresponding back reference is found
520 * (btrfs_header_owner(leaf), btrfs_header_generation(leaf),
521 * inode objectid, offset in file)
523 * Btree extents can be referenced by:
525 * - Different subvolumes
526 * - Different generations of the same subvolume
528 * Storing sufficient information for a full reverse mapping of a btree
529 * block would require storing the lowest key of the block in the backref,
530 * and it would require updating that lowest key either before write out or
531 * every time it changed. Instead, the objectid of the lowest key is stored
532 * along with the level of the tree block. This provides a hint
533 * about where in the btree the block can be found. Searches through the
534 * btree only need to look for a pointer to that block, so they stop one
535 * level higher than the level recorded in the backref.
537 * Some btrees do not do reference counting on their extents. These
538 * include the extent tree and the tree of tree roots. Backrefs for these
539 * trees always have a generation of zero.
541 * When a tree block is created, back references are inserted:
543 * (root->root_key.objectid, trans->transid or zero, level, lowest_key_objectid)
545 * When a tree block is cow'd in a reference counted root,
546 * new back references are added for all the blocks it points to.
547 * These are of the form (trans->transid will have increased since creation):
549 * (root->root_key.objectid, trans->transid, level, lowest_key_objectid)
551 * Because the lowest_key_objectid and the level are just hints
552 * they are not used when backrefs are deleted. When a backref is deleted:
554 * if backref was for a tree root:
555 * root_objectid = root->root_key.objectid
557 * root_objectid = btrfs_header_owner(parent)
559 * (root_objectid, btrfs_header_generation(parent) or zero, 0, 0)
561 * Back Reference Key hashing:
563 * Back references have four fields, each 64 bits long. Unfortunately,
564 * This is hashed into a single 64 bit number and placed into the key offset.
565 * The key objectid corresponds to the first byte in the extent, and the
566 * key type is set to BTRFS_EXTENT_REF_KEY
568 int btrfs_insert_extent_backref(struct btrfs_trans_handle *trans,
569 struct btrfs_root *root,
570 struct btrfs_path *path, u64 bytenr,
571 u64 root_objectid, u64 ref_generation,
572 u64 owner, u64 owner_offset)
575 struct btrfs_key key;
576 struct btrfs_extent_ref ref;
577 struct btrfs_extent_ref *disk_ref;
580 btrfs_set_stack_ref_root(&ref, root_objectid);
581 btrfs_set_stack_ref_generation(&ref, ref_generation);
582 btrfs_set_stack_ref_objectid(&ref, owner);
583 btrfs_set_stack_ref_offset(&ref, owner_offset);
585 hash = hash_extent_ref(root_objectid, ref_generation, owner,
588 key.objectid = bytenr;
589 key.type = BTRFS_EXTENT_REF_KEY;
591 ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(ref));
592 while (ret == -EEXIST) {
593 disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
594 struct btrfs_extent_ref);
595 if (match_extent_ref(path->nodes[0], disk_ref, &ref))
598 btrfs_release_path(root, path);
599 ret = btrfs_insert_empty_item(trans, root, path, &key,
604 disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
605 struct btrfs_extent_ref);
606 write_extent_buffer(path->nodes[0], &ref, (unsigned long)disk_ref,
608 btrfs_mark_buffer_dirty(path->nodes[0]);
610 btrfs_release_path(root, path);
614 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
615 struct btrfs_root *root,
616 u64 bytenr, u64 num_bytes,
617 u64 root_objectid, u64 ref_generation,
618 u64 owner, u64 owner_offset)
620 struct btrfs_path *path;
622 struct btrfs_key key;
623 struct extent_buffer *l;
624 struct btrfs_extent_item *item;
627 WARN_ON(num_bytes < root->sectorsize);
628 path = btrfs_alloc_path();
632 key.objectid = bytenr;
633 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
634 key.offset = num_bytes;
635 ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
644 item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
645 refs = btrfs_extent_refs(l, item);
646 btrfs_set_extent_refs(l, item, refs + 1);
647 btrfs_mark_buffer_dirty(path->nodes[0]);
649 btrfs_release_path(root->fs_info->extent_root, path);
651 ret = btrfs_insert_extent_backref(trans, root->fs_info->extent_root,
652 path, bytenr, root_objectid,
653 ref_generation, owner, owner_offset);
655 finish_current_insert(trans, root->fs_info->extent_root);
656 del_pending_extents(trans, root->fs_info->extent_root);
658 btrfs_free_path(path);
662 int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
663 struct btrfs_root *root)
665 finish_current_insert(trans, root->fs_info->extent_root);
666 del_pending_extents(trans, root->fs_info->extent_root);
670 static int lookup_extent_ref(struct btrfs_trans_handle *trans,
671 struct btrfs_root *root, u64 bytenr,
672 u64 num_bytes, u32 *refs)
674 struct btrfs_path *path;
676 struct btrfs_key key;
677 struct extent_buffer *l;
678 struct btrfs_extent_item *item;
680 WARN_ON(num_bytes < root->sectorsize);
681 path = btrfs_alloc_path();
682 key.objectid = bytenr;
683 key.offset = num_bytes;
684 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
685 ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
690 btrfs_print_leaf(root, path->nodes[0]);
691 printk("failed to find block number %Lu\n", bytenr);
695 item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
696 *refs = btrfs_extent_refs(l, item);
698 btrfs_free_path(path);
702 u32 btrfs_count_snapshots_in_path(struct btrfs_root *root,
703 struct btrfs_path *count_path,
706 struct btrfs_root *extent_root = root->fs_info->extent_root;
707 struct btrfs_path *path;
710 u64 root_objectid = root->root_key.objectid;
716 struct btrfs_key key;
717 struct btrfs_key found_key;
718 struct extent_buffer *l;
719 struct btrfs_extent_item *item;
720 struct btrfs_extent_ref *ref_item;
723 path = btrfs_alloc_path();
726 bytenr = first_extent;
728 bytenr = count_path->nodes[level]->start;
731 key.objectid = bytenr;
734 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
735 ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
741 btrfs_item_key_to_cpu(l, &found_key, path->slots[0]);
743 if (found_key.objectid != bytenr ||
744 found_key.type != BTRFS_EXTENT_ITEM_KEY) {
748 item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
749 refs = btrfs_extent_refs(l, item);
751 nritems = btrfs_header_nritems(l);
752 if (path->slots[0] >= nritems) {
753 ret = btrfs_next_leaf(extent_root, path);
758 btrfs_item_key_to_cpu(l, &found_key, path->slots[0]);
759 if (found_key.objectid != bytenr)
761 if (found_key.type != BTRFS_EXTENT_REF_KEY) {
767 ref_item = btrfs_item_ptr(l, path->slots[0],
768 struct btrfs_extent_ref);
769 found_objectid = btrfs_ref_root(l, ref_item);
771 if (found_objectid != root_objectid) {
778 if (cur_count == 0) {
782 if (level >= 0 && root->node == count_path->nodes[level])
785 btrfs_release_path(root, path);
789 btrfs_free_path(path);
792 int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
793 struct btrfs_root *root, u64 owner_objectid)
799 struct btrfs_disk_key disk_key;
801 level = btrfs_header_level(root->node);
802 generation = trans->transid;
803 nritems = btrfs_header_nritems(root->node);
806 btrfs_item_key(root->node, &disk_key, 0);
808 btrfs_node_key(root->node, &disk_key, 0);
809 key_objectid = btrfs_disk_key_objectid(&disk_key);
813 return btrfs_inc_extent_ref(trans, root, root->node->start,
814 root->node->len, owner_objectid,
815 generation, level, key_objectid);
818 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
819 struct extent_buffer *buf)
823 struct btrfs_key key;
824 struct btrfs_file_extent_item *fi;
833 level = btrfs_header_level(buf);
834 nritems = btrfs_header_nritems(buf);
835 for (i = 0; i < nritems; i++) {
838 btrfs_item_key_to_cpu(buf, &key, i);
839 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
841 fi = btrfs_item_ptr(buf, i,
842 struct btrfs_file_extent_item);
843 if (btrfs_file_extent_type(buf, fi) ==
844 BTRFS_FILE_EXTENT_INLINE)
846 disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
847 if (disk_bytenr == 0)
849 ret = btrfs_inc_extent_ref(trans, root, disk_bytenr,
850 btrfs_file_extent_disk_num_bytes(buf, fi),
851 root->root_key.objectid, trans->transid,
852 key.objectid, key.offset);
858 bytenr = btrfs_node_blockptr(buf, i);
859 btrfs_node_key_to_cpu(buf, &key, i);
860 ret = btrfs_inc_extent_ref(trans, root, bytenr,
861 btrfs_level_size(root, level - 1),
862 root->root_key.objectid,
864 level - 1, key.objectid);
875 for (i =0; i < faili; i++) {
878 btrfs_item_key_to_cpu(buf, &key, i);
879 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
881 fi = btrfs_item_ptr(buf, i,
882 struct btrfs_file_extent_item);
883 if (btrfs_file_extent_type(buf, fi) ==
884 BTRFS_FILE_EXTENT_INLINE)
886 disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
887 if (disk_bytenr == 0)
889 err = btrfs_free_extent(trans, root, disk_bytenr,
890 btrfs_file_extent_disk_num_bytes(buf,
894 bytenr = btrfs_node_blockptr(buf, i);
895 err = btrfs_free_extent(trans, root, bytenr,
896 btrfs_level_size(root, level - 1), 0);
904 static int write_one_cache_group(struct btrfs_trans_handle *trans,
905 struct btrfs_root *root,
906 struct btrfs_path *path,
907 struct btrfs_block_group_cache *cache)
911 struct btrfs_root *extent_root = root->fs_info->extent_root;
913 struct extent_buffer *leaf;
915 ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
920 leaf = path->nodes[0];
921 bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
922 write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
923 btrfs_mark_buffer_dirty(leaf);
924 btrfs_release_path(extent_root, path);
926 finish_current_insert(trans, extent_root);
927 pending_ret = del_pending_extents(trans, extent_root);
936 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
937 struct btrfs_root *root)
939 struct extent_io_tree *block_group_cache;
940 struct btrfs_block_group_cache *cache;
944 struct btrfs_path *path;
950 block_group_cache = &root->fs_info->block_group_cache;
951 path = btrfs_alloc_path();
956 ret = find_first_extent_bit(block_group_cache, last,
957 &start, &end, BLOCK_GROUP_DIRTY);
962 ret = get_state_private(block_group_cache, start, &ptr);
966 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
967 err = write_one_cache_group(trans, root,
970 * if we fail to write the cache group, we want
971 * to keep it marked dirty in hopes that a later
978 clear_extent_bits(block_group_cache, start, end,
979 BLOCK_GROUP_DIRTY, GFP_NOFS);
981 btrfs_free_path(path);
985 static int update_block_group(struct btrfs_trans_handle *trans,
986 struct btrfs_root *root,
987 u64 bytenr, u64 num_bytes, int alloc,
988 int mark_free, int data)
990 struct btrfs_block_group_cache *cache;
991 struct btrfs_fs_info *info = root->fs_info;
992 u64 total = num_bytes;
999 cache = btrfs_lookup_block_group(info, bytenr);
1003 byte_in_group = bytenr - cache->key.objectid;
1004 WARN_ON(byte_in_group > cache->key.offset);
1005 start = cache->key.objectid;
1006 end = start + cache->key.offset - 1;
1007 set_extent_bits(&info->block_group_cache, start, end,
1008 BLOCK_GROUP_DIRTY, GFP_NOFS);
1010 old_val = btrfs_block_group_used(&cache->item);
1011 num_bytes = min(total, cache->key.offset - byte_in_group);
1013 if (cache->data != data &&
1014 old_val < (cache->key.offset >> 1)) {
1019 bit_to_clear = BLOCK_GROUP_METADATA;
1020 bit_to_set = BLOCK_GROUP_DATA;
1021 cache->item.flags &=
1022 ~BTRFS_BLOCK_GROUP_MIXED;
1023 cache->item.flags |=
1024 BTRFS_BLOCK_GROUP_DATA;
1026 bit_to_clear = BLOCK_GROUP_DATA;
1027 bit_to_set = BLOCK_GROUP_METADATA;
1028 cache->item.flags &=
1029 ~BTRFS_BLOCK_GROUP_MIXED;
1030 cache->item.flags &=
1031 ~BTRFS_BLOCK_GROUP_DATA;
1033 clear_extent_bits(&info->block_group_cache,
1034 start, end, bit_to_clear,
1036 set_extent_bits(&info->block_group_cache,
1037 start, end, bit_to_set,
1039 } else if (cache->data != data &&
1040 cache->data != BTRFS_BLOCK_GROUP_MIXED) {
1041 cache->data = BTRFS_BLOCK_GROUP_MIXED;
1042 set_extent_bits(&info->block_group_cache,
1045 BLOCK_GROUP_METADATA,
1048 old_val += num_bytes;
1050 old_val -= num_bytes;
1052 set_extent_dirty(&info->free_space_cache,
1053 bytenr, bytenr + num_bytes - 1,
1057 btrfs_set_block_group_used(&cache->item, old_val);
1059 bytenr += num_bytes;
1063 static int update_pinned_extents(struct btrfs_root *root,
1064 u64 bytenr, u64 num, int pin)
1067 struct btrfs_block_group_cache *cache;
1068 struct btrfs_fs_info *fs_info = root->fs_info;
1071 set_extent_dirty(&fs_info->pinned_extents,
1072 bytenr, bytenr + num - 1, GFP_NOFS);
1074 clear_extent_dirty(&fs_info->pinned_extents,
1075 bytenr, bytenr + num - 1, GFP_NOFS);
1078 cache = btrfs_lookup_block_group(fs_info, bytenr);
1080 len = min(num, cache->key.offset -
1081 (bytenr - cache->key.objectid));
1083 cache->pinned += len;
1084 fs_info->total_pinned += len;
1086 cache->pinned -= len;
1087 fs_info->total_pinned -= len;
1095 int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy)
1100 struct extent_io_tree *pinned_extents = &root->fs_info->pinned_extents;
1104 ret = find_first_extent_bit(pinned_extents, last,
1105 &start, &end, EXTENT_DIRTY);
1108 set_extent_dirty(copy, start, end, GFP_NOFS);
1114 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
1115 struct btrfs_root *root,
1116 struct extent_io_tree *unpin)
1121 struct extent_io_tree *free_space_cache;
1122 free_space_cache = &root->fs_info->free_space_cache;
1125 ret = find_first_extent_bit(unpin, 0, &start, &end,
1129 update_pinned_extents(root, start, end + 1 - start, 0);
1130 clear_extent_dirty(unpin, start, end, GFP_NOFS);
1131 set_extent_dirty(free_space_cache, start, end, GFP_NOFS);
1136 static int finish_current_insert(struct btrfs_trans_handle *trans,
1137 struct btrfs_root *extent_root)
1141 struct btrfs_fs_info *info = extent_root->fs_info;
1142 struct extent_buffer *eb;
1143 struct btrfs_path *path;
1144 struct btrfs_key ins;
1145 struct btrfs_disk_key first;
1146 struct btrfs_extent_item extent_item;
1151 btrfs_set_stack_extent_refs(&extent_item, 1);
1152 btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
1153 path = btrfs_alloc_path();
1156 ret = find_first_extent_bit(&info->extent_ins, 0, &start,
1157 &end, EXTENT_LOCKED);
1161 ins.objectid = start;
1162 ins.offset = end + 1 - start;
1163 err = btrfs_insert_item(trans, extent_root, &ins,
1164 &extent_item, sizeof(extent_item));
1165 clear_extent_bits(&info->extent_ins, start, end, EXTENT_LOCKED,
1167 eb = read_tree_block(extent_root, ins.objectid, ins.offset);
1168 level = btrfs_header_level(eb);
1170 btrfs_item_key(eb, &first, 0);
1172 btrfs_node_key(eb, &first, 0);
1174 err = btrfs_insert_extent_backref(trans, extent_root, path,
1175 start, extent_root->root_key.objectid,
1177 btrfs_disk_key_objectid(&first));
1179 free_extent_buffer(eb);
1181 btrfs_free_path(path);
1185 static int pin_down_bytes(struct btrfs_root *root, u64 bytenr, u32 num_bytes,
1189 struct extent_buffer *buf;
1192 buf = btrfs_find_tree_block(root, bytenr, num_bytes);
1194 if (btrfs_buffer_uptodate(buf)) {
1196 root->fs_info->running_transaction->transid;
1197 if (btrfs_header_generation(buf) == transid) {
1198 free_extent_buffer(buf);
1202 free_extent_buffer(buf);
1204 update_pinned_extents(root, bytenr, num_bytes, 1);
1206 set_extent_bits(&root->fs_info->pending_del,
1207 bytenr, bytenr + num_bytes - 1,
1208 EXTENT_LOCKED, GFP_NOFS);
1215 * remove an extent from the root, returns 0 on success
1217 static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
1218 *root, u64 bytenr, u64 num_bytes,
1219 u64 root_objectid, u64 ref_generation,
1220 u64 owner_objectid, u64 owner_offset, int pin,
1223 struct btrfs_path *path;
1224 struct btrfs_key key;
1225 struct btrfs_fs_info *info = root->fs_info;
1226 struct btrfs_extent_ops *ops = info->extent_ops;
1227 struct btrfs_root *extent_root = info->extent_root;
1228 struct extent_buffer *leaf;
1230 int extent_slot = 0;
1231 int found_extent = 0;
1233 struct btrfs_extent_item *ei;
1236 key.objectid = bytenr;
1237 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
1238 key.offset = num_bytes;
1240 path = btrfs_alloc_path();
1244 ret = lookup_extent_backref(trans, extent_root, path,
1245 bytenr, root_objectid,
1247 owner_objectid, owner_offset, 1);
1249 struct btrfs_key found_key;
1250 extent_slot = path->slots[0];
1251 while(extent_slot > 0) {
1253 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
1255 if (found_key.objectid != bytenr)
1257 if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
1258 found_key.offset == num_bytes) {
1262 if (path->slots[0] - extent_slot > 5)
1266 ret = btrfs_del_item(trans, extent_root, path);
1268 btrfs_print_leaf(extent_root, path->nodes[0]);
1270 printk("Unable to find ref byte nr %Lu root %Lu "
1271 " gen %Lu owner %Lu offset %Lu\n", bytenr,
1272 root_objectid, ref_generation, owner_objectid,
1275 if (!found_extent) {
1276 btrfs_release_path(extent_root, path);
1277 ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
1281 extent_slot = path->slots[0];
1284 leaf = path->nodes[0];
1285 ei = btrfs_item_ptr(leaf, extent_slot,
1286 struct btrfs_extent_item);
1287 refs = btrfs_extent_refs(leaf, ei);
1290 btrfs_set_extent_refs(leaf, ei, refs);
1292 btrfs_mark_buffer_dirty(leaf);
1294 if (refs == 0 && found_extent && path->slots[0] == extent_slot + 1) {
1295 /* if the back ref and the extent are next to each other
1296 * they get deleted below in one shot
1298 path->slots[0] = extent_slot;
1300 } else if (found_extent) {
1301 /* otherwise delete the extent back ref */
1302 ret = btrfs_del_item(trans, extent_root, path);
1304 /* if refs are 0, we need to setup the path for deletion */
1306 btrfs_release_path(extent_root, path);
1307 ret = btrfs_search_slot(trans, extent_root, &key, path,
1320 ret = pin_down_bytes(root, bytenr, num_bytes, 0);
1326 /* block accounting for super block */
1327 super_used = btrfs_super_bytes_used(&info->super_copy);
1328 btrfs_set_super_bytes_used(&info->super_copy,
1329 super_used - num_bytes);
1331 /* block accounting for root item */
1332 root_used = btrfs_root_used(&root->root_item);
1333 btrfs_set_root_used(&root->root_item,
1334 root_used - num_bytes);
1335 ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
1340 if (ops && ops->free_extent)
1341 ops->free_extent(root, bytenr, num_bytes);
1343 ret = update_block_group(trans, root, bytenr, num_bytes, 0,
1347 btrfs_free_path(path);
1348 finish_current_insert(trans, extent_root);
1353 * find all the blocks marked as pending in the radix tree and remove
1354 * them from the extent map
1356 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
1357 btrfs_root *extent_root)
1363 struct extent_io_tree *pending_del;
1364 struct extent_io_tree *pinned_extents;
1366 pending_del = &extent_root->fs_info->pending_del;
1367 pinned_extents = &extent_root->fs_info->pinned_extents;
1370 ret = find_first_extent_bit(pending_del, 0, &start, &end,
1374 update_pinned_extents(extent_root, start, end + 1 - start, 1);
1375 clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
1377 ret = __free_extent(trans, extent_root,
1378 start, end + 1 - start,
1379 extent_root->root_key.objectid,
1388 * remove an extent from the root, returns 0 on success
1390 int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
1391 *root, u64 bytenr, u64 num_bytes,
1392 u64 root_objectid, u64 ref_generation,
1393 u64 owner_objectid, u64 owner_offset, int pin)
1395 struct btrfs_root *extent_root = root->fs_info->extent_root;
1399 WARN_ON(num_bytes < root->sectorsize);
1400 if (!root->ref_cows)
1403 if (root == extent_root) {
1404 pin_down_bytes(root, bytenr, num_bytes, 1);
1407 ret = __free_extent(trans, root, bytenr, num_bytes, root_objectid,
1408 ref_generation, owner_objectid, owner_offset,
1410 pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
1411 return ret ? ret : pending_ret;
1414 static u64 stripe_align(struct btrfs_root *root, u64 val)
1416 u64 mask = ((u64)root->stripesize - 1);
1417 u64 ret = (val + mask) & ~mask;
1422 * walks the btree of allocated extents and find a hole of a given size.
1423 * The key ins is changed to record the hole:
1424 * ins->objectid == block start
1425 * ins->flags = BTRFS_EXTENT_ITEM_KEY
1426 * ins->offset == number of blocks
1427 * Any available blocks before search_start are skipped.
1429 static int noinline find_free_extent(struct btrfs_trans_handle *trans,
1430 struct btrfs_root *orig_root,
1431 u64 num_bytes, u64 empty_size,
1432 u64 search_start, u64 search_end,
1433 u64 hint_byte, struct btrfs_key *ins,
1434 u64 exclude_start, u64 exclude_nr,
1437 struct btrfs_path *path;
1438 struct btrfs_key key;
1444 u64 orig_search_start = search_start;
1446 struct extent_buffer *l;
1447 struct btrfs_root * root = orig_root->fs_info->extent_root;
1448 struct btrfs_fs_info *info = root->fs_info;
1449 u64 total_needed = num_bytes;
1451 struct btrfs_block_group_cache *block_group;
1456 WARN_ON(num_bytes < root->sectorsize);
1457 btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
1459 level = btrfs_header_level(root->node);
1461 if (num_bytes >= 32 * 1024 * 1024 && hint_byte) {
1462 data = BTRFS_BLOCK_GROUP_MIXED;
1465 if (search_end == (u64)-1)
1466 search_end = btrfs_super_total_bytes(&info->super_copy);
1468 block_group = btrfs_lookup_block_group(info, hint_byte);
1470 hint_byte = search_start;
1471 block_group = btrfs_find_block_group(root, block_group,
1472 hint_byte, data, 1);
1474 block_group = btrfs_find_block_group(root,
1476 search_start, data, 1);
1479 total_needed += empty_size;
1480 path = btrfs_alloc_path();
1483 block_group = btrfs_lookup_block_group(info, search_start);
1485 block_group = btrfs_lookup_block_group(info,
1488 search_start = find_search_start(root, &block_group, search_start,
1489 total_needed, data);
1490 search_start = stripe_align(root, search_start);
1491 cached_start = search_start;
1492 btrfs_init_path(path);
1493 ins->objectid = search_start;
1498 ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
1501 ret = find_previous_extent(root, path);
1505 btrfs_item_key_to_cpu(l, &key, path->slots[0]);
1508 slot = path->slots[0];
1509 if (slot >= btrfs_header_nritems(l)) {
1510 ret = btrfs_next_leaf(root, path);
1516 search_start = max(search_start,
1517 block_group->key.objectid);
1519 aligned = stripe_align(root, search_start);
1520 ins->objectid = aligned;
1521 if (aligned >= search_end) {
1525 ins->offset = search_end - aligned;
1529 ins->objectid = stripe_align(root,
1530 last_byte > search_start ?
1531 last_byte : search_start);
1532 if (search_end <= ins->objectid) {
1536 ins->offset = search_end - ins->objectid;
1537 BUG_ON(ins->objectid >= search_end);
1540 btrfs_item_key_to_cpu(l, &key, slot);
1542 if (key.objectid >= search_start && key.objectid > last_byte &&
1544 if (last_byte < search_start)
1545 last_byte = search_start;
1546 aligned = stripe_align(root, last_byte);
1547 hole_size = key.objectid - aligned;
1548 if (key.objectid > aligned && hole_size >= num_bytes) {
1549 ins->objectid = aligned;
1550 ins->offset = hole_size;
1554 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY) {
1555 if (!start_found && btrfs_key_type(&key) ==
1556 BTRFS_BLOCK_GROUP_ITEM_KEY) {
1557 last_byte = key.objectid;
1565 last_byte = key.objectid + key.offset;
1567 if (!full_scan && data != BTRFS_BLOCK_GROUP_MIXED &&
1568 last_byte >= block_group->key.objectid +
1569 block_group->key.offset) {
1570 btrfs_release_path(root, path);
1571 search_start = block_group->key.objectid +
1572 block_group->key.offset;
1580 /* we have to make sure we didn't find an extent that has already
1581 * been allocated by the map tree or the original allocation
1583 btrfs_release_path(root, path);
1584 BUG_ON(ins->objectid < search_start);
1586 if (ins->objectid + num_bytes >= search_end)
1588 if (!full_scan && data != BTRFS_BLOCK_GROUP_MIXED &&
1589 ins->objectid + num_bytes > block_group->
1590 key.objectid + block_group->key.offset) {
1591 search_start = block_group->key.objectid +
1592 block_group->key.offset;
1595 if (test_range_bit(&info->extent_ins, ins->objectid,
1596 ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
1597 search_start = ins->objectid + num_bytes;
1600 if (test_range_bit(&info->pinned_extents, ins->objectid,
1601 ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
1602 search_start = ins->objectid + num_bytes;
1605 if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
1606 ins->objectid < exclude_start + exclude_nr)) {
1607 search_start = exclude_start + exclude_nr;
1611 block_group = btrfs_lookup_block_group(info, ins->objectid);
1613 trans->block_group = block_group;
1615 ins->offset = num_bytes;
1616 btrfs_free_path(path);
1620 if (search_start + num_bytes >= search_end) {
1622 search_start = orig_search_start;
1629 total_needed -= empty_size;
1631 data = BTRFS_BLOCK_GROUP_MIXED;
1635 block_group = btrfs_lookup_block_group(info, search_start);
1637 block_group = btrfs_find_block_group(root, block_group,
1638 search_start, data, 0);
1642 btrfs_release_path(root, path);
1643 btrfs_free_path(path);
1647 * finds a free extent and does all the dirty work required for allocation
1648 * returns the key for the extent through ins, and a tree buffer for
1649 * the first block of the extent through buf.
1651 * returns 0 if everything worked, non-zero otherwise.
1653 int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
1654 struct btrfs_root *root,
1655 u64 num_bytes, u64 root_objectid, u64 ref_generation,
1656 u64 owner, u64 owner_offset,
1657 u64 empty_size, u64 hint_byte,
1658 u64 search_end, struct btrfs_key *ins, int data)
1662 u64 super_used, root_used;
1663 u64 search_start = 0;
1664 struct btrfs_fs_info *info = root->fs_info;
1665 struct btrfs_extent_ops *ops = info->extent_ops;
1667 struct btrfs_root *extent_root = info->extent_root;
1668 struct btrfs_path *path;
1669 struct btrfs_extent_item *extent_item;
1670 struct btrfs_extent_ref *ref;
1671 struct btrfs_key keys[2];
1673 WARN_ON(num_bytes < root->sectorsize);
1674 if (ops && ops->alloc_extent) {
1675 ret = ops->alloc_extent(root, num_bytes, hint_byte, ins);
1677 ret = find_free_extent(trans, root, num_bytes, empty_size,
1678 search_start, search_end, hint_byte,
1679 ins, trans->alloc_exclude_start,
1680 trans->alloc_exclude_nr, data);
1686 /* block accounting for super block */
1687 super_used = btrfs_super_bytes_used(&info->super_copy);
1688 btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
1690 /* block accounting for root item */
1691 root_used = btrfs_root_used(&root->root_item);
1692 btrfs_set_root_used(&root->root_item, root_used + num_bytes);
1694 clear_extent_dirty(&root->fs_info->free_space_cache,
1695 ins->objectid, ins->objectid + ins->offset - 1,
1698 if (root == extent_root) {
1699 set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
1700 ins->objectid + ins->offset - 1,
1701 EXTENT_LOCKED, GFP_NOFS);
1706 WARN_ON(trans->alloc_exclude_nr);
1707 trans->alloc_exclude_start = ins->objectid;
1708 trans->alloc_exclude_nr = ins->offset;
1710 memcpy(&keys[0], ins, sizeof(*ins));
1711 keys[1].offset = hash_extent_ref(root_objectid, ref_generation,
1712 owner, owner_offset);
1713 keys[1].objectid = ins->objectid;
1714 keys[1].type = BTRFS_EXTENT_REF_KEY;
1715 sizes[0] = sizeof(*extent_item);
1716 sizes[1] = sizeof(*ref);
1718 path = btrfs_alloc_path();
1721 ret = btrfs_insert_empty_items(trans, extent_root, path, keys,
1725 extent_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
1726 struct btrfs_extent_item);
1727 btrfs_set_extent_refs(path->nodes[0], extent_item, 1);
1728 ref = btrfs_item_ptr(path->nodes[0], path->slots[0] + 1,
1729 struct btrfs_extent_ref);
1731 btrfs_set_ref_root(path->nodes[0], ref, root_objectid);
1732 btrfs_set_ref_generation(path->nodes[0], ref, ref_generation);
1733 btrfs_set_ref_objectid(path->nodes[0], ref, owner);
1734 btrfs_set_ref_offset(path->nodes[0], ref, owner_offset);
1736 btrfs_mark_buffer_dirty(path->nodes[0]);
1738 trans->alloc_exclude_start = 0;
1739 trans->alloc_exclude_nr = 0;
1740 btrfs_free_path(path);
1741 finish_current_insert(trans, extent_root);
1742 pending_ret = del_pending_extents(trans, extent_root);
1752 ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0,
1755 printk("update block group failed for %Lu %Lu\n",
1756 ins->objectid, ins->offset);
1763 * helper function to allocate a block for a given tree
1764 * returns the tree buffer or NULL.
1766 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1767 struct btrfs_root *root,
1769 u64 root_objectid, u64 hint,
1775 ref_generation = trans->transid;
1780 return __btrfs_alloc_free_block(trans, root, blocksize, root_objectid,
1781 ref_generation, 0, 0, hint, empty_size);
1785 * helper function to allocate a block for a given tree
1786 * returns the tree buffer or NULL.
1788 struct extent_buffer *__btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1789 struct btrfs_root *root,
1798 struct btrfs_key ins;
1800 struct extent_buffer *buf;
1802 ret = btrfs_alloc_extent(trans, root, blocksize,
1803 root_objectid, ref_generation,
1804 level, first_objectid, empty_size, hint,
1808 return ERR_PTR(ret);
1810 buf = btrfs_find_create_tree_block(root, ins.objectid, blocksize);
1812 btrfs_free_extent(trans, root, ins.objectid, blocksize,
1813 root->root_key.objectid, ref_generation,
1815 return ERR_PTR(-ENOMEM);
1817 btrfs_set_buffer_uptodate(buf);
1818 trans->blocks_used++;
1822 static int noinline drop_leaf_ref(struct btrfs_trans_handle *trans,
1823 struct btrfs_root *root,
1824 struct extent_buffer *leaf)
1827 u64 leaf_generation;
1828 struct btrfs_key key;
1829 struct btrfs_file_extent_item *fi;
1834 BUG_ON(!btrfs_is_leaf(leaf));
1835 nritems = btrfs_header_nritems(leaf);
1836 leaf_owner = btrfs_header_owner(leaf);
1837 leaf_generation = btrfs_header_generation(leaf);
1839 for (i = 0; i < nritems; i++) {
1842 btrfs_item_key_to_cpu(leaf, &key, i);
1843 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1845 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
1846 if (btrfs_file_extent_type(leaf, fi) ==
1847 BTRFS_FILE_EXTENT_INLINE)
1850 * FIXME make sure to insert a trans record that
1851 * repeats the snapshot del on crash
1853 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
1854 if (disk_bytenr == 0)
1856 ret = btrfs_free_extent(trans, root, disk_bytenr,
1857 btrfs_file_extent_disk_num_bytes(leaf, fi),
1858 leaf_owner, leaf_generation,
1859 key.objectid, key.offset, 0);
1865 static void noinline reada_walk_down(struct btrfs_root *root,
1866 struct extent_buffer *node,
1879 nritems = btrfs_header_nritems(node);
1880 level = btrfs_header_level(node);
1884 for (i = slot; i < nritems && skipped < 32; i++) {
1885 bytenr = btrfs_node_blockptr(node, i);
1886 if (last && ((bytenr > last && bytenr - last > 32 * 1024) ||
1887 (last > bytenr && last - bytenr > 32 * 1024))) {
1891 blocksize = btrfs_level_size(root, level - 1);
1893 ret = lookup_extent_ref(NULL, root, bytenr,
1901 mutex_unlock(&root->fs_info->fs_mutex);
1902 ret = readahead_tree_block(root, bytenr, blocksize);
1903 last = bytenr + blocksize;
1905 mutex_lock(&root->fs_info->fs_mutex);
1912 * helper function for drop_snapshot, this walks down the tree dropping ref
1913 * counts as it goes.
1915 static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
1916 struct btrfs_root *root,
1917 struct btrfs_path *path, int *level)
1922 struct extent_buffer *next;
1923 struct extent_buffer *cur;
1924 struct extent_buffer *parent;
1929 WARN_ON(*level < 0);
1930 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1931 ret = lookup_extent_ref(trans, root,
1932 path->nodes[*level]->start,
1933 path->nodes[*level]->len, &refs);
1939 * walk down to the last node level and free all the leaves
1941 while(*level >= 0) {
1942 WARN_ON(*level < 0);
1943 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1944 cur = path->nodes[*level];
1946 if (btrfs_header_level(cur) != *level)
1949 if (path->slots[*level] >=
1950 btrfs_header_nritems(cur))
1953 ret = drop_leaf_ref(trans, root, cur);
1957 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
1958 blocksize = btrfs_level_size(root, *level - 1);
1959 ret = lookup_extent_ref(trans, root, bytenr, blocksize, &refs);
1962 parent = path->nodes[*level];
1963 root_owner = btrfs_header_owner(parent);
1964 root_gen = btrfs_header_generation(parent);
1965 path->slots[*level]++;
1966 ret = btrfs_free_extent(trans, root, bytenr,
1967 blocksize, root_owner,
1972 next = btrfs_find_tree_block(root, bytenr, blocksize);
1973 if (!next || !btrfs_buffer_uptodate(next)) {
1974 free_extent_buffer(next);
1975 reada_walk_down(root, cur, path->slots[*level]);
1976 mutex_unlock(&root->fs_info->fs_mutex);
1977 next = read_tree_block(root, bytenr, blocksize);
1978 mutex_lock(&root->fs_info->fs_mutex);
1980 /* we dropped the lock, check one more time */
1981 ret = lookup_extent_ref(trans, root, bytenr,
1985 parent = path->nodes[*level];
1986 root_owner = btrfs_header_owner(parent);
1987 root_gen = btrfs_header_generation(parent);
1989 path->slots[*level]++;
1990 free_extent_buffer(next);
1991 ret = btrfs_free_extent(trans, root, bytenr,
1999 WARN_ON(*level <= 0);
2000 if (path->nodes[*level-1])
2001 free_extent_buffer(path->nodes[*level-1]);
2002 path->nodes[*level-1] = next;
2003 *level = btrfs_header_level(next);
2004 path->slots[*level] = 0;
2007 WARN_ON(*level < 0);
2008 WARN_ON(*level >= BTRFS_MAX_LEVEL);
2010 if (path->nodes[*level] == root->node) {
2011 root_owner = root->root_key.objectid;
2012 parent = path->nodes[*level];
2014 parent = path->nodes[*level + 1];
2015 root_owner = btrfs_header_owner(parent);
2018 root_gen = btrfs_header_generation(parent);
2019 ret = btrfs_free_extent(trans, root, path->nodes[*level]->start,
2020 path->nodes[*level]->len,
2021 root_owner, root_gen, 0, 0, 1);
2022 free_extent_buffer(path->nodes[*level]);
2023 path->nodes[*level] = NULL;
2030 * helper for dropping snapshots. This walks back up the tree in the path
2031 * to find the first node higher up where we haven't yet gone through
2034 static int noinline walk_up_tree(struct btrfs_trans_handle *trans,
2035 struct btrfs_root *root,
2036 struct btrfs_path *path, int *level)
2040 struct btrfs_root_item *root_item = &root->root_item;
2045 for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
2046 slot = path->slots[i];
2047 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
2048 struct extent_buffer *node;
2049 struct btrfs_disk_key disk_key;
2050 node = path->nodes[i];
2053 WARN_ON(*level == 0);
2054 btrfs_node_key(node, &disk_key, path->slots[i]);
2055 memcpy(&root_item->drop_progress,
2056 &disk_key, sizeof(disk_key));
2057 root_item->drop_level = i;
2060 if (path->nodes[*level] == root->node) {
2061 root_owner = root->root_key.objectid;
2063 btrfs_header_generation(path->nodes[*level]);
2065 struct extent_buffer *node;
2066 node = path->nodes[*level + 1];
2067 root_owner = btrfs_header_owner(node);
2068 root_gen = btrfs_header_generation(node);
2070 ret = btrfs_free_extent(trans, root,
2071 path->nodes[*level]->start,
2072 path->nodes[*level]->len,
2073 root_owner, root_gen, 0, 0, 1);
2075 free_extent_buffer(path->nodes[*level]);
2076 path->nodes[*level] = NULL;
2084 * drop the reference count on the tree rooted at 'snap'. This traverses
2085 * the tree freeing any blocks that have a ref count of zero after being
2088 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
2094 struct btrfs_path *path;
2097 struct btrfs_root_item *root_item = &root->root_item;
2099 path = btrfs_alloc_path();
2102 level = btrfs_header_level(root->node);
2104 if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
2105 path->nodes[level] = root->node;
2106 extent_buffer_get(root->node);
2107 path->slots[level] = 0;
2109 struct btrfs_key key;
2110 struct btrfs_disk_key found_key;
2111 struct extent_buffer *node;
2113 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
2114 level = root_item->drop_level;
2115 path->lowest_level = level;
2116 wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2121 node = path->nodes[level];
2122 btrfs_node_key(node, &found_key, path->slots[level]);
2123 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
2124 sizeof(found_key)));
2127 wret = walk_down_tree(trans, root, path, &level);
2133 wret = walk_up_tree(trans, root, path, &level);
2143 for (i = 0; i <= orig_level; i++) {
2144 if (path->nodes[i]) {
2145 free_extent_buffer(path->nodes[i]);
2146 path->nodes[i] = NULL;
2150 btrfs_free_path(path);
2154 int btrfs_free_block_groups(struct btrfs_fs_info *info)
2161 ret = find_first_extent_bit(&info->block_group_cache, 0,
2162 &start, &end, (unsigned int)-1);
2165 ret = get_state_private(&info->block_group_cache, start, &ptr);
2167 kfree((void *)(unsigned long)ptr);
2168 clear_extent_bits(&info->block_group_cache, start,
2169 end, (unsigned int)-1, GFP_NOFS);
2172 ret = find_first_extent_bit(&info->free_space_cache, 0,
2173 &start, &end, EXTENT_DIRTY);
2176 clear_extent_dirty(&info->free_space_cache, start,
2182 int btrfs_read_block_groups(struct btrfs_root *root)
2184 struct btrfs_path *path;
2188 struct btrfs_block_group_cache *cache;
2189 struct btrfs_fs_info *info = root->fs_info;
2190 struct extent_io_tree *block_group_cache;
2191 struct btrfs_key key;
2192 struct btrfs_key found_key;
2193 struct extent_buffer *leaf;
2195 block_group_cache = &info->block_group_cache;
2197 root = info->extent_root;
2199 key.offset = BTRFS_BLOCK_GROUP_SIZE;
2200 btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
2202 path = btrfs_alloc_path();
2207 ret = btrfs_search_slot(NULL, info->extent_root,
2213 leaf = path->nodes[0];
2214 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2215 cache = kmalloc(sizeof(*cache), GFP_NOFS);
2221 read_extent_buffer(leaf, &cache->item,
2222 btrfs_item_ptr_offset(leaf, path->slots[0]),
2223 sizeof(cache->item));
2224 memcpy(&cache->key, &found_key, sizeof(found_key));
2227 key.objectid = found_key.objectid + found_key.offset;
2228 btrfs_release_path(root, path);
2230 if (cache->item.flags & BTRFS_BLOCK_GROUP_MIXED) {
2231 bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
2232 cache->data = BTRFS_BLOCK_GROUP_MIXED;
2233 } else if (cache->item.flags & BTRFS_BLOCK_GROUP_DATA) {
2234 bit = BLOCK_GROUP_DATA;
2235 cache->data = BTRFS_BLOCK_GROUP_DATA;
2237 bit = BLOCK_GROUP_METADATA;
2241 /* use EXTENT_LOCKED to prevent merging */
2242 set_extent_bits(block_group_cache, found_key.objectid,
2243 found_key.objectid + found_key.offset - 1,
2244 bit | EXTENT_LOCKED, GFP_NOFS);
2245 set_state_private(block_group_cache, found_key.objectid,
2246 (unsigned long)cache);
2249 btrfs_super_total_bytes(&info->super_copy))
2253 btrfs_free_path(path);
2257 static int btrfs_insert_block_group(struct btrfs_trans_handle *trans,
2258 struct btrfs_root *root,
2259 struct btrfs_key *key,
2260 struct btrfs_block_group_item *bi)
2264 struct btrfs_root *extent_root;
2266 extent_root = root->fs_info->extent_root;
2267 ret = btrfs_insert_item(trans, extent_root, key, bi, sizeof(*bi));
2268 finish_current_insert(trans, extent_root);
2269 pending_ret = del_pending_extents(trans, extent_root);
2277 int btrfs_make_block_groups(struct btrfs_trans_handle *trans,
2278 struct btrfs_root *root)
2287 struct btrfs_root *extent_root;
2288 struct btrfs_block_group_cache *cache;
2289 struct extent_io_tree *block_group_cache;
2291 extent_root = root->fs_info->extent_root;
2292 block_group_cache = &root->fs_info->block_group_cache;
2293 group_size = BTRFS_BLOCK_GROUP_SIZE;
2294 bytes_used = btrfs_super_bytes_used(&root->fs_info->super_copy);
2295 total_bytes = btrfs_super_total_bytes(&root->fs_info->super_copy);
2298 while (cur_start < total_bytes) {
2299 cache = malloc(sizeof(*cache));
2301 cache->key.objectid = cur_start;
2302 cache->key.offset = group_size;
2303 btrfs_set_key_type(&cache->key, BTRFS_BLOCK_GROUP_ITEM_KEY);
2304 memset(&cache->item, 0, sizeof(cache->item));
2306 btrfs_set_block_group_used(&cache->item, bytes_used);
2308 bit = BLOCK_GROUP_DATA;
2310 cache->item.flags |= BTRFS_BLOCK_GROUP_DATA;
2312 bit = BLOCK_GROUP_METADATA;
2316 set_extent_bits(block_group_cache, cur_start,
2317 cur_start + group_size - 1,
2318 bit | EXTENT_LOCKED, GFP_NOFS);
2319 set_state_private(block_group_cache, cur_start,
2320 (unsigned long)cache);
2321 cur_start += group_size;
2323 /* then insert all the items */
2325 while(cur_start < total_bytes) {
2326 cache = btrfs_lookup_block_group(root->fs_info, cur_start);
2328 ret = btrfs_insert_block_group(trans, root, &cache->key,
2331 cur_start += group_size;
2336 u64 btrfs_hash_extent_ref(u64 root_objectid, u64 ref_generation,
2337 u64 owner, u64 owner_offset)
2339 return hash_extent_ref(root_objectid, ref_generation,
2340 owner, owner_offset);
2343 int btrfs_update_block_group(struct btrfs_trans_handle *trans,
2344 struct btrfs_root *root,
2345 u64 bytenr, u64 num_bytes, int alloc,
2346 int mark_free, int data)
2348 return update_block_group(trans, root, bytenr, num_bytes,
2349 alloc, mark_free, data);