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 unsigned int rescan_running:1;
63 unsigned int qgroup_inconsist:1;
64 } counts = { .root = RB_ROOT };
66 static struct rb_root by_bytenr = RB_ROOT;
69 * List of interior tree blocks. We walk this list after loading the
70 * extent tree to resolve implied refs. For each interior node we'll
71 * place a shared ref in the ref tree against each child object. This
72 * allows the shared ref resolving code to do the actual work later of
73 * finding roots to account against.
75 * An implied ref is when a tree block has refs on it that may not
76 * exist in any of its child nodes. Even though the refs might not
77 * exist further down the tree, the fact that our interior node has a
78 * ref means we need to account anything below it to all its roots.
80 static struct ulist *tree_blocks = NULL; /* unode->val = bytenr, ->aux
81 * = tree_block pointer */
93 struct rb_node bytenr_node;
96 #ifdef QGROUP_VERIFY_DEBUG
97 static void print_ref(struct ref *ref)
99 printf("bytenr: %llu\t\tnum_bytes: %llu\t\t parent: %llu\t\t"
100 "root: %llu\n", ref->bytenr, ref->num_bytes,
101 ref->parent, ref->root);
104 static void print_all_refs(void)
106 unsigned long count = 0;
108 struct rb_node *node;
110 node = rb_first(&by_bytenr);
112 ref = rb_entry(node, struct ref, bytenr_node);
117 node = rb_next(node);
120 printf("%lu extents scanned with %lu refs in total.\n",
121 tot_extents_scanned, count);
126 * Store by bytenr in rbtree
128 * The tree is sorted in ascending order by bytenr, then parent, then
129 * root. Since full refs have a parent == 0, those will come before
132 static int compare_ref(struct ref *orig, u64 bytenr, u64 root, u64 parent)
134 if (bytenr < orig->bytenr)
136 if (bytenr > orig->bytenr)
139 if (parent < orig->parent)
141 if (parent > orig->parent)
144 if (root < orig->root)
146 if (root > orig->root)
153 * insert a new ref into the tree. returns the existing ref entry
154 * if one is already there.
156 static struct ref *insert_ref(struct ref *ref)
159 struct rb_node **p = &by_bytenr.rb_node;
160 struct rb_node *parent = NULL;
165 curr = rb_entry(parent, struct ref, bytenr_node);
167 ret = compare_ref(curr, ref->bytenr, ref->root, ref->parent);
176 rb_link_node(&ref->bytenr_node, parent, p);
177 rb_insert_color(&ref->bytenr_node, &by_bytenr);
182 * Partial search, returns the first ref with matching bytenr. Caller
183 * can walk forward from there.
185 * Leftmost refs will be full refs - this is used to our advantage
186 * when resolving roots.
188 static struct ref *find_ref_bytenr(u64 bytenr)
190 struct rb_node *n = by_bytenr.rb_node;
194 ref = rb_entry(n, struct ref, bytenr_node);
196 if (bytenr < ref->bytenr)
198 else if (bytenr > ref->bytenr)
201 /* Walk to the left to find the first item */
202 struct rb_node *node_left = rb_prev(&ref->bytenr_node);
203 struct ref *ref_left;
206 ref_left = rb_entry(node_left, struct ref,
208 if (ref_left->bytenr != ref->bytenr)
211 node_left = rb_prev(node_left);
219 static struct ref *find_ref(u64 bytenr, u64 root, u64 parent)
221 struct rb_node *n = by_bytenr.rb_node;
226 ref = rb_entry(n, struct ref, bytenr_node);
228 ret = compare_ref(ref, bytenr, root, parent);
239 static struct ref *alloc_ref(u64 bytenr, u64 root, u64 parent, u64 num_bytes)
241 struct ref *ref = find_ref(bytenr, root, parent);
243 BUG_ON(parent && root);
246 ref = calloc(1, sizeof(*ref));
248 ref->bytenr = bytenr;
250 ref->parent = parent;
251 ref->num_bytes = num_bytes;
259 static void free_ref_node(struct rb_node *node)
261 struct ref *ref = rb_entry(node, struct ref, bytenr_node);
265 FREE_RB_BASED_TREE(ref, free_ref_node);
268 * Resolves all the possible roots for the ref at parent.
270 static void find_parent_roots(struct ulist *roots, u64 parent)
273 struct rb_node *node;
276 * Search the rbtree for the first ref with bytenr == parent.
277 * Walk forward so long as bytenr == parent, adding resolved root ids.
278 * For each unresolved root, we recurse
280 ref = find_ref_bytenr(parent);
281 node = &ref->bytenr_node;
283 BUG_ON(ref->bytenr != parent);
287 * Random sanity check, are we actually getting the
290 struct rb_node *prev_node = rb_prev(&ref->bytenr_node);
293 prev = rb_entry(prev_node, struct ref, bytenr_node);
294 BUG_ON(prev->bytenr == parent);
300 ulist_add(roots, ref->root, 0, 0);
302 find_parent_roots(roots, ref->parent);
304 node = rb_next(node);
306 ref = rb_entry(node, struct ref, bytenr_node);
307 } while (node && ref->bytenr == parent);
310 static void print_subvol_info(u64 subvolid, u64 bytenr, u64 num_bytes,
311 struct ulist *roots);
313 * Account each ref. Walk the refs, for each set of refs in a
316 * - add the roots for direct refs to the ref roots ulist
318 * - resolve all possible roots for shared refs, insert each
319 * of those into ref_roots ulist (this is a recursive process)
321 * - Walk ref_roots ulist, adding extent bytes to each qgroup count that
322 * cooresponds to a found root.
324 static void account_all_refs(int do_qgroups, u64 search_subvol)
328 struct rb_node *node;
329 u64 bytenr, num_bytes;
330 struct ulist *roots = ulist_alloc(0);
331 struct ulist_iterator uiter;
332 struct ulist_node *unode;
334 node = rb_first(&by_bytenr);
338 ref = rb_entry(node, struct ref, bytenr_node);
340 * Walk forward through the list of refs for this
341 * bytenr, adding roots to our ulist. If it's a full
342 * ref, then we have the easy case. Otherwise we need
343 * to search for roots.
345 bytenr = ref->bytenr;
346 num_bytes = ref->num_bytes;
348 BUG_ON(ref->bytenr != bytenr);
349 BUG_ON(ref->num_bytes != num_bytes);
351 ulist_add(roots, ref->root, 0, 0);
353 find_parent_roots(roots, ref->parent);
356 * When we leave this inner loop, node is set
357 * to next in our tree and will be turned into
358 * a ref object up top
360 node = rb_next(node);
362 ref = rb_entry(node, struct ref, bytenr_node);
363 } while (node && ref->bytenr == bytenr);
366 * Now that we have all roots, we can properly account
367 * this extent against the corresponding qgroups.
369 if (roots->nnodes == 1)
375 print_subvol_info(search_subvol, bytenr, num_bytes,
378 ULIST_ITER_INIT(&uiter);
379 while ((unode = ulist_next(roots, &uiter))) {
380 BUG_ON(unode->val == 0ULL);
381 /* We only want to account fs trees */
382 if (is_fstree(unode->val) && do_qgroups)
383 add_bytes(unode->val, num_bytes, exclusive);
390 static u64 resolve_one_root(u64 bytenr)
392 struct ref *ref = find_ref_bytenr(bytenr);
398 return resolve_one_root(ref->parent);
401 static inline struct tree_block *unode_tree_block(struct ulist_node *unode)
403 return u64_to_ptr(unode->aux);
405 static inline u64 unode_bytenr(struct ulist_node *unode)
410 static int alloc_tree_block(u64 bytenr, u64 num_bytes, int level)
412 struct tree_block *block = calloc(1, sizeof(*block));
415 block->num_bytes = num_bytes;
416 block->level = level;
417 if (ulist_add(tree_blocks, bytenr, ptr_to_u64(block), 0) >= 0)
424 static void free_tree_blocks(void)
426 struct ulist_iterator uiter;
427 struct ulist_node *unode;
432 ULIST_ITER_INIT(&uiter);
433 while ((unode = ulist_next(tree_blocks, &uiter)))
434 free(unode_tree_block(unode));
435 ulist_free(tree_blocks);
439 #ifdef QGROUP_VERIFY_DEBUG
440 static void print_tree_block(u64 bytenr, struct tree_block *block)
443 struct rb_node *node;
445 printf("tree block: %llu\t\tlevel: %d\n", (unsigned long long)bytenr,
448 ref = find_ref_bytenr(bytenr);
449 node = &ref->bytenr_node;
452 node = rb_next(node);
454 ref = rb_entry(node, struct ref, bytenr_node);
455 } while (node && ref->bytenr == bytenr);
460 static void print_all_tree_blocks(void)
462 struct ulist_iterator uiter;
463 struct ulist_node *unode;
468 printf("Listing all found interior tree nodes:\n");
470 ULIST_ITER_INIT(&uiter);
471 while ((unode = ulist_next(tree_blocks, &uiter)))
472 print_tree_block(unode_bytenr(unode), unode_tree_block(unode));
476 static int add_refs_for_leaf_items(struct extent_buffer *eb, u64 ref_parent)
480 u64 bytenr, num_bytes;
481 struct btrfs_key key;
482 struct btrfs_disk_key disk_key;
483 struct btrfs_file_extent_item *fi;
485 nr = btrfs_header_nritems(eb);
486 for (i = 0; i < nr; i++) {
487 btrfs_item_key(eb, &disk_key, i);
488 btrfs_disk_key_to_cpu(&key, &disk_key);
490 if (key.type != BTRFS_EXTENT_DATA_KEY)
493 fi = btrfs_item_ptr(eb, i, struct btrfs_file_extent_item);
494 /* filter out: inline, disk_bytenr == 0, compressed?
495 * not if we can avoid it */
496 extent_type = btrfs_file_extent_type(eb, fi);
498 if (extent_type == BTRFS_FILE_EXTENT_INLINE)
501 bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
505 num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
506 if (alloc_ref(bytenr, 0, ref_parent, num_bytes) == NULL)
513 static int travel_tree(struct btrfs_fs_info *info, struct btrfs_root *root,
514 u64 bytenr, u64 num_bytes, u64 ref_parent)
517 struct extent_buffer *eb;
521 // printf("travel_tree: bytenr: %llu\tnum_bytes: %llu\tref_parent: %llu\n",
522 // bytenr, num_bytes, ref_parent);
524 eb = read_tree_block(root, bytenr, num_bytes, 0);
525 if (!extent_buffer_uptodate(eb))
529 /* Don't add a ref for our starting tree block to itself */
530 if (bytenr != ref_parent) {
531 if (alloc_ref(bytenr, 0, ref_parent, num_bytes) == NULL)
535 if (btrfs_is_leaf(eb)) {
536 ret = add_refs_for_leaf_items(eb, ref_parent);
541 * Interior nodes are tuples of (key, bytenr) where key is the
542 * leftmost key in the tree block pointed to by bytenr. We
543 * don't have to care about key here, just follow the bytenr
546 nr = btrfs_header_nritems(eb);
547 for (i = 0; i < nr; i++) {
548 new_bytenr = btrfs_node_blockptr(eb, i);
549 new_num_bytes = root->nodesize;
551 ret = travel_tree(info, root, new_bytenr, new_num_bytes,
556 free_extent_buffer(eb);
560 static int add_refs_for_implied(struct btrfs_fs_info *info, u64 bytenr,
561 struct tree_block *block)
564 u64 root_id = resolve_one_root(bytenr);
565 struct btrfs_root *root;
566 struct btrfs_key key;
568 key.objectid = root_id;
569 key.type = BTRFS_ROOT_ITEM_KEY;
570 key.offset = (u64)-1;
573 * XXX: Don't free the root object as we don't know whether it
574 * came off our fs_info struct or not.
576 root = btrfs_read_fs_root(info, &key);
577 if (!root || IS_ERR(root))
580 ret = travel_tree(info, root, bytenr, block->num_bytes, bytenr);
588 * Place shared refs in the ref tree for each child of an interior tree node.
590 static int map_implied_refs(struct btrfs_fs_info *info)
593 struct ulist_iterator uiter;
594 struct ulist_node *unode;
596 ULIST_ITER_INIT(&uiter);
597 while ((unode = ulist_next(tree_blocks, &uiter))) {
598 ret = add_refs_for_implied(info, unode_bytenr(unode),
599 unode_tree_block(unode));
608 * insert a new root into the tree. returns the existing root entry
609 * if one is already there. qgroupid is used
612 static int insert_count(struct qgroup_count *qc)
614 struct rb_node **p = &counts.root.rb_node;
615 struct rb_node *parent = NULL;
616 struct qgroup_count *curr;
620 curr = rb_entry(parent, struct qgroup_count, rb_node);
622 if (qc->qgroupid < curr->qgroupid)
624 else if (qc->qgroupid > curr->qgroupid)
630 rb_link_node(&qc->rb_node, parent, p);
631 rb_insert_color(&qc->rb_node, &counts.root);
635 static struct qgroup_count *find_count(u64 qgroupid)
637 struct rb_node *n = counts.root.rb_node;
638 struct qgroup_count *count;
641 count = rb_entry(n, struct qgroup_count, rb_node);
643 if (qgroupid < count->qgroupid)
645 else if (qgroupid > count->qgroupid)
653 static struct qgroup_count *alloc_count(struct btrfs_disk_key *key,
654 struct extent_buffer *leaf,
655 struct btrfs_qgroup_info_item *disk)
657 struct qgroup_count *c = calloc(1, sizeof(*c));
658 struct qgroup_info *item;
661 c->qgroupid = btrfs_disk_key_offset(key);
665 item->referenced = btrfs_qgroup_info_referenced(leaf, disk);
666 item->referenced_compressed =
667 btrfs_qgroup_info_referenced_compressed(leaf, disk);
668 item->exclusive = btrfs_qgroup_info_exclusive(leaf, disk);
669 item->exclusive_compressed =
670 btrfs_qgroup_info_exclusive_compressed(leaf, disk);
672 if (insert_count(c)) {
680 static void add_bytes(u64 root_objectid, u64 num_bytes, int exclusive)
682 struct qgroup_count *count = find_count(root_objectid);
683 struct qgroup_info *qg;
685 BUG_ON(num_bytes < 4096); /* Random sanity check. */
692 qg->referenced += num_bytes;
694 * count of compressed bytes is unimplemented, so we do the
697 qg->referenced_compressed += num_bytes;
700 qg->exclusive += num_bytes;
701 qg->exclusive_compressed += num_bytes;
705 static void read_qgroup_status(struct btrfs_path *path,
706 struct counts_tree *counts)
708 struct btrfs_qgroup_status_item *status_item;
711 status_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
712 struct btrfs_qgroup_status_item);
713 flags = btrfs_qgroup_status_flags(path->nodes[0], status_item);
714 counts->qgroup_inconsist = flags & BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
715 counts->rescan_running = flags & BTRFS_QGROUP_STATUS_FLAG_RESCAN;
718 static int load_quota_info(struct btrfs_fs_info *info)
721 struct btrfs_root *root = info->quota_root;
722 struct btrfs_root *tmproot;
723 struct btrfs_path path;
724 struct btrfs_key key;
725 struct btrfs_key root_key;
726 struct btrfs_disk_key disk_key;
727 struct extent_buffer *leaf;
728 struct btrfs_qgroup_info_item *item;
729 struct qgroup_count *count;
732 btrfs_init_path(&path);
738 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
740 fprintf(stderr, "ERROR: Couldn't search slot: %d\n", ret);
745 leaf = path.nodes[0];
747 nr = btrfs_header_nritems(leaf);
748 for(i = 0; i < nr; i++) {
749 btrfs_item_key(leaf, &disk_key, i);
750 btrfs_disk_key_to_cpu(&key, &disk_key);
752 if (key.type == BTRFS_QGROUP_STATUS_KEY) {
753 read_qgroup_status(&path, &counts);
756 if (key.type == BTRFS_QGROUP_RELATION_KEY)
757 printf("Ignoring qgroup relation key %llu\n",
761 * Ignore: BTRFS_QGROUP_LIMIT_KEY,
762 * BTRFS_QGROUP_RELATION_KEY
764 if (key.type != BTRFS_QGROUP_INFO_KEY)
767 item = btrfs_item_ptr(leaf, i,
768 struct btrfs_qgroup_info_item);
770 count = alloc_count(&disk_key, leaf, item);
773 fprintf(stderr, "ERROR: out of memory\n");
777 root_key.objectid = key.offset;
778 root_key.type = BTRFS_ROOT_ITEM_KEY;
779 root_key.offset = (u64)-1;
780 tmproot = btrfs_read_fs_root_no_cache(info, &root_key);
781 if (tmproot && !IS_ERR(tmproot)) {
782 count->subvol_exists = 1;
783 btrfs_free_fs_root(tmproot);
787 ret = btrfs_next_leaf(root, &path);
793 btrfs_release_path(&path);
798 static int add_inline_refs(struct btrfs_fs_info *info,
799 struct extent_buffer *ei_leaf, int slot,
800 u64 bytenr, u64 num_bytes, int meta_item)
802 struct btrfs_extent_item *ei;
803 struct btrfs_extent_inline_ref *iref;
804 struct btrfs_extent_data_ref *dref;
805 u64 flags, root_obj, offset, parent;
806 u32 item_size = btrfs_item_size_nr(ei_leaf, slot);
811 ei = btrfs_item_ptr(ei_leaf, slot, struct btrfs_extent_item);
812 flags = btrfs_extent_flags(ei_leaf, ei);
814 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK && !meta_item) {
815 struct btrfs_tree_block_info *tbinfo;
816 tbinfo = (struct btrfs_tree_block_info *)(ei + 1);
817 iref = (struct btrfs_extent_inline_ref *)(tbinfo + 1);
819 iref = (struct btrfs_extent_inline_ref *)(ei + 1);
822 ptr = (unsigned long)iref;
823 end = (unsigned long)ei + item_size;
825 iref = (struct btrfs_extent_inline_ref *)ptr;
827 parent = root_obj = 0;
828 offset = btrfs_extent_inline_ref_offset(ei_leaf, iref);
829 type = btrfs_extent_inline_ref_type(ei_leaf, iref);
831 case BTRFS_TREE_BLOCK_REF_KEY:
834 case BTRFS_EXTENT_DATA_REF_KEY:
835 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
836 root_obj = btrfs_extent_data_ref_root(ei_leaf, dref);
838 case BTRFS_SHARED_DATA_REF_KEY:
839 case BTRFS_SHARED_BLOCK_REF_KEY:
846 if (alloc_ref(bytenr, root_obj, parent, num_bytes) == NULL)
849 ptr += btrfs_extent_inline_ref_size(type);
855 static int add_keyed_ref(struct btrfs_fs_info *info,
856 struct btrfs_key *key,
857 struct extent_buffer *leaf, int slot,
858 u64 bytenr, u64 num_bytes)
860 u64 root_obj = 0, parent = 0;
861 struct btrfs_extent_data_ref *dref;
864 case BTRFS_TREE_BLOCK_REF_KEY:
865 root_obj = key->offset;
867 case BTRFS_EXTENT_DATA_REF_KEY:
868 dref = btrfs_item_ptr(leaf, slot, struct btrfs_extent_data_ref);
869 root_obj = btrfs_extent_data_ref_root(leaf, dref);
871 case BTRFS_SHARED_DATA_REF_KEY:
872 case BTRFS_SHARED_BLOCK_REF_KEY:
873 parent = key->offset;
879 if (alloc_ref(bytenr, root_obj, parent, num_bytes) == NULL)
886 * return value of 0 indicates leaf or not meta data. The code that
887 * calls this does not need to make a distinction between the two as
888 * it is only concerned with intermediate blocks which will always
891 static int get_tree_block_level(struct btrfs_key *key,
892 struct extent_buffer *ei_leaf,
896 int meta_key = key->type == BTRFS_METADATA_ITEM_KEY;
898 struct btrfs_extent_item *ei;
900 ei = btrfs_item_ptr(ei_leaf, slot, struct btrfs_extent_item);
901 flags = btrfs_extent_flags(ei_leaf, ei);
903 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK && !meta_key) {
904 struct btrfs_tree_block_info *tbinfo;
905 tbinfo = (struct btrfs_tree_block_info *)(ei + 1);
906 level = btrfs_tree_block_level(ei_leaf, tbinfo);
907 } else if (meta_key) {
908 /* skinny metadata */
909 level = (int)key->offset;
915 * Walk the extent tree, allocating a ref item for every ref and
916 * storing it in the bytenr tree.
918 static int scan_extents(struct btrfs_fs_info *info,
921 int ret, i, nr, level;
922 struct btrfs_root *root = info->extent_root;
923 struct btrfs_key key;
924 struct btrfs_path path;
925 struct btrfs_disk_key disk_key;
926 struct extent_buffer *leaf;
927 u64 bytenr = 0, num_bytes = 0;
929 btrfs_init_path(&path);
931 key.objectid = start;
935 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
937 fprintf(stderr, "ERROR: Couldn't search slot: %d\n", ret);
943 leaf = path.nodes[0];
945 nr = btrfs_header_nritems(leaf);
946 for(i = 0; i < nr; i++) {
947 btrfs_item_key(leaf, &disk_key, i);
948 btrfs_disk_key_to_cpu(&key, &disk_key);
950 if (key.objectid < start)
953 if (key.objectid > end)
956 if (key.type == BTRFS_EXTENT_ITEM_KEY ||
957 key.type == BTRFS_METADATA_ITEM_KEY) {
960 tot_extents_scanned++;
962 bytenr = key.objectid;
963 num_bytes = key.offset;
964 if (key.type == BTRFS_METADATA_ITEM_KEY) {
965 num_bytes = info->extent_root->nodesize;
969 ret = add_inline_refs(info, leaf, i, bytenr,
974 level = get_tree_block_level(&key, leaf, i);
976 if (alloc_tree_block(bytenr, num_bytes,
984 if (key.type > BTRFS_SHARED_DATA_REF_KEY)
986 if (key.type < BTRFS_TREE_BLOCK_REF_KEY)
990 * Keyed refs should come after their extent
991 * item in the tree. As a result, the value of
992 * bytenr and num_bytes should be unchanged
993 * from the above block that catches the
994 * original extent item.
996 BUG_ON(key.objectid != bytenr);
998 ret = add_keyed_ref(info, &key, leaf, i, bytenr,
1004 ret = btrfs_next_leaf(root, &path);
1008 "ERROR: Next leaf failed: %d\n", ret);
1017 btrfs_release_path(&path);
1022 static void print_fields(u64 bytes, u64 bytes_compressed, char *prefix,
1025 printf("%s\t\t%s %llu %s compressed %llu\n",
1026 prefix, type, (unsigned long long)bytes, type,
1027 (unsigned long long)bytes_compressed);
1030 static void print_fields_signed(long long bytes,
1031 long long bytes_compressed,
1032 char *prefix, char *type)
1034 printf("%s\t\t%s %lld %s compressed %lld\n",
1035 prefix, type, bytes, type, bytes_compressed);
1038 static int report_qgroup_difference(struct qgroup_count *count, int verbose)
1041 struct qgroup_info *info = &count->info;
1042 struct qgroup_info *disk = &count->diskinfo;
1043 long long excl_diff = info->exclusive - disk->exclusive;
1044 long long ref_diff = info->referenced - disk->referenced;
1046 is_different = excl_diff || ref_diff;
1048 if (verbose || (is_different && count->subvol_exists)) {
1049 printf("Counts for qgroup id: %llu %s\n",
1050 (unsigned long long)count->qgroupid,
1051 is_different ? "are different" : "");
1053 print_fields(info->referenced, info->referenced_compressed,
1054 "our:", "referenced");
1055 print_fields(disk->referenced, disk->referenced_compressed,
1056 "disk:", "referenced");
1058 print_fields_signed(ref_diff, ref_diff,
1059 "diff:", "referenced");
1060 print_fields(info->exclusive, info->exclusive_compressed,
1061 "our:", "exclusive");
1062 print_fields(disk->exclusive, disk->exclusive_compressed,
1063 "disk:", "exclusive");
1065 print_fields_signed(excl_diff, excl_diff,
1066 "diff:", "exclusive");
1068 return (is_different && count->subvol_exists);
1071 int report_qgroups(int all)
1073 struct rb_node *node;
1074 struct qgroup_count *c;
1077 if (counts.rescan_running) {
1080 "Qgroup rescan is running, qgroup counts difference is expected\n");
1083 "Qgroup rescan is running, ignore qgroup check\n");
1087 if (counts.qgroup_inconsist && !counts.rescan_running)
1088 fprintf(stderr, "Qgroup is already inconsistent before checking\n");
1089 node = rb_first(&counts.root);
1091 c = rb_entry(node, struct qgroup_count, rb_node);
1092 ret |= report_qgroup_difference(c, all);
1093 node = rb_next(node);
1098 int qgroup_verify_all(struct btrfs_fs_info *info)
1102 if (!info->quota_enabled)
1105 tree_blocks = ulist_alloc(0);
1108 "ERROR: Out of memory while allocating ulist.\n");
1112 ret = load_quota_info(info);
1114 fprintf(stderr, "ERROR: Loading qgroups from disk: %d\n", ret);
1119 * Put all extent refs into our rbtree
1121 ret = scan_extents(info, 0, ~0ULL);
1123 fprintf(stderr, "ERROR: while scanning extent tree: %d\n", ret);
1127 ret = map_implied_refs(info);
1129 fprintf(stderr, "ERROR: while mapping refs: %d\n", ret);
1133 account_all_refs(1, 0);
1137 * Don't free the qgroup count records as they will be walked
1138 * later via the print function.
1141 free_ref_tree(&by_bytenr);
1145 static void __print_subvol_info(u64 bytenr, u64 num_bytes, struct ulist *roots)
1147 int n = roots->nnodes;
1148 struct ulist_iterator uiter;
1149 struct ulist_node *unode;
1151 printf("%llu\t%llu\t%d\t", bytenr, num_bytes, n);
1153 ULIST_ITER_INIT(&uiter);
1154 while ((unode = ulist_next(roots, &uiter))) {
1155 printf("%llu ", unode->val);
1160 static void print_subvol_info(u64 subvolid, u64 bytenr, u64 num_bytes,
1161 struct ulist *roots)
1163 struct ulist_iterator uiter;
1164 struct ulist_node *unode;
1166 ULIST_ITER_INIT(&uiter);
1167 while ((unode = ulist_next(roots, &uiter))) {
1168 BUG_ON(unode->val == 0ULL);
1169 if (unode->val == subvolid) {
1170 __print_subvol_info(bytenr, num_bytes, roots);
1178 int print_extent_state(struct btrfs_fs_info *info, u64 subvol)
1182 tree_blocks = ulist_alloc(0);
1185 "ERROR: Out of memory while allocating ulist.\n");
1190 * Put all extent refs into our rbtree
1192 ret = scan_extents(info, 0, ~0ULL);
1194 fprintf(stderr, "ERROR: while scanning extent tree: %d\n", ret);
1198 ret = map_implied_refs(info);
1200 fprintf(stderr, "ERROR: while mapping refs: %d\n", ret);
1204 printf("Offset\t\tLen\tRoot Refs\tRoots\n");
1205 account_all_refs(0, subvol);
1209 free_ref_tree(&by_bytenr);