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"
32 #include "qgroup-verify.h"
34 /*#define QGROUP_VERIFY_DEBUG*/
35 static unsigned long tot_extents_scanned = 0;
37 static void add_bytes(u64 root_objectid, u64 num_bytes, int exclusive);
42 struct btrfs_disk_key key;
43 struct btrfs_qgroup_info_item diskinfo;
45 struct btrfs_qgroup_info_item info;
47 struct rb_node rb_node;
52 unsigned int num_groups;
53 } counts = { .root = RB_ROOT };
55 struct rb_root by_bytenr = RB_ROOT;
58 * List of interior tree blocks. We walk this list after loading the
59 * extent tree to resolve implied refs. For each interior node we'll
60 * place a shared ref in the ref tree against each child object. This
61 * allows the shared ref resolving code to do the actual work later of
62 * finding roots to account against.
64 * An implied ref is when a tree block has refs on it that may not
65 * exist in any of it's child nodes. Even though the refs might not
66 * exist further down the tree, the fact that our interior node has a
67 * ref means we need to account anything below it to all it's roots.
69 struct ulist *tree_blocks = NULL; /* unode->val = bytenr, ->aux
70 * = tree_block pointer */
82 struct rb_node bytenr_node;
85 #ifdef QGROUP_VERIFY_DEBUG
86 static void print_ref(struct ref *ref)
88 printf("bytenr: %llu\t\tnum_bytes: %llu\t\t parent: %llu\t\t"
89 "root: %llu\n", ref->bytenr, ref->num_bytes,
90 ref->parent, ref->root);
93 static void print_all_refs(void)
95 unsigned long count = 0;
99 node = rb_first(&by_bytenr);
101 ref = rb_entry(node, struct ref, bytenr_node);
106 node = rb_next(node);
109 printf("%lu extents scanned with %lu refs in total.\n",
110 tot_extents_scanned, count);
115 * Store by bytenr in rbtree
117 * The tree is sorted in ascending order by bytenr, then parent, then
118 * root. Since full refs have a parent == 0, those will come before
121 static int compare_ref(struct ref *orig, u64 bytenr, u64 root, u64 parent)
123 if (bytenr < orig->bytenr)
125 if (bytenr > orig->bytenr)
128 if (parent < orig->parent)
130 if (parent > orig->parent)
133 if (root < orig->root)
135 if (root > orig->root)
142 * insert a new ref into the tree. returns the existing ref entry
143 * if one is already there.
145 static struct ref *insert_ref(struct ref *ref)
148 struct rb_node **p = &by_bytenr.rb_node;
149 struct rb_node *parent = NULL;
154 curr = rb_entry(parent, struct ref, bytenr_node);
156 ret = compare_ref(curr, ref->bytenr, ref->root, ref->parent);
165 rb_link_node(&ref->bytenr_node, parent, p);
166 rb_insert_color(&ref->bytenr_node, &by_bytenr);
171 * Partial search, returns the first ref with matching bytenr. Caller
172 * can walk forward from there.
174 * Leftmost refs will be full refs - this is used to our advantage
175 * when resolving roots.
177 static struct ref *find_ref_bytenr(u64 bytenr)
179 struct rb_node *n = by_bytenr.rb_node;
183 ref = rb_entry(n, struct ref, bytenr_node);
185 if (bytenr < ref->bytenr)
187 else if (bytenr > ref->bytenr)
190 /* Walk to the left to find the first item */
191 struct rb_node *node_left = rb_prev(&ref->bytenr_node);
192 struct ref *ref_left;
195 ref_left = rb_entry(node_left, struct ref,
197 if (ref_left->bytenr != ref->bytenr)
200 node_left = rb_prev(node_left);
208 static struct ref *find_ref(u64 bytenr, u64 root, u64 parent)
210 struct rb_node *n = by_bytenr.rb_node;
215 ref = rb_entry(n, struct ref, bytenr_node);
217 ret = compare_ref(ref, bytenr, root, parent);
228 static struct ref *alloc_ref(u64 bytenr, u64 root, u64 parent, u64 num_bytes)
230 struct ref *ref = find_ref(bytenr, root, parent);
232 BUG_ON(parent && root);
235 ref = calloc(1, sizeof(*ref));
237 ref->bytenr = bytenr;
239 ref->parent = parent;
240 ref->num_bytes = num_bytes;
248 static void free_ref_node(struct rb_node *node)
250 struct ref *ref = rb_entry(node, struct ref, bytenr_node);
254 FREE_RB_BASED_TREE(ref, free_ref_node);
257 * Resolves all the possible roots for the ref at parent.
259 static void find_parent_roots(struct ulist *roots, u64 parent)
262 struct rb_node *node;
265 * Search the rbtree for the first ref with bytenr == parent.
266 * Walk forward so long as bytenr == parent, adding resolved root ids.
267 * For each unresolved root, we recurse
269 ref = find_ref_bytenr(parent);
270 node = &ref->bytenr_node;
272 BUG_ON(ref->bytenr != parent);
276 * Random sanity check, are we actually getting the
279 struct rb_node *prev_node = rb_prev(&ref->bytenr_node);
282 prev = rb_entry(prev_node, struct ref, bytenr_node);
283 BUG_ON(prev->bytenr == parent);
289 ulist_add(roots, ref->root, 0, 0);
291 find_parent_roots(roots, ref->parent);
293 node = rb_next(node);
295 ref = rb_entry(node, struct ref, bytenr_node);
296 } while (node && ref->bytenr == parent);
299 static void print_subvol_info(u64 subvolid, u64 bytenr, u64 num_bytes,
300 struct ulist *roots);
302 * Account each ref. Walk the refs, for each set of refs in a
305 * - add the roots for direct refs to the ref roots ulist
307 * - resolve all possible roots for shared refs, insert each
308 * of those into ref_roots ulist (this is a recursive process)
310 * - Walk ref_roots ulist, adding extent bytes to each qgroup count that
311 * cooresponds to a found root.
313 static void account_all_refs(int do_qgroups, u64 search_subvol)
317 struct rb_node *node;
318 u64 bytenr, num_bytes;
319 struct ulist *roots = ulist_alloc(0);
320 struct ulist_iterator uiter;
321 struct ulist_node *unode;
323 node = rb_first(&by_bytenr);
327 ref = rb_entry(node, struct ref, bytenr_node);
329 * Walk forward through the list of refs for this
330 * bytenr, adding roots to our ulist. If it's a full
331 * ref, then we have the easy case. Otherwise we need
332 * to search for roots.
334 bytenr = ref->bytenr;
335 num_bytes = ref->num_bytes;
337 BUG_ON(ref->bytenr != bytenr);
338 BUG_ON(ref->num_bytes != num_bytes);
340 ulist_add(roots, ref->root, 0, 0);
342 find_parent_roots(roots, ref->parent);
345 * When we leave this inner loop, node is set
346 * to next in our tree and will be turned into
347 * a ref object up top
349 node = rb_next(node);
351 ref = rb_entry(node, struct ref, bytenr_node);
352 } while (node && ref->bytenr == bytenr);
355 * Now that we have all roots, we can properly account
356 * this extent against the corresponding qgroups.
358 if (roots->nnodes == 1)
364 print_subvol_info(search_subvol, bytenr, num_bytes,
367 ULIST_ITER_INIT(&uiter);
368 while ((unode = ulist_next(roots, &uiter))) {
369 BUG_ON(unode->val == 0ULL);
370 /* We only want to account fs trees */
371 if (is_fstree(unode->val) && do_qgroups)
372 add_bytes(unode->val, num_bytes, exclusive);
379 static u64 resolve_one_root(u64 bytenr)
381 struct ref *ref = find_ref_bytenr(bytenr);
387 return resolve_one_root(ref->parent);
390 static inline struct tree_block *unode_tree_block(struct ulist_node *unode)
392 return (struct tree_block *)unode->aux;
394 static inline u64 unode_bytenr(struct ulist_node *unode)
399 static int alloc_tree_block(u64 bytenr, u64 num_bytes, int level)
401 struct tree_block *block = calloc(1, sizeof(*block));
404 block->num_bytes = num_bytes;
405 block->level = level;
406 if (ulist_add(tree_blocks, bytenr, (unsigned long long)block, 0) >= 0)
413 static void free_tree_blocks(void)
415 struct ulist_iterator uiter;
416 struct ulist_node *unode;
421 ULIST_ITER_INIT(&uiter);
422 while ((unode = ulist_next(tree_blocks, &uiter)))
423 free(unode_tree_block(unode));
424 ulist_free(tree_blocks);
428 #ifdef QGROUP_VERIFY_DEBUG
429 static void print_tree_block(u64 bytenr, struct tree_block *block)
432 struct rb_node *node;
434 printf("tree block: %llu\t\tlevel: %d\n", (unsigned long long)bytenr,
437 ref = find_ref_bytenr(bytenr);
438 node = &ref->bytenr_node;
441 node = rb_next(node);
443 ref = rb_entry(node, struct ref, bytenr_node);
444 } while (node && ref->bytenr == bytenr);
449 static void print_all_tree_blocks(void)
451 struct ulist_iterator uiter;
452 struct ulist_node *unode;
457 printf("Listing all found interior tree nodes:\n");
459 ULIST_ITER_INIT(&uiter);
460 while ((unode = ulist_next(tree_blocks, &uiter)))
461 print_tree_block(unode_bytenr(unode), unode_tree_block(unode));
465 static int add_refs_for_leaf_items(struct extent_buffer *eb, u64 ref_parent)
469 u64 bytenr, num_bytes;
470 struct btrfs_key key;
471 struct btrfs_disk_key disk_key;
472 struct btrfs_file_extent_item *fi;
474 nr = btrfs_header_nritems(eb);
475 for (i = 0; i < nr; i++) {
476 btrfs_item_key(eb, &disk_key, i);
477 btrfs_disk_key_to_cpu(&key, &disk_key);
479 if (key.type != BTRFS_EXTENT_DATA_KEY)
482 fi = btrfs_item_ptr(eb, i, struct btrfs_file_extent_item);
483 /* filter out: inline, disk_bytenr == 0, compressed?
484 * not if we can avoid it */
485 extent_type = btrfs_file_extent_type(eb, fi);
487 if (extent_type == BTRFS_FILE_EXTENT_INLINE)
490 bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
494 num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
495 if (alloc_ref(bytenr, 0, ref_parent, num_bytes) == NULL)
502 static int travel_tree(struct btrfs_fs_info *info, struct btrfs_root *root,
503 u64 bytenr, u64 num_bytes, u64 ref_parent)
506 struct extent_buffer *eb;
510 // printf("travel_tree: bytenr: %llu\tnum_bytes: %llu\tref_parent: %llu\n",
511 // bytenr, num_bytes, ref_parent);
513 eb = read_tree_block(root, bytenr, num_bytes, 0);
518 /* Don't add a ref for our starting tree block to itself */
519 if (bytenr != ref_parent) {
520 if (alloc_ref(bytenr, 0, ref_parent, num_bytes) == NULL)
524 if (btrfs_is_leaf(eb)) {
525 ret = add_refs_for_leaf_items(eb, ref_parent);
530 * Interior nodes are tuples of (key, bytenr) where key is the
531 * leftmost key in the tree block pointed to by bytenr. We
532 * don't have to care about key here, just follow the bytenr
535 nr = btrfs_header_nritems(eb);
536 for (i = 0; i < nr; i++) {
537 new_bytenr = btrfs_node_blockptr(eb, i);
538 new_num_bytes = btrfs_level_size(root,
539 btrfs_header_level(eb) - 1);
541 ret = travel_tree(info, root, new_bytenr, new_num_bytes,
546 free_extent_buffer(eb);
550 static int add_refs_for_implied(struct btrfs_fs_info *info, u64 bytenr,
551 struct tree_block *block)
554 u64 root_bytenr = resolve_one_root(bytenr);
555 struct btrfs_root *root;
556 struct btrfs_key key;
558 key.objectid = root_bytenr;
559 key.type = BTRFS_ROOT_ITEM_KEY;
560 key.offset = (u64)-1;
563 * XXX: Don't free the root object as we don't know whether it
564 * came off our fs_info struct or not.
566 root = btrfs_read_fs_root(info, &key);
567 if (!root || IS_ERR(root))
570 ret = travel_tree(info, root, bytenr, block->num_bytes, bytenr);
578 * Place shared refs in the ref tree for each child of an interior tree node.
580 static int map_implied_refs(struct btrfs_fs_info *info)
583 struct ulist_iterator uiter;
584 struct ulist_node *unode;
586 ULIST_ITER_INIT(&uiter);
587 while ((unode = ulist_next(tree_blocks, &uiter))) {
588 ret = add_refs_for_implied(info, unode_bytenr(unode),
589 unode_tree_block(unode));
598 * insert a new root into the tree. returns the existing root entry
599 * if one is already there. qgroupid is used
602 static int insert_count(struct qgroup_count *qc)
604 struct rb_node **p = &counts.root.rb_node;
605 struct rb_node *parent = NULL;
606 struct qgroup_count *curr;
610 curr = rb_entry(parent, struct qgroup_count, rb_node);
612 if (qc->qgroupid < curr->qgroupid)
614 else if (qc->qgroupid > curr->qgroupid)
620 rb_link_node(&qc->rb_node, parent, p);
621 rb_insert_color(&qc->rb_node, &counts.root);
625 static struct qgroup_count *find_count(u64 qgroupid)
627 struct rb_node *n = counts.root.rb_node;
628 struct qgroup_count *count;
631 count = rb_entry(n, struct qgroup_count, rb_node);
633 if (qgroupid < count->qgroupid)
635 else if (qgroupid > count->qgroupid)
643 static struct qgroup_count *alloc_count(struct btrfs_disk_key *key,
644 struct extent_buffer *leaf,
645 struct btrfs_qgroup_info_item *disk)
647 struct qgroup_count *c = calloc(1, sizeof(*c));
648 struct btrfs_qgroup_info_item *item;
651 c->qgroupid = btrfs_disk_key_offset(key);
655 item->generation = btrfs_qgroup_info_generation(leaf, disk);
656 item->referenced = btrfs_qgroup_info_referenced(leaf, disk);
657 item->referenced_compressed =
658 btrfs_qgroup_info_referenced_compressed(leaf, disk);
659 item->exclusive = btrfs_qgroup_info_exclusive(leaf, disk);
660 item->exclusive_compressed =
661 btrfs_qgroup_info_exclusive_compressed(leaf, disk);
663 if (insert_count(c)) {
671 static void add_bytes(u64 root_objectid, u64 num_bytes, int exclusive)
673 struct qgroup_count *count = find_count(root_objectid);
674 struct btrfs_qgroup_info_item *qg;
676 BUG_ON(num_bytes < 4096); /* Random sanity check. */
683 qg->referenced += num_bytes;
685 * count of compressed bytes is unimplemented, so we do the
688 qg->referenced_compressed += num_bytes;
691 qg->exclusive += num_bytes;
692 qg->exclusive_compressed += num_bytes;
696 static int load_quota_info(struct btrfs_fs_info *info)
699 struct btrfs_root *root = info->quota_root;
700 struct btrfs_path path;
701 struct btrfs_key key;
702 struct btrfs_disk_key disk_key;
703 struct extent_buffer *leaf;
704 struct btrfs_qgroup_info_item *item;
705 struct qgroup_count *count;
708 btrfs_init_path(&path);
714 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
716 fprintf(stderr, "ERROR: Couldn't search slot: %d\n", ret);
721 leaf = path.nodes[0];
723 nr = btrfs_header_nritems(leaf);
724 for(i = 0; i < nr; i++) {
725 btrfs_item_key(leaf, &disk_key, i);
726 btrfs_disk_key_to_cpu(&key, &disk_key);
728 if (key.type == BTRFS_QGROUP_RELATION_KEY)
729 printf("Ignoring qgroup relation key %llu\n",
733 * Ignore: BTRFS_QGROUP_STATUS_KEY,
734 * BTRFS_QGROUP_LIMIT_KEY, BTRFS_QGROUP_RELATION_KEY
736 if (key.type != BTRFS_QGROUP_INFO_KEY)
739 item = btrfs_item_ptr(leaf, i,
740 struct btrfs_qgroup_info_item);
742 count = alloc_count(&disk_key, leaf, item);
745 fprintf(stderr, "ERROR: out of memory\n");
750 ret = btrfs_next_leaf(root, &path);
756 btrfs_release_path(&path);
761 static int add_inline_refs(struct btrfs_fs_info *info,
762 struct extent_buffer *ei_leaf, int slot,
763 u64 bytenr, u64 num_bytes, int meta_item)
765 struct btrfs_extent_item *ei;
766 struct btrfs_extent_inline_ref *iref;
767 struct btrfs_extent_data_ref *dref;
768 u64 flags, root_obj, offset, parent;
769 u32 item_size = btrfs_item_size_nr(ei_leaf, slot);
774 ei = btrfs_item_ptr(ei_leaf, slot, struct btrfs_extent_item);
775 flags = btrfs_extent_flags(ei_leaf, ei);
777 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK && !meta_item) {
778 struct btrfs_tree_block_info *tbinfo;
779 tbinfo = (struct btrfs_tree_block_info *)(ei + 1);
780 iref = (struct btrfs_extent_inline_ref *)(tbinfo + 1);
782 iref = (struct btrfs_extent_inline_ref *)(ei + 1);
785 ptr = (unsigned long)iref;
786 end = (unsigned long)ei + item_size;
788 iref = (struct btrfs_extent_inline_ref *)ptr;
790 parent = root_obj = 0;
791 offset = btrfs_extent_inline_ref_offset(ei_leaf, iref);
792 type = btrfs_extent_inline_ref_type(ei_leaf, iref);
794 case BTRFS_TREE_BLOCK_REF_KEY:
797 case BTRFS_EXTENT_DATA_REF_KEY:
798 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
799 root_obj = btrfs_extent_data_ref_root(ei_leaf, dref);
801 case BTRFS_SHARED_DATA_REF_KEY:
802 case BTRFS_SHARED_BLOCK_REF_KEY:
809 if (alloc_ref(bytenr, root_obj, parent, num_bytes) == NULL)
812 ptr += btrfs_extent_inline_ref_size(type);
818 static int add_keyed_ref(struct btrfs_fs_info *info,
819 struct btrfs_key *key,
820 struct extent_buffer *leaf, int slot,
821 u64 bytenr, u64 num_bytes)
823 u64 root_obj = 0, parent = 0;
824 struct btrfs_extent_data_ref *dref;
827 case BTRFS_TREE_BLOCK_REF_KEY:
828 root_obj = key->offset;
830 case BTRFS_EXTENT_DATA_REF_KEY:
831 dref = btrfs_item_ptr(leaf, slot, struct btrfs_extent_data_ref);
832 root_obj = btrfs_extent_data_ref_root(leaf, dref);
834 case BTRFS_SHARED_DATA_REF_KEY:
835 case BTRFS_SHARED_BLOCK_REF_KEY:
836 parent = key->offset;
842 if (alloc_ref(bytenr, root_obj, parent, num_bytes) == NULL)
849 * return value of 0 indicates leaf or not meta data. The code that
850 * calls this does not need to make a distinction between the two as
851 * it is only concerned with intermediate blocks which will always
854 static int get_tree_block_level(struct btrfs_key *key,
855 struct extent_buffer *ei_leaf,
859 int meta_key = key->type == BTRFS_METADATA_ITEM_KEY;
861 struct btrfs_extent_item *ei;
863 ei = btrfs_item_ptr(ei_leaf, slot, struct btrfs_extent_item);
864 flags = btrfs_extent_flags(ei_leaf, ei);
866 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK && !meta_key) {
867 struct btrfs_tree_block_info *tbinfo;
868 tbinfo = (struct btrfs_tree_block_info *)(ei + 1);
869 level = btrfs_tree_block_level(ei_leaf, tbinfo);
870 } else if (meta_key) {
871 /* skinny metadata */
872 level = (int)key->offset;
878 * Walk the extent tree, allocating a ref item for every ref and
879 * storing it in the bytenr tree.
881 static int scan_extents(struct btrfs_fs_info *info,
884 int ret, i, nr, level;
885 struct btrfs_root *root = info->extent_root;
886 struct btrfs_key key;
887 struct btrfs_path path;
888 struct btrfs_disk_key disk_key;
889 struct extent_buffer *leaf;
890 u64 bytenr = 0, num_bytes = 0;
892 btrfs_init_path(&path);
894 key.objectid = start;
898 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
900 fprintf(stderr, "ERROR: Couldn't search slot: %d\n", ret);
906 leaf = path.nodes[0];
908 nr = btrfs_header_nritems(leaf);
909 for(i = 0; i < nr; i++) {
910 btrfs_item_key(leaf, &disk_key, i);
911 btrfs_disk_key_to_cpu(&key, &disk_key);
913 if (key.objectid < start)
916 if (key.objectid > end)
919 if (key.type == BTRFS_EXTENT_ITEM_KEY ||
920 key.type == BTRFS_METADATA_ITEM_KEY) {
923 tot_extents_scanned++;
925 bytenr = key.objectid;
926 num_bytes = key.offset;
927 if (key.type == BTRFS_METADATA_ITEM_KEY) {
928 num_bytes = info->extent_root->leafsize;
932 ret = add_inline_refs(info, leaf, i, bytenr,
937 level = get_tree_block_level(&key, leaf, i);
939 if (alloc_tree_block(bytenr, num_bytes,
947 if (key.type > BTRFS_SHARED_DATA_REF_KEY)
949 if (key.type < BTRFS_TREE_BLOCK_REF_KEY)
953 * Keyed refs should come after their extent
954 * item in the tree. As a result, the value of
955 * bytenr and num_bytes should be unchanged
956 * from the above block that catches the
957 * original extent item.
959 BUG_ON(key.objectid != bytenr);
961 ret = add_keyed_ref(info, &key, leaf, i, bytenr,
967 ret = btrfs_next_leaf(root, &path);
971 "ERROR: Next leaf failed: %d\n", ret);
980 btrfs_release_path(&path);
985 static void print_fields(u64 bytes, u64 bytes_compressed, char *prefix,
988 printf("%s\t\t%s %llu %s compressed %llu\n",
989 prefix, type, (unsigned long long)bytes, type,
990 (unsigned long long)bytes_compressed);
993 static void print_fields_signed(long long bytes,
994 long long bytes_compressed,
995 char *prefix, char *type)
997 printf("%s\t\t%s %lld %s compressed %lld\n",
998 prefix, type, bytes, type, bytes_compressed);
1001 static void print_qgroup_difference(struct qgroup_count *count, int verbose)
1004 struct btrfs_qgroup_info_item *info = &count->info;
1005 struct btrfs_qgroup_info_item *disk = &count->diskinfo;
1006 long long excl_diff = info->exclusive - disk->exclusive;
1007 long long ref_diff = info->referenced - disk->referenced;
1009 is_different = excl_diff || ref_diff;
1011 if (verbose || is_different) {
1012 printf("Counts for qgroup id: %llu %s\n",
1013 (unsigned long long)count->qgroupid,
1014 is_different ? "are different" : "");
1016 print_fields(info->referenced, info->referenced_compressed,
1017 "our:", "referenced");
1018 print_fields(disk->referenced, disk->referenced_compressed,
1019 "disk:", "referenced");
1021 print_fields_signed(ref_diff, ref_diff,
1022 "diff:", "referenced");
1023 print_fields(info->exclusive, info->exclusive_compressed,
1024 "our:", "exclusive");
1025 print_fields(disk->exclusive, disk->exclusive_compressed,
1026 "disk:", "exclusive");
1028 print_fields_signed(excl_diff, excl_diff,
1029 "diff:", "exclusive");
1033 void print_qgroup_report(int all)
1035 struct rb_node *node;
1036 struct qgroup_count *c;
1038 node = rb_first(&counts.root);
1040 c = rb_entry(node, struct qgroup_count, rb_node);
1041 print_qgroup_difference(c, all);
1042 node = rb_next(node);
1046 int qgroup_verify_all(struct btrfs_fs_info *info)
1050 if (!info->quota_enabled)
1053 tree_blocks = ulist_alloc(0);
1056 "ERROR: Out of memory while allocating ulist.\n");
1060 ret = load_quota_info(info);
1062 fprintf(stderr, "ERROR: Loading qgroups from disk: %d\n", ret);
1067 * Put all extent refs into our rbtree
1069 ret = scan_extents(info, 0, ~0ULL);
1071 fprintf(stderr, "ERROR: while scanning extent tree: %d\n", ret);
1075 ret = map_implied_refs(info);
1077 fprintf(stderr, "ERROR: while mapping refs: %d\n", ret);
1081 account_all_refs(1, 0);
1085 * Don't free the qgroup count records as they will be walked
1086 * later via the print function.
1089 free_ref_tree(&by_bytenr);
1093 static void __print_subvol_info(u64 bytenr, u64 num_bytes, struct ulist *roots)
1095 int n = roots->nnodes;
1096 struct ulist_iterator uiter;
1097 struct ulist_node *unode;
1099 printf("%llu\t%llu\t%d\t", bytenr, num_bytes, n);
1101 ULIST_ITER_INIT(&uiter);
1102 while ((unode = ulist_next(roots, &uiter))) {
1103 printf("%llu ", unode->val);
1108 static void print_subvol_info(u64 subvolid, u64 bytenr, u64 num_bytes,
1109 struct ulist *roots)
1111 struct ulist_iterator uiter;
1112 struct ulist_node *unode;
1114 ULIST_ITER_INIT(&uiter);
1115 while ((unode = ulist_next(roots, &uiter))) {
1116 BUG_ON(unode->val == 0ULL);
1117 if (unode->val == subvolid) {
1118 __print_subvol_info(bytenr, num_bytes, roots);
1126 int print_extent_state(struct btrfs_fs_info *info, u64 subvol)
1130 tree_blocks = ulist_alloc(0);
1133 "ERROR: Out of memory while allocating ulist.\n");
1138 * Put all extent refs into our rbtree
1140 ret = scan_extents(info, 0, ~0ULL);
1142 fprintf(stderr, "ERROR: while scanning extent tree: %d\n", ret);
1146 ret = map_implied_refs(info);
1148 fprintf(stderr, "ERROR: while mapping refs: %d\n", ret);
1152 printf("Offset\t\tLen\tRoot Refs\tRoots\n");
1153 account_all_refs(0, subvol);
1157 free_ref_tree(&by_bytenr);