2 * Copyright (C) 2014 SUSE. 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.
18 * Authors: Mark Fasheh <mfasheh@suse.de>
23 #include <uuid/uuid.h>
24 #include "kerncompat.h"
25 #include "radix-tree.h"
28 #include "print-tree.h"
31 #include "rbtree-utils.h"
33 #include "qgroup-verify.h"
35 /*#define QGROUP_VERIFY_DEBUG*/
36 static unsigned long tot_extents_scanned
= 0;
38 static void add_bytes(u64 root_objectid
, u64 num_bytes
, int exclusive
);
42 u64 referenced_compressed
;
44 u64 exclusive_compressed
;
51 struct btrfs_disk_key key
;
52 struct qgroup_info diskinfo
;
54 struct qgroup_info info
;
56 struct rb_node rb_node
;
59 static struct counts_tree
{
61 unsigned int num_groups
;
62 } counts
= { .root
= RB_ROOT
};
64 static struct rb_root by_bytenr
= RB_ROOT
;
67 * List of interior tree blocks. We walk this list after loading the
68 * extent tree to resolve implied refs. For each interior node we'll
69 * place a shared ref in the ref tree against each child object. This
70 * allows the shared ref resolving code to do the actual work later of
71 * finding roots to account against.
73 * An implied ref is when a tree block has refs on it that may not
74 * exist in any of its child nodes. Even though the refs might not
75 * exist further down the tree, the fact that our interior node has a
76 * ref means we need to account anything below it to all its roots.
78 static struct ulist
*tree_blocks
= NULL
; /* unode->val = bytenr, ->aux
79 * = tree_block pointer */
91 struct rb_node bytenr_node
;
94 #ifdef QGROUP_VERIFY_DEBUG
95 static void print_ref(struct ref
*ref
)
97 printf("bytenr: %llu\t\tnum_bytes: %llu\t\t parent: %llu\t\t"
98 "root: %llu\n", ref
->bytenr
, ref
->num_bytes
,
99 ref
->parent
, ref
->root
);
102 static void print_all_refs(void)
104 unsigned long count
= 0;
106 struct rb_node
*node
;
108 node
= rb_first(&by_bytenr
);
110 ref
= rb_entry(node
, struct ref
, bytenr_node
);
115 node
= rb_next(node
);
118 printf("%lu extents scanned with %lu refs in total.\n",
119 tot_extents_scanned
, count
);
124 * Store by bytenr in rbtree
126 * The tree is sorted in ascending order by bytenr, then parent, then
127 * root. Since full refs have a parent == 0, those will come before
130 static int compare_ref(struct ref
*orig
, u64 bytenr
, u64 root
, u64 parent
)
132 if (bytenr
< orig
->bytenr
)
134 if (bytenr
> orig
->bytenr
)
137 if (parent
< orig
->parent
)
139 if (parent
> orig
->parent
)
142 if (root
< orig
->root
)
144 if (root
> orig
->root
)
151 * insert a new ref into the tree. returns the existing ref entry
152 * if one is already there.
154 static struct ref
*insert_ref(struct ref
*ref
)
157 struct rb_node
**p
= &by_bytenr
.rb_node
;
158 struct rb_node
*parent
= NULL
;
163 curr
= rb_entry(parent
, struct ref
, bytenr_node
);
165 ret
= compare_ref(curr
, ref
->bytenr
, ref
->root
, ref
->parent
);
174 rb_link_node(&ref
->bytenr_node
, parent
, p
);
175 rb_insert_color(&ref
->bytenr_node
, &by_bytenr
);
180 * Partial search, returns the first ref with matching bytenr. Caller
181 * can walk forward from there.
183 * Leftmost refs will be full refs - this is used to our advantage
184 * when resolving roots.
186 static struct ref
*find_ref_bytenr(u64 bytenr
)
188 struct rb_node
*n
= by_bytenr
.rb_node
;
192 ref
= rb_entry(n
, struct ref
, bytenr_node
);
194 if (bytenr
< ref
->bytenr
)
196 else if (bytenr
> ref
->bytenr
)
199 /* Walk to the left to find the first item */
200 struct rb_node
*node_left
= rb_prev(&ref
->bytenr_node
);
201 struct ref
*ref_left
;
204 ref_left
= rb_entry(node_left
, struct ref
,
206 if (ref_left
->bytenr
!= ref
->bytenr
)
209 node_left
= rb_prev(node_left
);
217 static struct ref
*find_ref(u64 bytenr
, u64 root
, u64 parent
)
219 struct rb_node
*n
= by_bytenr
.rb_node
;
224 ref
= rb_entry(n
, struct ref
, bytenr_node
);
226 ret
= compare_ref(ref
, bytenr
, root
, parent
);
237 static struct ref
*alloc_ref(u64 bytenr
, u64 root
, u64 parent
, u64 num_bytes
)
239 struct ref
*ref
= find_ref(bytenr
, root
, parent
);
241 BUG_ON(parent
&& root
);
244 ref
= calloc(1, sizeof(*ref
));
246 ref
->bytenr
= bytenr
;
248 ref
->parent
= parent
;
249 ref
->num_bytes
= num_bytes
;
257 static void free_ref_node(struct rb_node
*node
)
259 struct ref
*ref
= rb_entry(node
, struct ref
, bytenr_node
);
263 FREE_RB_BASED_TREE(ref
, free_ref_node
);
266 * Resolves all the possible roots for the ref at parent.
268 static void find_parent_roots(struct ulist
*roots
, u64 parent
)
271 struct rb_node
*node
;
274 * Search the rbtree for the first ref with bytenr == parent.
275 * Walk forward so long as bytenr == parent, adding resolved root ids.
276 * For each unresolved root, we recurse
278 ref
= find_ref_bytenr(parent
);
279 node
= &ref
->bytenr_node
;
281 BUG_ON(ref
->bytenr
!= parent
);
285 * Random sanity check, are we actually getting the
288 struct rb_node
*prev_node
= rb_prev(&ref
->bytenr_node
);
291 prev
= rb_entry(prev_node
, struct ref
, bytenr_node
);
292 BUG_ON(prev
->bytenr
== parent
);
298 ulist_add(roots
, ref
->root
, 0, 0);
300 find_parent_roots(roots
, ref
->parent
);
302 node
= rb_next(node
);
304 ref
= rb_entry(node
, struct ref
, bytenr_node
);
305 } while (node
&& ref
->bytenr
== parent
);
308 static void print_subvol_info(u64 subvolid
, u64 bytenr
, u64 num_bytes
,
309 struct ulist
*roots
);
311 * Account each ref. Walk the refs, for each set of refs in a
314 * - add the roots for direct refs to the ref roots ulist
316 * - resolve all possible roots for shared refs, insert each
317 * of those into ref_roots ulist (this is a recursive process)
319 * - Walk ref_roots ulist, adding extent bytes to each qgroup count that
320 * cooresponds to a found root.
322 static void account_all_refs(int do_qgroups
, u64 search_subvol
)
326 struct rb_node
*node
;
327 u64 bytenr
, num_bytes
;
328 struct ulist
*roots
= ulist_alloc(0);
329 struct ulist_iterator uiter
;
330 struct ulist_node
*unode
;
332 node
= rb_first(&by_bytenr
);
336 ref
= rb_entry(node
, struct ref
, bytenr_node
);
338 * Walk forward through the list of refs for this
339 * bytenr, adding roots to our ulist. If it's a full
340 * ref, then we have the easy case. Otherwise we need
341 * to search for roots.
343 bytenr
= ref
->bytenr
;
344 num_bytes
= ref
->num_bytes
;
346 BUG_ON(ref
->bytenr
!= bytenr
);
347 BUG_ON(ref
->num_bytes
!= num_bytes
);
349 ulist_add(roots
, ref
->root
, 0, 0);
351 find_parent_roots(roots
, ref
->parent
);
354 * When we leave this inner loop, node is set
355 * to next in our tree and will be turned into
356 * a ref object up top
358 node
= rb_next(node
);
360 ref
= rb_entry(node
, struct ref
, bytenr_node
);
361 } while (node
&& ref
->bytenr
== bytenr
);
364 * Now that we have all roots, we can properly account
365 * this extent against the corresponding qgroups.
367 if (roots
->nnodes
== 1)
373 print_subvol_info(search_subvol
, bytenr
, num_bytes
,
376 ULIST_ITER_INIT(&uiter
);
377 while ((unode
= ulist_next(roots
, &uiter
))) {
378 BUG_ON(unode
->val
== 0ULL);
379 /* We only want to account fs trees */
380 if (is_fstree(unode
->val
) && do_qgroups
)
381 add_bytes(unode
->val
, num_bytes
, exclusive
);
388 static u64
resolve_one_root(u64 bytenr
)
390 struct ref
*ref
= find_ref_bytenr(bytenr
);
396 return resolve_one_root(ref
->parent
);
399 static inline struct tree_block
*unode_tree_block(struct ulist_node
*unode
)
401 return u64_to_ptr(unode
->aux
);
403 static inline u64
unode_bytenr(struct ulist_node
*unode
)
408 static int alloc_tree_block(u64 bytenr
, u64 num_bytes
, int level
)
410 struct tree_block
*block
= calloc(1, sizeof(*block
));
413 block
->num_bytes
= num_bytes
;
414 block
->level
= level
;
415 if (ulist_add(tree_blocks
, bytenr
, ptr_to_u64(block
), 0) >= 0)
422 static void free_tree_blocks(void)
424 struct ulist_iterator uiter
;
425 struct ulist_node
*unode
;
430 ULIST_ITER_INIT(&uiter
);
431 while ((unode
= ulist_next(tree_blocks
, &uiter
)))
432 free(unode_tree_block(unode
));
433 ulist_free(tree_blocks
);
437 #ifdef QGROUP_VERIFY_DEBUG
438 static void print_tree_block(u64 bytenr
, struct tree_block
*block
)
441 struct rb_node
*node
;
443 printf("tree block: %llu\t\tlevel: %d\n", (unsigned long long)bytenr
,
446 ref
= find_ref_bytenr(bytenr
);
447 node
= &ref
->bytenr_node
;
450 node
= rb_next(node
);
452 ref
= rb_entry(node
, struct ref
, bytenr_node
);
453 } while (node
&& ref
->bytenr
== bytenr
);
458 static void print_all_tree_blocks(void)
460 struct ulist_iterator uiter
;
461 struct ulist_node
*unode
;
466 printf("Listing all found interior tree nodes:\n");
468 ULIST_ITER_INIT(&uiter
);
469 while ((unode
= ulist_next(tree_blocks
, &uiter
)))
470 print_tree_block(unode_bytenr(unode
), unode_tree_block(unode
));
474 static int add_refs_for_leaf_items(struct extent_buffer
*eb
, u64 ref_parent
)
478 u64 bytenr
, num_bytes
;
479 struct btrfs_key key
;
480 struct btrfs_disk_key disk_key
;
481 struct btrfs_file_extent_item
*fi
;
483 nr
= btrfs_header_nritems(eb
);
484 for (i
= 0; i
< nr
; i
++) {
485 btrfs_item_key(eb
, &disk_key
, i
);
486 btrfs_disk_key_to_cpu(&key
, &disk_key
);
488 if (key
.type
!= BTRFS_EXTENT_DATA_KEY
)
491 fi
= btrfs_item_ptr(eb
, i
, struct btrfs_file_extent_item
);
492 /* filter out: inline, disk_bytenr == 0, compressed?
493 * not if we can avoid it */
494 extent_type
= btrfs_file_extent_type(eb
, fi
);
496 if (extent_type
== BTRFS_FILE_EXTENT_INLINE
)
499 bytenr
= btrfs_file_extent_disk_bytenr(eb
, fi
);
503 num_bytes
= btrfs_file_extent_disk_num_bytes(eb
, fi
);
504 if (alloc_ref(bytenr
, 0, ref_parent
, num_bytes
) == NULL
)
511 static int travel_tree(struct btrfs_fs_info
*info
, struct btrfs_root
*root
,
512 u64 bytenr
, u64 num_bytes
, u64 ref_parent
)
515 struct extent_buffer
*eb
;
519 // printf("travel_tree: bytenr: %llu\tnum_bytes: %llu\tref_parent: %llu\n",
520 // bytenr, num_bytes, ref_parent);
522 eb
= read_tree_block(root
, bytenr
, num_bytes
, 0);
523 if (!extent_buffer_uptodate(eb
))
527 /* Don't add a ref for our starting tree block to itself */
528 if (bytenr
!= ref_parent
) {
529 if (alloc_ref(bytenr
, 0, ref_parent
, num_bytes
) == NULL
)
533 if (btrfs_is_leaf(eb
)) {
534 ret
= add_refs_for_leaf_items(eb
, ref_parent
);
539 * Interior nodes are tuples of (key, bytenr) where key is the
540 * leftmost key in the tree block pointed to by bytenr. We
541 * don't have to care about key here, just follow the bytenr
544 nr
= btrfs_header_nritems(eb
);
545 for (i
= 0; i
< nr
; i
++) {
546 new_bytenr
= btrfs_node_blockptr(eb
, i
);
547 new_num_bytes
= btrfs_level_size(root
,
548 btrfs_header_level(eb
) - 1);
550 ret
= travel_tree(info
, root
, new_bytenr
, new_num_bytes
,
555 free_extent_buffer(eb
);
559 static int add_refs_for_implied(struct btrfs_fs_info
*info
, u64 bytenr
,
560 struct tree_block
*block
)
563 u64 root_id
= resolve_one_root(bytenr
);
564 struct btrfs_root
*root
;
565 struct btrfs_key key
;
567 key
.objectid
= root_id
;
568 key
.type
= BTRFS_ROOT_ITEM_KEY
;
569 key
.offset
= (u64
)-1;
572 * XXX: Don't free the root object as we don't know whether it
573 * came off our fs_info struct or not.
575 root
= btrfs_read_fs_root(info
, &key
);
576 if (!root
|| IS_ERR(root
))
579 ret
= travel_tree(info
, root
, bytenr
, block
->num_bytes
, bytenr
);
587 * Place shared refs in the ref tree for each child of an interior tree node.
589 static int map_implied_refs(struct btrfs_fs_info
*info
)
592 struct ulist_iterator uiter
;
593 struct ulist_node
*unode
;
595 ULIST_ITER_INIT(&uiter
);
596 while ((unode
= ulist_next(tree_blocks
, &uiter
))) {
597 ret
= add_refs_for_implied(info
, unode_bytenr(unode
),
598 unode_tree_block(unode
));
607 * insert a new root into the tree. returns the existing root entry
608 * if one is already there. qgroupid is used
611 static int insert_count(struct qgroup_count
*qc
)
613 struct rb_node
**p
= &counts
.root
.rb_node
;
614 struct rb_node
*parent
= NULL
;
615 struct qgroup_count
*curr
;
619 curr
= rb_entry(parent
, struct qgroup_count
, rb_node
);
621 if (qc
->qgroupid
< curr
->qgroupid
)
623 else if (qc
->qgroupid
> curr
->qgroupid
)
629 rb_link_node(&qc
->rb_node
, parent
, p
);
630 rb_insert_color(&qc
->rb_node
, &counts
.root
);
634 static struct qgroup_count
*find_count(u64 qgroupid
)
636 struct rb_node
*n
= counts
.root
.rb_node
;
637 struct qgroup_count
*count
;
640 count
= rb_entry(n
, struct qgroup_count
, rb_node
);
642 if (qgroupid
< count
->qgroupid
)
644 else if (qgroupid
> count
->qgroupid
)
652 static struct qgroup_count
*alloc_count(struct btrfs_disk_key
*key
,
653 struct extent_buffer
*leaf
,
654 struct btrfs_qgroup_info_item
*disk
)
656 struct qgroup_count
*c
= calloc(1, sizeof(*c
));
657 struct qgroup_info
*item
;
660 c
->qgroupid
= btrfs_disk_key_offset(key
);
664 item
->referenced
= btrfs_qgroup_info_referenced(leaf
, disk
);
665 item
->referenced_compressed
=
666 btrfs_qgroup_info_referenced_compressed(leaf
, disk
);
667 item
->exclusive
= btrfs_qgroup_info_exclusive(leaf
, disk
);
668 item
->exclusive_compressed
=
669 btrfs_qgroup_info_exclusive_compressed(leaf
, disk
);
671 if (insert_count(c
)) {
679 static void add_bytes(u64 root_objectid
, u64 num_bytes
, int exclusive
)
681 struct qgroup_count
*count
= find_count(root_objectid
);
682 struct qgroup_info
*qg
;
684 BUG_ON(num_bytes
< 4096); /* Random sanity check. */
691 qg
->referenced
+= num_bytes
;
693 * count of compressed bytes is unimplemented, so we do the
696 qg
->referenced_compressed
+= num_bytes
;
699 qg
->exclusive
+= num_bytes
;
700 qg
->exclusive_compressed
+= num_bytes
;
704 static int load_quota_info(struct btrfs_fs_info
*info
)
707 struct btrfs_root
*root
= info
->quota_root
;
708 struct btrfs_root
*tmproot
;
709 struct btrfs_path path
;
710 struct btrfs_key key
;
711 struct btrfs_key root_key
;
712 struct btrfs_disk_key disk_key
;
713 struct extent_buffer
*leaf
;
714 struct btrfs_qgroup_info_item
*item
;
715 struct qgroup_count
*count
;
718 btrfs_init_path(&path
);
724 ret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
726 fprintf(stderr
, "ERROR: Couldn't search slot: %d\n", ret
);
731 leaf
= path
.nodes
[0];
733 nr
= btrfs_header_nritems(leaf
);
734 for(i
= 0; i
< nr
; i
++) {
735 btrfs_item_key(leaf
, &disk_key
, i
);
736 btrfs_disk_key_to_cpu(&key
, &disk_key
);
738 if (key
.type
== BTRFS_QGROUP_RELATION_KEY
)
739 printf("Ignoring qgroup relation key %llu\n",
743 * Ignore: BTRFS_QGROUP_STATUS_KEY,
744 * BTRFS_QGROUP_LIMIT_KEY, BTRFS_QGROUP_RELATION_KEY
746 if (key
.type
!= BTRFS_QGROUP_INFO_KEY
)
749 item
= btrfs_item_ptr(leaf
, i
,
750 struct btrfs_qgroup_info_item
);
752 count
= alloc_count(&disk_key
, leaf
, item
);
755 fprintf(stderr
, "ERROR: out of memory\n");
759 root_key
.objectid
= key
.offset
;
760 root_key
.type
= BTRFS_ROOT_ITEM_KEY
;
761 root_key
.offset
= (u64
)-1;
762 tmproot
= btrfs_read_fs_root_no_cache(info
, &root_key
);
763 if (tmproot
&& !IS_ERR(tmproot
)) {
764 count
->subvol_exists
= 1;
769 ret
= btrfs_next_leaf(root
, &path
);
775 btrfs_release_path(&path
);
780 static int add_inline_refs(struct btrfs_fs_info
*info
,
781 struct extent_buffer
*ei_leaf
, int slot
,
782 u64 bytenr
, u64 num_bytes
, int meta_item
)
784 struct btrfs_extent_item
*ei
;
785 struct btrfs_extent_inline_ref
*iref
;
786 struct btrfs_extent_data_ref
*dref
;
787 u64 flags
, root_obj
, offset
, parent
;
788 u32 item_size
= btrfs_item_size_nr(ei_leaf
, slot
);
793 ei
= btrfs_item_ptr(ei_leaf
, slot
, struct btrfs_extent_item
);
794 flags
= btrfs_extent_flags(ei_leaf
, ei
);
796 if (flags
& BTRFS_EXTENT_FLAG_TREE_BLOCK
&& !meta_item
) {
797 struct btrfs_tree_block_info
*tbinfo
;
798 tbinfo
= (struct btrfs_tree_block_info
*)(ei
+ 1);
799 iref
= (struct btrfs_extent_inline_ref
*)(tbinfo
+ 1);
801 iref
= (struct btrfs_extent_inline_ref
*)(ei
+ 1);
804 ptr
= (unsigned long)iref
;
805 end
= (unsigned long)ei
+ item_size
;
807 iref
= (struct btrfs_extent_inline_ref
*)ptr
;
809 parent
= root_obj
= 0;
810 offset
= btrfs_extent_inline_ref_offset(ei_leaf
, iref
);
811 type
= btrfs_extent_inline_ref_type(ei_leaf
, iref
);
813 case BTRFS_TREE_BLOCK_REF_KEY
:
816 case BTRFS_EXTENT_DATA_REF_KEY
:
817 dref
= (struct btrfs_extent_data_ref
*)(&iref
->offset
);
818 root_obj
= btrfs_extent_data_ref_root(ei_leaf
, dref
);
820 case BTRFS_SHARED_DATA_REF_KEY
:
821 case BTRFS_SHARED_BLOCK_REF_KEY
:
828 if (alloc_ref(bytenr
, root_obj
, parent
, num_bytes
) == NULL
)
831 ptr
+= btrfs_extent_inline_ref_size(type
);
837 static int add_keyed_ref(struct btrfs_fs_info
*info
,
838 struct btrfs_key
*key
,
839 struct extent_buffer
*leaf
, int slot
,
840 u64 bytenr
, u64 num_bytes
)
842 u64 root_obj
= 0, parent
= 0;
843 struct btrfs_extent_data_ref
*dref
;
846 case BTRFS_TREE_BLOCK_REF_KEY
:
847 root_obj
= key
->offset
;
849 case BTRFS_EXTENT_DATA_REF_KEY
:
850 dref
= btrfs_item_ptr(leaf
, slot
, struct btrfs_extent_data_ref
);
851 root_obj
= btrfs_extent_data_ref_root(leaf
, dref
);
853 case BTRFS_SHARED_DATA_REF_KEY
:
854 case BTRFS_SHARED_BLOCK_REF_KEY
:
855 parent
= key
->offset
;
861 if (alloc_ref(bytenr
, root_obj
, parent
, num_bytes
) == NULL
)
868 * return value of 0 indicates leaf or not meta data. The code that
869 * calls this does not need to make a distinction between the two as
870 * it is only concerned with intermediate blocks which will always
873 static int get_tree_block_level(struct btrfs_key
*key
,
874 struct extent_buffer
*ei_leaf
,
878 int meta_key
= key
->type
== BTRFS_METADATA_ITEM_KEY
;
880 struct btrfs_extent_item
*ei
;
882 ei
= btrfs_item_ptr(ei_leaf
, slot
, struct btrfs_extent_item
);
883 flags
= btrfs_extent_flags(ei_leaf
, ei
);
885 if (flags
& BTRFS_EXTENT_FLAG_TREE_BLOCK
&& !meta_key
) {
886 struct btrfs_tree_block_info
*tbinfo
;
887 tbinfo
= (struct btrfs_tree_block_info
*)(ei
+ 1);
888 level
= btrfs_tree_block_level(ei_leaf
, tbinfo
);
889 } else if (meta_key
) {
890 /* skinny metadata */
891 level
= (int)key
->offset
;
897 * Walk the extent tree, allocating a ref item for every ref and
898 * storing it in the bytenr tree.
900 static int scan_extents(struct btrfs_fs_info
*info
,
903 int ret
, i
, nr
, level
;
904 struct btrfs_root
*root
= info
->extent_root
;
905 struct btrfs_key key
;
906 struct btrfs_path path
;
907 struct btrfs_disk_key disk_key
;
908 struct extent_buffer
*leaf
;
909 u64 bytenr
= 0, num_bytes
= 0;
911 btrfs_init_path(&path
);
913 key
.objectid
= start
;
917 ret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
919 fprintf(stderr
, "ERROR: Couldn't search slot: %d\n", ret
);
925 leaf
= path
.nodes
[0];
927 nr
= btrfs_header_nritems(leaf
);
928 for(i
= 0; i
< nr
; i
++) {
929 btrfs_item_key(leaf
, &disk_key
, i
);
930 btrfs_disk_key_to_cpu(&key
, &disk_key
);
932 if (key
.objectid
< start
)
935 if (key
.objectid
> end
)
938 if (key
.type
== BTRFS_EXTENT_ITEM_KEY
||
939 key
.type
== BTRFS_METADATA_ITEM_KEY
) {
942 tot_extents_scanned
++;
944 bytenr
= key
.objectid
;
945 num_bytes
= key
.offset
;
946 if (key
.type
== BTRFS_METADATA_ITEM_KEY
) {
947 num_bytes
= info
->extent_root
->nodesize
;
951 ret
= add_inline_refs(info
, leaf
, i
, bytenr
,
956 level
= get_tree_block_level(&key
, leaf
, i
);
958 if (alloc_tree_block(bytenr
, num_bytes
,
966 if (key
.type
> BTRFS_SHARED_DATA_REF_KEY
)
968 if (key
.type
< BTRFS_TREE_BLOCK_REF_KEY
)
972 * Keyed refs should come after their extent
973 * item in the tree. As a result, the value of
974 * bytenr and num_bytes should be unchanged
975 * from the above block that catches the
976 * original extent item.
978 BUG_ON(key
.objectid
!= bytenr
);
980 ret
= add_keyed_ref(info
, &key
, leaf
, i
, bytenr
,
986 ret
= btrfs_next_leaf(root
, &path
);
990 "ERROR: Next leaf failed: %d\n", ret
);
999 btrfs_release_path(&path
);
1004 static void print_fields(u64 bytes
, u64 bytes_compressed
, char *prefix
,
1007 printf("%s\t\t%s %llu %s compressed %llu\n",
1008 prefix
, type
, (unsigned long long)bytes
, type
,
1009 (unsigned long long)bytes_compressed
);
1012 static void print_fields_signed(long long bytes
,
1013 long long bytes_compressed
,
1014 char *prefix
, char *type
)
1016 printf("%s\t\t%s %lld %s compressed %lld\n",
1017 prefix
, type
, bytes
, type
, bytes_compressed
);
1020 static void print_qgroup_difference(struct qgroup_count
*count
, int verbose
)
1023 struct qgroup_info
*info
= &count
->info
;
1024 struct qgroup_info
*disk
= &count
->diskinfo
;
1025 long long excl_diff
= info
->exclusive
- disk
->exclusive
;
1026 long long ref_diff
= info
->referenced
- disk
->referenced
;
1028 is_different
= excl_diff
|| ref_diff
;
1030 if (verbose
|| (is_different
&& count
->subvol_exists
)) {
1031 printf("Counts for qgroup id: %llu %s\n",
1032 (unsigned long long)count
->qgroupid
,
1033 is_different
? "are different" : "");
1035 print_fields(info
->referenced
, info
->referenced_compressed
,
1036 "our:", "referenced");
1037 print_fields(disk
->referenced
, disk
->referenced_compressed
,
1038 "disk:", "referenced");
1040 print_fields_signed(ref_diff
, ref_diff
,
1041 "diff:", "referenced");
1042 print_fields(info
->exclusive
, info
->exclusive_compressed
,
1043 "our:", "exclusive");
1044 print_fields(disk
->exclusive
, disk
->exclusive_compressed
,
1045 "disk:", "exclusive");
1047 print_fields_signed(excl_diff
, excl_diff
,
1048 "diff:", "exclusive");
1052 void print_qgroup_report(int all
)
1054 struct rb_node
*node
;
1055 struct qgroup_count
*c
;
1057 node
= rb_first(&counts
.root
);
1059 c
= rb_entry(node
, struct qgroup_count
, rb_node
);
1060 print_qgroup_difference(c
, all
);
1061 node
= rb_next(node
);
1065 int qgroup_verify_all(struct btrfs_fs_info
*info
)
1069 if (!info
->quota_enabled
)
1072 tree_blocks
= ulist_alloc(0);
1075 "ERROR: Out of memory while allocating ulist.\n");
1079 ret
= load_quota_info(info
);
1081 fprintf(stderr
, "ERROR: Loading qgroups from disk: %d\n", ret
);
1086 * Put all extent refs into our rbtree
1088 ret
= scan_extents(info
, 0, ~0ULL);
1090 fprintf(stderr
, "ERROR: while scanning extent tree: %d\n", ret
);
1094 ret
= map_implied_refs(info
);
1096 fprintf(stderr
, "ERROR: while mapping refs: %d\n", ret
);
1100 account_all_refs(1, 0);
1104 * Don't free the qgroup count records as they will be walked
1105 * later via the print function.
1108 free_ref_tree(&by_bytenr
);
1112 static void __print_subvol_info(u64 bytenr
, u64 num_bytes
, struct ulist
*roots
)
1114 int n
= roots
->nnodes
;
1115 struct ulist_iterator uiter
;
1116 struct ulist_node
*unode
;
1118 printf("%llu\t%llu\t%d\t", bytenr
, num_bytes
, n
);
1120 ULIST_ITER_INIT(&uiter
);
1121 while ((unode
= ulist_next(roots
, &uiter
))) {
1122 printf("%llu ", unode
->val
);
1127 static void print_subvol_info(u64 subvolid
, u64 bytenr
, u64 num_bytes
,
1128 struct ulist
*roots
)
1130 struct ulist_iterator uiter
;
1131 struct ulist_node
*unode
;
1133 ULIST_ITER_INIT(&uiter
);
1134 while ((unode
= ulist_next(roots
, &uiter
))) {
1135 BUG_ON(unode
->val
== 0ULL);
1136 if (unode
->val
== subvolid
) {
1137 __print_subvol_info(bytenr
, num_bytes
, roots
);
1145 int print_extent_state(struct btrfs_fs_info
*info
, u64 subvol
)
1149 tree_blocks
= ulist_alloc(0);
1152 "ERROR: Out of memory while allocating ulist.\n");
1157 * Put all extent refs into our rbtree
1159 ret
= scan_extents(info
, 0, ~0ULL);
1161 fprintf(stderr
, "ERROR: while scanning extent tree: %d\n", ret
);
1165 ret
= map_implied_refs(info
);
1167 fprintf(stderr
, "ERROR: while mapping refs: %d\n", ret
);
1171 printf("Offset\t\tLen\tRoot Refs\tRoots\n");
1172 account_all_refs(0, subvol
);
1176 free_ref_tree(&by_bytenr
);