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"
32 #include "transaction.h"
35 #include "qgroup-verify.h"
37 /*#define QGROUP_VERIFY_DEBUG*/
38 static unsigned long tot_extents_scanned
= 0;
41 static struct qgroup_count
*find_count(u64 qgroupid
);
45 u64 referenced_compressed
;
47 u64 exclusive_compressed
;
54 struct btrfs_disk_key key
;
55 struct qgroup_info diskinfo
;
57 struct qgroup_info info
;
59 struct rb_node rb_node
;
61 /* Parents when we are a child group */
62 struct list_head groups
;
65 * Children when we are a parent group (not currently used but
66 * maintained to mirror kernel handling of qgroups)
68 struct list_head members
;
72 struct list_head bad_list
;
75 static struct counts_tree
{
77 unsigned int num_groups
;
78 unsigned int rescan_running
:1;
79 unsigned int qgroup_inconsist
:1;
80 } counts
= { .root
= RB_ROOT
};
82 static LIST_HEAD(bad_qgroups
);
84 static struct rb_root by_bytenr
= RB_ROOT
;
87 * Glue structure to represent the relations between qgroups. Mirrored
90 struct btrfs_qgroup_list
{
91 struct list_head next_group
;
92 struct list_head next_member
;
93 struct qgroup_count
*group
; /* Parent group */
94 struct qgroup_count
*member
;
97 /* Allow us to reset ref counts during accounting without zeroing each group. */
98 static u64 qgroup_seq
= 1ULL;
100 static inline void update_cur_refcnt(struct qgroup_count
*c
)
102 if (c
->cur_refcnt
< qgroup_seq
)
103 c
->cur_refcnt
= qgroup_seq
;
107 static inline u64
group_get_cur_refcnt(struct qgroup_count
*c
)
109 if (c
->cur_refcnt
< qgroup_seq
)
111 return c
->cur_refcnt
- qgroup_seq
;
114 static void inc_qgroup_seq(int root_count
)
116 qgroup_seq
+= root_count
+ 1;
120 * List of interior tree blocks. We walk this list after loading the
121 * extent tree to resolve implied refs. For each interior node we'll
122 * place a shared ref in the ref tree against each child object. This
123 * allows the shared ref resolving code to do the actual work later of
124 * finding roots to account against.
126 * An implied ref is when a tree block has refs on it that may not
127 * exist in any of its child nodes. Even though the refs might not
128 * exist further down the tree, the fact that our interior node has a
129 * ref means we need to account anything below it to all its roots.
131 static struct ulist
*tree_blocks
= NULL
; /* unode->val = bytenr, ->aux
132 * = tree_block pointer */
144 struct rb_node bytenr_node
;
147 #ifdef QGROUP_VERIFY_DEBUG
148 static void print_ref(struct ref
*ref
)
150 printf("bytenr: %llu\t\tnum_bytes: %llu\t\t parent: %llu\t\t"
151 "root: %llu\n", ref
->bytenr
, ref
->num_bytes
,
152 ref
->parent
, ref
->root
);
155 static void print_all_refs(void)
157 unsigned long count
= 0;
159 struct rb_node
*node
;
161 node
= rb_first(&by_bytenr
);
163 ref
= rb_entry(node
, struct ref
, bytenr_node
);
168 node
= rb_next(node
);
171 printf("%lu extents scanned with %lu refs in total.\n",
172 tot_extents_scanned
, count
);
177 * Store by bytenr in rbtree
179 * The tree is sorted in ascending order by bytenr, then parent, then
180 * root. Since full refs have a parent == 0, those will come before
183 static int compare_ref(struct ref
*orig
, u64 bytenr
, u64 root
, u64 parent
)
185 if (bytenr
< orig
->bytenr
)
187 if (bytenr
> orig
->bytenr
)
190 if (parent
< orig
->parent
)
192 if (parent
> orig
->parent
)
195 if (root
< orig
->root
)
197 if (root
> orig
->root
)
204 * insert a new ref into the tree. returns the existing ref entry
205 * if one is already there.
207 static struct ref
*insert_ref(struct ref
*ref
)
210 struct rb_node
**p
= &by_bytenr
.rb_node
;
211 struct rb_node
*parent
= NULL
;
216 curr
= rb_entry(parent
, struct ref
, bytenr_node
);
218 ret
= compare_ref(curr
, ref
->bytenr
, ref
->root
, ref
->parent
);
227 rb_link_node(&ref
->bytenr_node
, parent
, p
);
228 rb_insert_color(&ref
->bytenr_node
, &by_bytenr
);
233 * Partial search, returns the first ref with matching bytenr. Caller
234 * can walk forward from there.
236 * Leftmost refs will be full refs - this is used to our advantage
237 * when resolving roots.
239 static struct ref
*find_ref_bytenr(u64 bytenr
)
241 struct rb_node
*n
= by_bytenr
.rb_node
;
245 ref
= rb_entry(n
, struct ref
, bytenr_node
);
247 if (bytenr
< ref
->bytenr
)
249 else if (bytenr
> ref
->bytenr
)
252 /* Walk to the left to find the first item */
253 struct rb_node
*node_left
= rb_prev(&ref
->bytenr_node
);
254 struct ref
*ref_left
;
257 ref_left
= rb_entry(node_left
, struct ref
,
259 if (ref_left
->bytenr
!= ref
->bytenr
)
262 node_left
= rb_prev(node_left
);
270 static struct ref
*find_ref(u64 bytenr
, u64 root
, u64 parent
)
272 struct rb_node
*n
= by_bytenr
.rb_node
;
277 ref
= rb_entry(n
, struct ref
, bytenr_node
);
279 ret
= compare_ref(ref
, bytenr
, root
, parent
);
290 static struct ref
*alloc_ref(u64 bytenr
, u64 root
, u64 parent
, u64 num_bytes
)
292 struct ref
*ref
= find_ref(bytenr
, root
, parent
);
294 BUG_ON(parent
&& root
);
297 ref
= calloc(1, sizeof(*ref
));
299 ref
->bytenr
= bytenr
;
301 ref
->parent
= parent
;
302 ref
->num_bytes
= num_bytes
;
310 static void free_ref_node(struct rb_node
*node
)
312 struct ref
*ref
= rb_entry(node
, struct ref
, bytenr_node
);
316 FREE_RB_BASED_TREE(ref
, free_ref_node
);
319 * Resolves all the possible roots for the ref at parent.
321 static int find_parent_roots(struct ulist
*roots
, u64 parent
)
324 struct rb_node
*node
;
328 * Search the rbtree for the first ref with bytenr == parent.
329 * Walk forward so long as bytenr == parent, adding resolved root ids.
330 * For each unresolved root, we recurse
332 ref
= find_ref_bytenr(parent
);
333 node
= &ref
->bytenr_node
;
335 BUG_ON(ref
->bytenr
!= parent
);
339 * Random sanity check, are we actually getting the
342 struct rb_node
*prev_node
= rb_prev(&ref
->bytenr_node
);
345 prev
= rb_entry(prev_node
, struct ref
, bytenr_node
);
346 BUG_ON(prev
->bytenr
== parent
);
352 if (is_fstree(ref
->root
)) {
353 ret
= ulist_add(roots
, ref
->root
, 0, 0);
358 ret
= find_parent_roots(roots
, ref
->parent
);
363 node
= rb_next(node
);
365 ref
= rb_entry(node
, struct ref
, bytenr_node
);
366 } while (node
&& ref
->bytenr
== parent
);
373 static int account_one_extent(struct ulist
*roots
, u64 bytenr
, u64 num_bytes
)
376 u64 id
, nr_roots
, nr_refs
;
377 struct qgroup_count
*count
;
378 struct ulist
*counts
= ulist_alloc(0);
379 struct ulist
*tmp
= ulist_alloc(0);
380 struct ulist_iterator uiter
;
381 struct ulist_iterator tmp_uiter
;
382 struct ulist_node
*unode
;
383 struct ulist_node
*tmp_unode
;
384 struct btrfs_qgroup_list
*glist
;
386 if (!counts
|| !tmp
) {
392 ULIST_ITER_INIT(&uiter
);
393 while ((unode
= ulist_next(roots
, &uiter
))) {
394 BUG_ON(unode
->val
== 0ULL);
397 * For each root, find their corresponding tracking group and
398 * add it to our qgroups list.
400 count
= find_count(unode
->val
);
404 BUG_ON(!is_fstree(unode
->val
));
405 ret
= ulist_add(counts
, count
->qgroupid
, ptr_to_u64(count
), 0);
410 * Now we look for parents (and parents of those...). Use a tmp
411 * ulist here to avoid re-walking (and re-incrementing) our
412 * already added items on every loop iteration.
415 ret
= ulist_add(tmp
, count
->qgroupid
, ptr_to_u64(count
), 0);
419 ULIST_ITER_INIT(&tmp_uiter
);
420 while ((tmp_unode
= ulist_next(tmp
, &tmp_uiter
))) {
421 /* Bump the refcount on a node every time we see it. */
422 count
= u64_to_ptr(tmp_unode
->aux
);
423 update_cur_refcnt(count
);
425 list_for_each_entry(glist
, &count
->groups
, next_group
) {
426 struct qgroup_count
*parent
;
427 parent
= glist
->group
;
428 id
= parent
->qgroupid
;
432 ret
= ulist_add(counts
, id
, ptr_to_u64(parent
),
436 ret
= ulist_add(tmp
, id
, ptr_to_u64(parent
),
445 * Now that we have gathered up and counted all the groups, we
446 * can add bytes for this ref.
448 nr_roots
= roots
->nnodes
;
449 ULIST_ITER_INIT(&uiter
);
450 while ((unode
= ulist_next(counts
, &uiter
))) {
451 count
= u64_to_ptr(unode
->aux
);
453 nr_refs
= group_get_cur_refcnt(count
);
455 count
->info
.referenced
+= num_bytes
;
456 count
->info
.referenced_compressed
+= num_bytes
;
458 if (nr_refs
== nr_roots
) {
459 count
->info
.exclusive
+= num_bytes
;
460 count
->info
.exclusive_compressed
+= num_bytes
;
463 #ifdef QGROUP_VERIFY_DEBUG
464 printf("account (%llu, %llu), qgroup %llu/%llu, rfer %llu,"
465 " excl %llu, refs %llu, roots %llu\n", bytenr
, num_bytes
,
466 btrfs_qgroup_level(count
->qgroupid
),
467 btrfs_qgroup_subvid(count
->qgroupid
),
468 count
->info
.referenced
, count
->info
.exclusive
, nr_refs
,
473 inc_qgroup_seq(roots
->nnodes
);
481 static void print_subvol_info(u64 subvolid
, u64 bytenr
, u64 num_bytes
,
482 struct ulist
*roots
);
484 * Account each ref. Walk the refs, for each set of refs in a
487 * - add the roots for direct refs to the ref roots ulist
489 * - resolve all possible roots for shared refs, insert each
490 * of those into ref_roots ulist (this is a recursive process)
492 * - With all roots resolved we can account the ref - this is done in
493 * account_one_extent().
495 static int account_all_refs(int do_qgroups
, u64 search_subvol
)
498 struct rb_node
*node
;
499 u64 bytenr
, num_bytes
;
500 struct ulist
*roots
= ulist_alloc(0);
503 node
= rb_first(&by_bytenr
);
507 ref
= rb_entry(node
, struct ref
, bytenr_node
);
509 * Walk forward through the list of refs for this
510 * bytenr, adding roots to our ulist. If it's a full
511 * ref, then we have the easy case. Otherwise we need
512 * to search for roots.
514 bytenr
= ref
->bytenr
;
515 num_bytes
= ref
->num_bytes
;
517 BUG_ON(ref
->bytenr
!= bytenr
);
518 BUG_ON(ref
->num_bytes
!= num_bytes
);
520 if (is_fstree(ref
->root
)) {
521 if (ulist_add(roots
, ref
->root
, 0, 0) < 0)
525 ret
= find_parent_roots(roots
, ref
->parent
);
531 * When we leave this inner loop, node is set
532 * to next in our tree and will be turned into
533 * a ref object up top
535 node
= rb_next(node
);
537 ref
= rb_entry(node
, struct ref
, bytenr_node
);
538 } while (node
&& ref
->bytenr
== bytenr
);
541 print_subvol_info(search_subvol
, bytenr
, num_bytes
,
547 if (account_one_extent(roots
, bytenr
, num_bytes
))
554 error("Out of memory while accounting refs for qgroups");
558 static u64
resolve_one_root(u64 bytenr
)
560 struct ref
*ref
= find_ref_bytenr(bytenr
);
566 return resolve_one_root(ref
->parent
);
569 static inline struct tree_block
*unode_tree_block(struct ulist_node
*unode
)
571 return u64_to_ptr(unode
->aux
);
573 static inline u64
unode_bytenr(struct ulist_node
*unode
)
578 static int alloc_tree_block(u64 bytenr
, u64 num_bytes
, int level
)
580 struct tree_block
*block
= calloc(1, sizeof(*block
));
583 block
->num_bytes
= num_bytes
;
584 block
->level
= level
;
585 if (ulist_add(tree_blocks
, bytenr
, ptr_to_u64(block
), 0) >= 0)
592 static void free_tree_blocks(void)
594 struct ulist_iterator uiter
;
595 struct ulist_node
*unode
;
600 ULIST_ITER_INIT(&uiter
);
601 while ((unode
= ulist_next(tree_blocks
, &uiter
)))
602 free(unode_tree_block(unode
));
603 ulist_free(tree_blocks
);
607 #ifdef QGROUP_VERIFY_DEBUG
608 static void print_tree_block(u64 bytenr
, struct tree_block
*block
)
611 struct rb_node
*node
;
613 printf("tree block: %llu\t\tlevel: %d\n", (unsigned long long)bytenr
,
616 ref
= find_ref_bytenr(bytenr
);
617 node
= &ref
->bytenr_node
;
620 node
= rb_next(node
);
622 ref
= rb_entry(node
, struct ref
, bytenr_node
);
623 } while (node
&& ref
->bytenr
== bytenr
);
628 static void print_all_tree_blocks(void)
630 struct ulist_iterator uiter
;
631 struct ulist_node
*unode
;
636 printf("Listing all found interior tree nodes:\n");
638 ULIST_ITER_INIT(&uiter
);
639 while ((unode
= ulist_next(tree_blocks
, &uiter
)))
640 print_tree_block(unode_bytenr(unode
), unode_tree_block(unode
));
644 static int add_refs_for_leaf_items(struct extent_buffer
*eb
, u64 ref_parent
)
648 u64 bytenr
, num_bytes
;
649 struct btrfs_key key
;
650 struct btrfs_disk_key disk_key
;
651 struct btrfs_file_extent_item
*fi
;
653 nr
= btrfs_header_nritems(eb
);
654 for (i
= 0; i
< nr
; i
++) {
655 btrfs_item_key(eb
, &disk_key
, i
);
656 btrfs_disk_key_to_cpu(&key
, &disk_key
);
658 if (key
.type
!= BTRFS_EXTENT_DATA_KEY
)
661 fi
= btrfs_item_ptr(eb
, i
, struct btrfs_file_extent_item
);
662 /* filter out: inline, disk_bytenr == 0, compressed?
663 * not if we can avoid it */
664 extent_type
= btrfs_file_extent_type(eb
, fi
);
666 if (extent_type
== BTRFS_FILE_EXTENT_INLINE
)
669 bytenr
= btrfs_file_extent_disk_bytenr(eb
, fi
);
673 num_bytes
= btrfs_file_extent_disk_num_bytes(eb
, fi
);
674 if (alloc_ref(bytenr
, 0, ref_parent
, num_bytes
) == NULL
)
681 static int travel_tree(struct btrfs_fs_info
*info
, struct btrfs_root
*root
,
682 u64 bytenr
, u64 num_bytes
, u64 ref_parent
)
685 struct extent_buffer
*eb
;
689 // printf("travel_tree: bytenr: %llu\tnum_bytes: %llu\tref_parent: %llu\n",
690 // bytenr, num_bytes, ref_parent);
692 eb
= read_tree_block(root
, bytenr
, num_bytes
, 0);
693 if (!extent_buffer_uptodate(eb
))
697 /* Don't add a ref for our starting tree block to itself */
698 if (bytenr
!= ref_parent
) {
699 if (alloc_ref(bytenr
, 0, ref_parent
, num_bytes
) == NULL
)
703 if (btrfs_is_leaf(eb
)) {
704 ret
= add_refs_for_leaf_items(eb
, ref_parent
);
709 * Interior nodes are tuples of (key, bytenr) where key is the
710 * leftmost key in the tree block pointed to by bytenr. We
711 * don't have to care about key here, just follow the bytenr
714 nr
= btrfs_header_nritems(eb
);
715 for (i
= 0; i
< nr
; i
++) {
716 new_bytenr
= btrfs_node_blockptr(eb
, i
);
717 new_num_bytes
= root
->nodesize
;
719 ret
= travel_tree(info
, root
, new_bytenr
, new_num_bytes
,
724 free_extent_buffer(eb
);
728 static int add_refs_for_implied(struct btrfs_fs_info
*info
, u64 bytenr
,
729 struct tree_block
*block
)
732 u64 root_id
= resolve_one_root(bytenr
);
733 struct btrfs_root
*root
;
734 struct btrfs_key key
;
736 key
.objectid
= root_id
;
737 key
.type
= BTRFS_ROOT_ITEM_KEY
;
738 key
.offset
= (u64
)-1;
741 * XXX: Don't free the root object as we don't know whether it
742 * came off our fs_info struct or not.
744 root
= btrfs_read_fs_root(info
, &key
);
745 if (!root
|| IS_ERR(root
))
748 ret
= travel_tree(info
, root
, bytenr
, block
->num_bytes
, bytenr
);
756 * Place shared refs in the ref tree for each child of an interior tree node.
758 static int map_implied_refs(struct btrfs_fs_info
*info
)
761 struct ulist_iterator uiter
;
762 struct ulist_node
*unode
;
764 ULIST_ITER_INIT(&uiter
);
765 while ((unode
= ulist_next(tree_blocks
, &uiter
))) {
766 ret
= add_refs_for_implied(info
, unode_bytenr(unode
),
767 unode_tree_block(unode
));
776 * insert a new root into the tree. returns the existing root entry
777 * if one is already there. qgroupid is used
780 static int insert_count(struct qgroup_count
*qc
)
782 struct rb_node
**p
= &counts
.root
.rb_node
;
783 struct rb_node
*parent
= NULL
;
784 struct qgroup_count
*curr
;
788 curr
= rb_entry(parent
, struct qgroup_count
, rb_node
);
790 if (qc
->qgroupid
< curr
->qgroupid
)
792 else if (qc
->qgroupid
> curr
->qgroupid
)
798 rb_link_node(&qc
->rb_node
, parent
, p
);
799 rb_insert_color(&qc
->rb_node
, &counts
.root
);
803 static struct qgroup_count
*find_count(u64 qgroupid
)
805 struct rb_node
*n
= counts
.root
.rb_node
;
806 struct qgroup_count
*count
;
809 count
= rb_entry(n
, struct qgroup_count
, rb_node
);
811 if (qgroupid
< count
->qgroupid
)
813 else if (qgroupid
> count
->qgroupid
)
821 static struct qgroup_count
*alloc_count(struct btrfs_disk_key
*key
,
822 struct extent_buffer
*leaf
,
823 struct btrfs_qgroup_info_item
*disk
)
825 struct qgroup_count
*c
= calloc(1, sizeof(*c
));
826 struct qgroup_info
*item
;
829 c
->qgroupid
= btrfs_disk_key_offset(key
);
833 item
->referenced
= btrfs_qgroup_info_referenced(leaf
, disk
);
834 item
->referenced_compressed
=
835 btrfs_qgroup_info_referenced_compressed(leaf
, disk
);
836 item
->exclusive
= btrfs_qgroup_info_exclusive(leaf
, disk
);
837 item
->exclusive_compressed
=
838 btrfs_qgroup_info_exclusive_compressed(leaf
, disk
);
839 INIT_LIST_HEAD(&c
->groups
);
840 INIT_LIST_HEAD(&c
->members
);
841 INIT_LIST_HEAD(&c
->bad_list
);
843 if (insert_count(c
)) {
851 static int add_qgroup_relation(u64 memberid
, u64 parentid
)
853 struct qgroup_count
*member
;
854 struct qgroup_count
*parent
;
855 struct btrfs_qgroup_list
*list
;
857 if (memberid
> parentid
)
860 member
= find_count(memberid
);
861 parent
= find_count(parentid
);
862 if (!member
|| !parent
)
865 list
= calloc(1, sizeof(*list
));
869 list
->group
= parent
;
870 list
->member
= member
;
871 list_add_tail(&list
->next_group
, &member
->groups
);
872 list_add_tail(&list
->next_member
, &parent
->members
);
877 static void read_qgroup_status(struct btrfs_path
*path
,
878 struct counts_tree
*counts
)
880 struct btrfs_qgroup_status_item
*status_item
;
883 status_item
= btrfs_item_ptr(path
->nodes
[0], path
->slots
[0],
884 struct btrfs_qgroup_status_item
);
885 flags
= btrfs_qgroup_status_flags(path
->nodes
[0], status_item
);
887 * Since qgroup_inconsist/rescan_running is just one bit,
888 * assign value directly won't work.
890 counts
->qgroup_inconsist
= !!(flags
&
891 BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT
);
892 counts
->rescan_running
= !!(flags
& BTRFS_QGROUP_STATUS_FLAG_RESCAN
);
895 static int load_quota_info(struct btrfs_fs_info
*info
)
898 struct btrfs_root
*root
= info
->quota_root
;
899 struct btrfs_root
*tmproot
;
900 struct btrfs_path path
;
901 struct btrfs_key key
;
902 struct btrfs_key root_key
;
903 struct btrfs_disk_key disk_key
;
904 struct extent_buffer
*leaf
;
905 struct btrfs_qgroup_info_item
*item
;
906 struct qgroup_count
*count
;
908 int search_relations
= 0;
912 * Do 2 passes, the first allocates group counts and reads status
913 * items. The 2nd pass picks up relation items and glues them to their
914 * respective count structures.
916 btrfs_init_path(&path
);
919 key
.objectid
= search_relations
? 0 : BTRFS_QGROUP_RELATION_KEY
;
922 ret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
924 fprintf(stderr
, "ERROR: Couldn't search slot: %d\n", ret
);
929 leaf
= path
.nodes
[0];
931 nr
= btrfs_header_nritems(leaf
);
932 for(i
= 0; i
< nr
; i
++) {
933 btrfs_item_key(leaf
, &disk_key
, i
);
934 btrfs_disk_key_to_cpu(&key
, &disk_key
);
936 if (search_relations
) {
937 if (key
.type
== BTRFS_QGROUP_RELATION_KEY
) {
938 ret
= add_qgroup_relation(key
.objectid
,
941 error("out of memory");
948 if (key
.type
== BTRFS_QGROUP_STATUS_KEY
) {
949 read_qgroup_status(&path
, &counts
);
954 * At this point, we can ignore anything that
955 * isn't a qgroup info.
957 if (key
.type
!= BTRFS_QGROUP_INFO_KEY
)
960 item
= btrfs_item_ptr(leaf
, i
,
961 struct btrfs_qgroup_info_item
);
963 count
= alloc_count(&disk_key
, leaf
, item
);
966 fprintf(stderr
, "ERROR: out of memory\n");
970 root_key
.objectid
= key
.offset
;
971 root_key
.type
= BTRFS_ROOT_ITEM_KEY
;
972 root_key
.offset
= (u64
)-1;
973 tmproot
= btrfs_read_fs_root_no_cache(info
, &root_key
);
974 if (tmproot
&& !IS_ERR(tmproot
)) {
975 count
->subvol_exists
= 1;
976 btrfs_free_fs_root(tmproot
);
980 ret
= btrfs_next_leaf(root
, &path
);
986 btrfs_release_path(&path
);
988 if (!search_relations
) {
989 search_relations
= 1;
997 static int add_inline_refs(struct btrfs_fs_info
*info
,
998 struct extent_buffer
*ei_leaf
, int slot
,
999 u64 bytenr
, u64 num_bytes
, int meta_item
)
1001 struct btrfs_extent_item
*ei
;
1002 struct btrfs_extent_inline_ref
*iref
;
1003 struct btrfs_extent_data_ref
*dref
;
1004 u64 flags
, root_obj
, offset
, parent
;
1005 u32 item_size
= btrfs_item_size_nr(ei_leaf
, slot
);
1010 ei
= btrfs_item_ptr(ei_leaf
, slot
, struct btrfs_extent_item
);
1011 flags
= btrfs_extent_flags(ei_leaf
, ei
);
1013 if (flags
& BTRFS_EXTENT_FLAG_TREE_BLOCK
&& !meta_item
) {
1014 struct btrfs_tree_block_info
*tbinfo
;
1015 tbinfo
= (struct btrfs_tree_block_info
*)(ei
+ 1);
1016 iref
= (struct btrfs_extent_inline_ref
*)(tbinfo
+ 1);
1018 iref
= (struct btrfs_extent_inline_ref
*)(ei
+ 1);
1021 ptr
= (unsigned long)iref
;
1022 end
= (unsigned long)ei
+ item_size
;
1024 iref
= (struct btrfs_extent_inline_ref
*)ptr
;
1026 parent
= root_obj
= 0;
1027 offset
= btrfs_extent_inline_ref_offset(ei_leaf
, iref
);
1028 type
= btrfs_extent_inline_ref_type(ei_leaf
, iref
);
1030 case BTRFS_TREE_BLOCK_REF_KEY
:
1033 case BTRFS_EXTENT_DATA_REF_KEY
:
1034 dref
= (struct btrfs_extent_data_ref
*)(&iref
->offset
);
1035 root_obj
= btrfs_extent_data_ref_root(ei_leaf
, dref
);
1037 case BTRFS_SHARED_DATA_REF_KEY
:
1038 case BTRFS_SHARED_BLOCK_REF_KEY
:
1045 if (alloc_ref(bytenr
, root_obj
, parent
, num_bytes
) == NULL
)
1048 ptr
+= btrfs_extent_inline_ref_size(type
);
1054 static int add_keyed_ref(struct btrfs_fs_info
*info
,
1055 struct btrfs_key
*key
,
1056 struct extent_buffer
*leaf
, int slot
,
1057 u64 bytenr
, u64 num_bytes
)
1059 u64 root_obj
= 0, parent
= 0;
1060 struct btrfs_extent_data_ref
*dref
;
1063 case BTRFS_TREE_BLOCK_REF_KEY
:
1064 root_obj
= key
->offset
;
1066 case BTRFS_EXTENT_DATA_REF_KEY
:
1067 dref
= btrfs_item_ptr(leaf
, slot
, struct btrfs_extent_data_ref
);
1068 root_obj
= btrfs_extent_data_ref_root(leaf
, dref
);
1070 case BTRFS_SHARED_DATA_REF_KEY
:
1071 case BTRFS_SHARED_BLOCK_REF_KEY
:
1072 parent
= key
->offset
;
1078 if (alloc_ref(bytenr
, root_obj
, parent
, num_bytes
) == NULL
)
1085 * return value of 0 indicates leaf or not meta data. The code that
1086 * calls this does not need to make a distinction between the two as
1087 * it is only concerned with intermediate blocks which will always
1090 static int get_tree_block_level(struct btrfs_key
*key
,
1091 struct extent_buffer
*ei_leaf
,
1095 int meta_key
= key
->type
== BTRFS_METADATA_ITEM_KEY
;
1097 struct btrfs_extent_item
*ei
;
1099 ei
= btrfs_item_ptr(ei_leaf
, slot
, struct btrfs_extent_item
);
1100 flags
= btrfs_extent_flags(ei_leaf
, ei
);
1102 if (flags
& BTRFS_EXTENT_FLAG_TREE_BLOCK
&& !meta_key
) {
1103 struct btrfs_tree_block_info
*tbinfo
;
1104 tbinfo
= (struct btrfs_tree_block_info
*)(ei
+ 1);
1105 level
= btrfs_tree_block_level(ei_leaf
, tbinfo
);
1106 } else if (meta_key
) {
1107 /* skinny metadata */
1108 level
= (int)key
->offset
;
1114 * Walk the extent tree, allocating a ref item for every ref and
1115 * storing it in the bytenr tree.
1117 static int scan_extents(struct btrfs_fs_info
*info
,
1120 int ret
, i
, nr
, level
;
1121 struct btrfs_root
*root
= info
->extent_root
;
1122 struct btrfs_key key
;
1123 struct btrfs_path path
;
1124 struct btrfs_disk_key disk_key
;
1125 struct extent_buffer
*leaf
;
1126 u64 bytenr
= 0, num_bytes
= 0;
1128 btrfs_init_path(&path
);
1130 key
.objectid
= start
;
1134 ret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
1136 fprintf(stderr
, "ERROR: Couldn't search slot: %d\n", ret
);
1142 leaf
= path
.nodes
[0];
1144 nr
= btrfs_header_nritems(leaf
);
1145 for(i
= 0; i
< nr
; i
++) {
1146 btrfs_item_key(leaf
, &disk_key
, i
);
1147 btrfs_disk_key_to_cpu(&key
, &disk_key
);
1149 if (key
.objectid
< start
)
1152 if (key
.objectid
> end
)
1155 if (key
.type
== BTRFS_EXTENT_ITEM_KEY
||
1156 key
.type
== BTRFS_METADATA_ITEM_KEY
) {
1159 tot_extents_scanned
++;
1161 bytenr
= key
.objectid
;
1162 num_bytes
= key
.offset
;
1163 if (key
.type
== BTRFS_METADATA_ITEM_KEY
) {
1164 num_bytes
= info
->extent_root
->nodesize
;
1168 ret
= add_inline_refs(info
, leaf
, i
, bytenr
,
1173 level
= get_tree_block_level(&key
, leaf
, i
);
1175 if (alloc_tree_block(bytenr
, num_bytes
,
1183 if (key
.type
> BTRFS_SHARED_DATA_REF_KEY
)
1185 if (key
.type
< BTRFS_TREE_BLOCK_REF_KEY
)
1189 * Keyed refs should come after their extent
1190 * item in the tree. As a result, the value of
1191 * bytenr and num_bytes should be unchanged
1192 * from the above block that catches the
1193 * original extent item.
1195 BUG_ON(key
.objectid
!= bytenr
);
1197 ret
= add_keyed_ref(info
, &key
, leaf
, i
, bytenr
,
1203 ret
= btrfs_next_leaf(root
, &path
);
1207 "ERROR: Next leaf failed: %d\n", ret
);
1216 btrfs_release_path(&path
);
1221 static void print_fields(u64 bytes
, u64 bytes_compressed
, char *prefix
,
1224 printf("%s\t\t%s %llu %s compressed %llu\n",
1225 prefix
, type
, (unsigned long long)bytes
, type
,
1226 (unsigned long long)bytes_compressed
);
1229 static void print_fields_signed(long long bytes
,
1230 long long bytes_compressed
,
1231 char *prefix
, char *type
)
1233 printf("%s\t\t%s %lld %s compressed %lld\n",
1234 prefix
, type
, bytes
, type
, bytes_compressed
);
1237 static inline int qgroup_printable(struct qgroup_count
*c
)
1239 return !!(c
->subvol_exists
|| btrfs_qgroup_level(c
->qgroupid
));
1242 static int report_qgroup_difference(struct qgroup_count
*count
, int verbose
)
1245 struct qgroup_info
*info
= &count
->info
;
1246 struct qgroup_info
*disk
= &count
->diskinfo
;
1247 long long excl_diff
= info
->exclusive
- disk
->exclusive
;
1248 long long ref_diff
= info
->referenced
- disk
->referenced
;
1250 is_different
= excl_diff
|| ref_diff
;
1252 if (verbose
|| (is_different
&& qgroup_printable(count
))) {
1253 printf("Counts for qgroup id: %llu/%llu %s\n",
1254 btrfs_qgroup_level(count
->qgroupid
),
1255 btrfs_qgroup_subvid(count
->qgroupid
),
1256 is_different
? "are different" : "");
1258 print_fields(info
->referenced
, info
->referenced_compressed
,
1259 "our:", "referenced");
1260 print_fields(disk
->referenced
, disk
->referenced_compressed
,
1261 "disk:", "referenced");
1263 print_fields_signed(ref_diff
, ref_diff
,
1264 "diff:", "referenced");
1265 print_fields(info
->exclusive
, info
->exclusive_compressed
,
1266 "our:", "exclusive");
1267 print_fields(disk
->exclusive
, disk
->exclusive_compressed
,
1268 "disk:", "exclusive");
1270 print_fields_signed(excl_diff
, excl_diff
,
1271 "diff:", "exclusive");
1274 return is_different
;
1277 void report_qgroups(int all
)
1279 struct rb_node
*node
;
1280 struct qgroup_count
*c
;
1282 if (!repair
&& counts
.rescan_running
) {
1285 "Qgroup rescan is running, a difference in qgroup counts is expected\n");
1288 "Qgroup rescan is running, qgroups will not be printed.\n");
1292 if (counts
.qgroup_inconsist
&& !counts
.rescan_running
)
1293 fprintf(stderr
, "Qgroup are marked as inconsistent.\n");
1294 node
= rb_first(&counts
.root
);
1296 c
= rb_entry(node
, struct qgroup_count
, rb_node
);
1298 if (report_qgroup_difference(c
, all
))
1299 list_add_tail(&c
->bad_list
, &bad_qgroups
);
1301 node
= rb_next(node
);
1305 void free_qgroup_counts(void)
1307 struct rb_node
*node
;
1308 struct qgroup_count
*c
;
1309 struct btrfs_qgroup_list
*glist
, *tmpglist
;
1311 node
= rb_first(&counts
.root
);
1313 c
= rb_entry(node
, struct qgroup_count
, rb_node
);
1315 list_del(&c
->bad_list
);
1317 list_for_each_entry_safe(glist
, tmpglist
, &c
->groups
,
1319 list_del(&glist
->next_group
);
1320 list_del(&glist
->next_member
);
1323 list_for_each_entry_safe(glist
, tmpglist
, &c
->members
,
1325 list_del(&glist
->next_group
);
1326 list_del(&glist
->next_member
);
1330 node
= rb_next(node
);
1332 rb_erase(&c
->rb_node
, &counts
.root
);
1337 int qgroup_verify_all(struct btrfs_fs_info
*info
)
1341 if (!info
->quota_enabled
)
1344 tree_blocks
= ulist_alloc(0);
1347 "ERROR: Out of memory while allocating ulist.\n");
1351 ret
= load_quota_info(info
);
1353 fprintf(stderr
, "ERROR: Loading qgroups from disk: %d\n", ret
);
1358 * Put all extent refs into our rbtree
1360 ret
= scan_extents(info
, 0, ~0ULL);
1362 fprintf(stderr
, "ERROR: while scanning extent tree: %d\n", ret
);
1366 ret
= map_implied_refs(info
);
1368 fprintf(stderr
, "ERROR: while mapping refs: %d\n", ret
);
1372 ret
= account_all_refs(1, 0);
1376 * Don't free the qgroup count records as they will be walked
1377 * later via the print function.
1380 free_ref_tree(&by_bytenr
);
1384 static void __print_subvol_info(u64 bytenr
, u64 num_bytes
, struct ulist
*roots
)
1386 int n
= roots
->nnodes
;
1387 struct ulist_iterator uiter
;
1388 struct ulist_node
*unode
;
1390 printf("%llu\t%llu\t%d\t", bytenr
, num_bytes
, n
);
1392 ULIST_ITER_INIT(&uiter
);
1393 while ((unode
= ulist_next(roots
, &uiter
))) {
1394 printf("%llu ", unode
->val
);
1399 static void print_subvol_info(u64 subvolid
, u64 bytenr
, u64 num_bytes
,
1400 struct ulist
*roots
)
1402 struct ulist_iterator uiter
;
1403 struct ulist_node
*unode
;
1405 ULIST_ITER_INIT(&uiter
);
1406 while ((unode
= ulist_next(roots
, &uiter
))) {
1407 BUG_ON(unode
->val
== 0ULL);
1408 if (unode
->val
== subvolid
) {
1409 __print_subvol_info(bytenr
, num_bytes
, roots
);
1417 int print_extent_state(struct btrfs_fs_info
*info
, u64 subvol
)
1421 tree_blocks
= ulist_alloc(0);
1424 "ERROR: Out of memory while allocating ulist.\n");
1429 * Put all extent refs into our rbtree
1431 ret
= scan_extents(info
, 0, ~0ULL);
1433 fprintf(stderr
, "ERROR: while scanning extent tree: %d\n", ret
);
1437 ret
= map_implied_refs(info
);
1439 fprintf(stderr
, "ERROR: while mapping refs: %d\n", ret
);
1443 printf("Offset\t\tLen\tRoot Refs\tRoots\n");
1444 ret
= account_all_refs(0, subvol
);
1448 free_ref_tree(&by_bytenr
);
1452 static int repair_qgroup_info(struct btrfs_fs_info
*info
,
1453 struct qgroup_count
*count
)
1456 struct btrfs_root
*root
= info
->quota_root
;
1457 struct btrfs_trans_handle
*trans
;
1458 struct btrfs_path
*path
;
1459 struct btrfs_qgroup_info_item
*info_item
;
1460 struct btrfs_key key
;
1462 printf("Repair qgroup %llu/%llu\n", btrfs_qgroup_level(count
->qgroupid
),
1463 btrfs_qgroup_subvid(count
->qgroupid
));
1465 path
= btrfs_alloc_path();
1469 trans
= btrfs_start_transaction(root
, 1);
1470 if (IS_ERR(trans
)) {
1471 btrfs_free_path(path
);
1472 return PTR_ERR(trans
);
1476 key
.type
= BTRFS_QGROUP_INFO_KEY
;
1477 key
.offset
= count
->qgroupid
;
1478 ret
= btrfs_search_slot(trans
, root
, &key
, path
, 0, 1);
1480 error("Could not find disk item for qgroup %llu/%llu.\n",
1481 btrfs_qgroup_level(count
->qgroupid
),
1482 btrfs_qgroup_subvid(count
->qgroupid
));
1488 info_item
= btrfs_item_ptr(path
->nodes
[0], path
->slots
[0],
1489 struct btrfs_qgroup_info_item
);
1491 btrfs_set_qgroup_info_generation(path
->nodes
[0], info_item
,
1494 btrfs_set_qgroup_info_referenced(path
->nodes
[0], info_item
,
1495 count
->info
.referenced
);
1496 btrfs_set_qgroup_info_referenced_compressed(path
->nodes
[0], info_item
,
1497 count
->info
.referenced_compressed
);
1499 btrfs_set_qgroup_info_exclusive(path
->nodes
[0], info_item
,
1500 count
->info
.exclusive
);
1501 btrfs_set_qgroup_info_exclusive_compressed(path
->nodes
[0], info_item
,
1502 count
->info
.exclusive_compressed
);
1504 btrfs_mark_buffer_dirty(path
->nodes
[0]);
1507 btrfs_commit_transaction(trans
, root
);
1508 btrfs_free_path(path
);
1513 static int repair_qgroup_status(struct btrfs_fs_info
*info
)
1516 struct btrfs_root
*root
= info
->quota_root
;
1517 struct btrfs_trans_handle
*trans
;
1518 struct btrfs_path
*path
;
1519 struct btrfs_key key
;
1520 struct btrfs_qgroup_status_item
*status_item
;
1522 printf("Repair qgroup status item\n");
1524 path
= btrfs_alloc_path();
1528 trans
= btrfs_start_transaction(root
, 1);
1529 if (IS_ERR(trans
)) {
1530 btrfs_free_path(path
);
1531 return PTR_ERR(trans
);
1535 key
.type
= BTRFS_QGROUP_STATUS_KEY
;
1537 ret
= btrfs_search_slot(trans
, root
, &key
, path
, 0, 1);
1539 error("Could not find qgroup status item\n");
1545 status_item
= btrfs_item_ptr(path
->nodes
[0], path
->slots
[0],
1546 struct btrfs_qgroup_status_item
);
1547 btrfs_set_qgroup_status_flags(path
->nodes
[0], status_item
,
1548 BTRFS_QGROUP_STATUS_FLAG_ON
);
1549 btrfs_set_qgroup_status_rescan(path
->nodes
[0], status_item
, 0);
1550 btrfs_set_qgroup_status_generation(path
->nodes
[0], status_item
,
1553 btrfs_mark_buffer_dirty(path
->nodes
[0]);
1556 btrfs_commit_transaction(trans
, root
);
1557 btrfs_free_path(path
);
1562 int repair_qgroups(struct btrfs_fs_info
*info
, int *repaired
)
1565 struct qgroup_count
*count
, *tmpcount
;
1572 list_for_each_entry_safe(count
, tmpcount
, &bad_qgroups
, bad_list
) {
1573 ret
= repair_qgroup_info(info
, count
);
1580 list_del_init(&count
->bad_list
);
1584 * Do this step last as we want the latest transaction id on
1585 * our qgroup status to avoid a (useless) warning after
1588 if (*repaired
|| counts
.qgroup_inconsist
|| counts
.rescan_running
) {
1589 ret
= repair_qgroup_status(info
);