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);
334 error("bytenr ref not found for parent %llu",
335 (unsigned long long)parent);
338 node = &ref->bytenr_node;
339 if (ref->bytenr != parent) {
340 error("found bytenr ref does not match parent: %llu != %llu",
341 (unsigned long long)ref->bytenr,
342 (unsigned long long)parent);
348 * Random sanity check, are we actually getting the
351 struct rb_node *prev_node = rb_prev(&ref->bytenr_node);
355 prev = rb_entry(prev_node, struct ref, bytenr_node);
356 if (prev->bytenr == parent) {
358 "unexpected: prev bytenr same as parent: %llu",
359 (unsigned long long)parent);
367 if (is_fstree(ref->root)) {
368 ret = ulist_add(roots, ref->root, 0, 0);
373 ret = find_parent_roots(roots, ref->parent);
378 node = rb_next(node);
380 ref = rb_entry(node, struct ref, bytenr_node);
381 } while (node && ref->bytenr == parent);
388 static int account_one_extent(struct ulist *roots, u64 bytenr, u64 num_bytes)
391 u64 id, nr_roots, nr_refs;
392 struct qgroup_count *count;
393 struct ulist *counts = ulist_alloc(0);
394 struct ulist *tmp = ulist_alloc(0);
395 struct ulist_iterator uiter;
396 struct ulist_iterator tmp_uiter;
397 struct ulist_node *unode;
398 struct ulist_node *tmp_unode;
399 struct btrfs_qgroup_list *glist;
401 if (!counts || !tmp) {
407 ULIST_ITER_INIT(&uiter);
408 while ((unode = ulist_next(roots, &uiter))) {
409 BUG_ON(unode->val == 0ULL);
412 * For each root, find their corresponding tracking group and
413 * add it to our qgroups list.
415 count = find_count(unode->val);
419 BUG_ON(!is_fstree(unode->val));
420 ret = ulist_add(counts, count->qgroupid, ptr_to_u64(count), 0);
425 * Now we look for parents (and parents of those...). Use a tmp
426 * ulist here to avoid re-walking (and re-incrementing) our
427 * already added items on every loop iteration.
430 ret = ulist_add(tmp, count->qgroupid, ptr_to_u64(count), 0);
434 ULIST_ITER_INIT(&tmp_uiter);
435 while ((tmp_unode = ulist_next(tmp, &tmp_uiter))) {
436 /* Bump the refcount on a node every time we see it. */
437 count = u64_to_ptr(tmp_unode->aux);
438 update_cur_refcnt(count);
440 list_for_each_entry(glist, &count->groups, next_group) {
441 struct qgroup_count *parent;
442 parent = glist->group;
443 id = parent->qgroupid;
447 ret = ulist_add(counts, id, ptr_to_u64(parent),
451 ret = ulist_add(tmp, id, ptr_to_u64(parent),
460 * Now that we have gathered up and counted all the groups, we
461 * can add bytes for this ref.
463 nr_roots = roots->nnodes;
464 ULIST_ITER_INIT(&uiter);
465 while ((unode = ulist_next(counts, &uiter))) {
466 count = u64_to_ptr(unode->aux);
468 nr_refs = group_get_cur_refcnt(count);
470 count->info.referenced += num_bytes;
471 count->info.referenced_compressed += num_bytes;
473 if (nr_refs == nr_roots) {
474 count->info.exclusive += num_bytes;
475 count->info.exclusive_compressed += num_bytes;
478 #ifdef QGROUP_VERIFY_DEBUG
479 printf("account (%llu, %llu), qgroup %llu/%llu, rfer %llu,"
480 " excl %llu, refs %llu, roots %llu\n", bytenr, num_bytes,
481 btrfs_qgroup_level(count->qgroupid),
482 btrfs_qgroup_subvid(count->qgroupid),
483 count->info.referenced, count->info.exclusive, nr_refs,
488 inc_qgroup_seq(roots->nnodes);
496 static void print_subvol_info(u64 subvolid, u64 bytenr, u64 num_bytes,
497 struct ulist *roots);
499 * Account each ref. Walk the refs, for each set of refs in a
502 * - add the roots for direct refs to the ref roots ulist
504 * - resolve all possible roots for shared refs, insert each
505 * of those into ref_roots ulist (this is a recursive process)
507 * - With all roots resolved we can account the ref - this is done in
508 * account_one_extent().
510 static int account_all_refs(int do_qgroups, u64 search_subvol)
513 struct rb_node *node;
514 u64 bytenr, num_bytes;
515 struct ulist *roots = ulist_alloc(0);
518 node = rb_first(&by_bytenr);
522 ref = rb_entry(node, struct ref, bytenr_node);
524 * Walk forward through the list of refs for this
525 * bytenr, adding roots to our ulist. If it's a full
526 * ref, then we have the easy case. Otherwise we need
527 * to search for roots.
529 bytenr = ref->bytenr;
530 num_bytes = ref->num_bytes;
532 BUG_ON(ref->bytenr != bytenr);
533 BUG_ON(ref->num_bytes != num_bytes);
535 if (is_fstree(ref->root)) {
536 if (ulist_add(roots, ref->root, 0, 0) < 0)
540 ret = find_parent_roots(roots, ref->parent);
546 * When we leave this inner loop, node is set
547 * to next in our tree and will be turned into
548 * a ref object up top
550 node = rb_next(node);
552 ref = rb_entry(node, struct ref, bytenr_node);
553 } while (node && ref->bytenr == bytenr);
556 print_subvol_info(search_subvol, bytenr, num_bytes,
562 if (account_one_extent(roots, bytenr, num_bytes))
569 error("Out of memory while accounting refs for qgroups");
573 static u64 resolve_one_root(u64 bytenr)
575 struct ref *ref = find_ref_bytenr(bytenr);
581 return resolve_one_root(ref->parent);
584 static inline struct tree_block *unode_tree_block(struct ulist_node *unode)
586 return u64_to_ptr(unode->aux);
588 static inline u64 unode_bytenr(struct ulist_node *unode)
593 static int alloc_tree_block(u64 bytenr, u64 num_bytes, int level)
595 struct tree_block *block = calloc(1, sizeof(*block));
598 block->num_bytes = num_bytes;
599 block->level = level;
600 if (ulist_add(tree_blocks, bytenr, ptr_to_u64(block), 0) >= 0)
607 static void free_tree_blocks(void)
609 struct ulist_iterator uiter;
610 struct ulist_node *unode;
615 ULIST_ITER_INIT(&uiter);
616 while ((unode = ulist_next(tree_blocks, &uiter)))
617 free(unode_tree_block(unode));
618 ulist_free(tree_blocks);
622 #ifdef QGROUP_VERIFY_DEBUG
623 static void print_tree_block(u64 bytenr, struct tree_block *block)
626 struct rb_node *node;
628 printf("tree block: %llu\t\tlevel: %d\n", (unsigned long long)bytenr,
631 ref = find_ref_bytenr(bytenr);
632 node = &ref->bytenr_node;
635 node = rb_next(node);
637 ref = rb_entry(node, struct ref, bytenr_node);
638 } while (node && ref->bytenr == bytenr);
643 static void print_all_tree_blocks(void)
645 struct ulist_iterator uiter;
646 struct ulist_node *unode;
651 printf("Listing all found interior tree nodes:\n");
653 ULIST_ITER_INIT(&uiter);
654 while ((unode = ulist_next(tree_blocks, &uiter)))
655 print_tree_block(unode_bytenr(unode), unode_tree_block(unode));
659 static int add_refs_for_leaf_items(struct extent_buffer *eb, u64 ref_parent)
663 u64 bytenr, num_bytes;
664 struct btrfs_key key;
665 struct btrfs_disk_key disk_key;
666 struct btrfs_file_extent_item *fi;
668 nr = btrfs_header_nritems(eb);
669 for (i = 0; i < nr; i++) {
670 btrfs_item_key(eb, &disk_key, i);
671 btrfs_disk_key_to_cpu(&key, &disk_key);
673 if (key.type != BTRFS_EXTENT_DATA_KEY)
676 fi = btrfs_item_ptr(eb, i, struct btrfs_file_extent_item);
677 /* filter out: inline, disk_bytenr == 0, compressed?
678 * not if we can avoid it */
679 extent_type = btrfs_file_extent_type(eb, fi);
681 if (extent_type == BTRFS_FILE_EXTENT_INLINE)
684 bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
688 num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
689 if (alloc_ref(bytenr, 0, ref_parent, num_bytes) == NULL)
696 static int travel_tree(struct btrfs_fs_info *info, struct btrfs_root *root,
697 u64 bytenr, u64 num_bytes, u64 ref_parent)
700 struct extent_buffer *eb;
704 // printf("travel_tree: bytenr: %llu\tnum_bytes: %llu\tref_parent: %llu\n",
705 // bytenr, num_bytes, ref_parent);
707 eb = read_tree_block(root, bytenr, num_bytes, 0);
708 if (!extent_buffer_uptodate(eb))
712 /* Don't add a ref for our starting tree block to itself */
713 if (bytenr != ref_parent) {
714 if (alloc_ref(bytenr, 0, ref_parent, num_bytes) == NULL)
718 if (btrfs_is_leaf(eb)) {
719 ret = add_refs_for_leaf_items(eb, ref_parent);
724 * Interior nodes are tuples of (key, bytenr) where key is the
725 * leftmost key in the tree block pointed to by bytenr. We
726 * don't have to care about key here, just follow the bytenr
729 nr = btrfs_header_nritems(eb);
730 for (i = 0; i < nr; i++) {
731 new_bytenr = btrfs_node_blockptr(eb, i);
732 new_num_bytes = root->nodesize;
734 ret = travel_tree(info, root, new_bytenr, new_num_bytes,
739 free_extent_buffer(eb);
743 static int add_refs_for_implied(struct btrfs_fs_info *info, u64 bytenr,
744 struct tree_block *block)
747 u64 root_id = resolve_one_root(bytenr);
748 struct btrfs_root *root;
749 struct btrfs_key key;
751 key.objectid = root_id;
752 key.type = BTRFS_ROOT_ITEM_KEY;
753 key.offset = (u64)-1;
756 * XXX: Don't free the root object as we don't know whether it
757 * came off our fs_info struct or not.
759 root = btrfs_read_fs_root(info, &key);
760 if (!root || IS_ERR(root))
763 ret = travel_tree(info, root, bytenr, block->num_bytes, bytenr);
771 * Place shared refs in the ref tree for each child of an interior tree node.
773 static int map_implied_refs(struct btrfs_fs_info *info)
776 struct ulist_iterator uiter;
777 struct ulist_node *unode;
779 ULIST_ITER_INIT(&uiter);
780 while ((unode = ulist_next(tree_blocks, &uiter))) {
781 ret = add_refs_for_implied(info, unode_bytenr(unode),
782 unode_tree_block(unode));
791 * insert a new root into the tree. returns the existing root entry
792 * if one is already there. qgroupid is used
795 static int insert_count(struct qgroup_count *qc)
797 struct rb_node **p = &counts.root.rb_node;
798 struct rb_node *parent = NULL;
799 struct qgroup_count *curr;
803 curr = rb_entry(parent, struct qgroup_count, rb_node);
805 if (qc->qgroupid < curr->qgroupid)
807 else if (qc->qgroupid > curr->qgroupid)
813 rb_link_node(&qc->rb_node, parent, p);
814 rb_insert_color(&qc->rb_node, &counts.root);
818 static struct qgroup_count *find_count(u64 qgroupid)
820 struct rb_node *n = counts.root.rb_node;
821 struct qgroup_count *count;
824 count = rb_entry(n, struct qgroup_count, rb_node);
826 if (qgroupid < count->qgroupid)
828 else if (qgroupid > count->qgroupid)
836 static struct qgroup_count *alloc_count(struct btrfs_disk_key *key,
837 struct extent_buffer *leaf,
838 struct btrfs_qgroup_info_item *disk)
840 struct qgroup_count *c = calloc(1, sizeof(*c));
841 struct qgroup_info *item;
844 c->qgroupid = btrfs_disk_key_offset(key);
848 item->referenced = btrfs_qgroup_info_referenced(leaf, disk);
849 item->referenced_compressed =
850 btrfs_qgroup_info_referenced_compressed(leaf, disk);
851 item->exclusive = btrfs_qgroup_info_exclusive(leaf, disk);
852 item->exclusive_compressed =
853 btrfs_qgroup_info_exclusive_compressed(leaf, disk);
854 INIT_LIST_HEAD(&c->groups);
855 INIT_LIST_HEAD(&c->members);
856 INIT_LIST_HEAD(&c->bad_list);
858 if (insert_count(c)) {
866 static int add_qgroup_relation(u64 memberid, u64 parentid)
868 struct qgroup_count *member;
869 struct qgroup_count *parent;
870 struct btrfs_qgroup_list *list;
872 if (memberid > parentid)
875 member = find_count(memberid);
876 parent = find_count(parentid);
877 if (!member || !parent)
880 list = calloc(1, sizeof(*list));
884 list->group = parent;
885 list->member = member;
886 list_add_tail(&list->next_group, &member->groups);
887 list_add_tail(&list->next_member, &parent->members);
892 static void read_qgroup_status(struct extent_buffer *eb, int slot,
893 struct counts_tree *counts)
895 struct btrfs_qgroup_status_item *status_item;
898 status_item = btrfs_item_ptr(eb, slot, struct btrfs_qgroup_status_item);
899 flags = btrfs_qgroup_status_flags(eb, status_item);
901 * Since qgroup_inconsist/rescan_running is just one bit,
902 * assign value directly won't work.
904 counts->qgroup_inconsist = !!(flags &
905 BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT);
906 counts->rescan_running = !!(flags & BTRFS_QGROUP_STATUS_FLAG_RESCAN);
909 static int load_quota_info(struct btrfs_fs_info *info)
912 struct btrfs_root *root = info->quota_root;
913 struct btrfs_root *tmproot;
914 struct btrfs_path path;
915 struct btrfs_key key;
916 struct btrfs_key root_key;
917 struct btrfs_disk_key disk_key;
918 struct extent_buffer *leaf;
919 struct btrfs_qgroup_info_item *item;
920 struct qgroup_count *count;
922 int search_relations = 0;
926 * Do 2 passes, the first allocates group counts and reads status
927 * items. The 2nd pass picks up relation items and glues them to their
928 * respective count structures.
930 btrfs_init_path(&path);
933 key.objectid = search_relations ? 0 : BTRFS_QGROUP_RELATION_KEY;
936 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
938 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 (search_relations) {
951 if (key.type == BTRFS_QGROUP_RELATION_KEY) {
952 ret = add_qgroup_relation(key.objectid,
955 error("out of memory");
962 if (key.type == BTRFS_QGROUP_STATUS_KEY) {
963 read_qgroup_status(leaf, i, &counts);
968 * At this point, we can ignore anything that
969 * isn't a qgroup info.
971 if (key.type != BTRFS_QGROUP_INFO_KEY)
974 item = btrfs_item_ptr(leaf, i,
975 struct btrfs_qgroup_info_item);
977 count = alloc_count(&disk_key, leaf, item);
980 fprintf(stderr, "ERROR: out of memory\n");
984 root_key.objectid = key.offset;
985 root_key.type = BTRFS_ROOT_ITEM_KEY;
986 root_key.offset = (u64)-1;
987 tmproot = btrfs_read_fs_root_no_cache(info, &root_key);
988 if (tmproot && !IS_ERR(tmproot)) {
989 count->subvol_exists = 1;
990 btrfs_free_fs_root(tmproot);
994 ret = btrfs_next_leaf(root, &path);
1000 btrfs_release_path(&path);
1002 if (!search_relations) {
1003 search_relations = 1;
1011 static int add_inline_refs(struct btrfs_fs_info *info,
1012 struct extent_buffer *ei_leaf, int slot,
1013 u64 bytenr, u64 num_bytes, int meta_item)
1015 struct btrfs_extent_item *ei;
1016 struct btrfs_extent_inline_ref *iref;
1017 struct btrfs_extent_data_ref *dref;
1018 u64 flags, root_obj, offset, parent;
1019 u32 item_size = btrfs_item_size_nr(ei_leaf, slot);
1024 ei = btrfs_item_ptr(ei_leaf, slot, struct btrfs_extent_item);
1025 flags = btrfs_extent_flags(ei_leaf, ei);
1027 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK && !meta_item) {
1028 struct btrfs_tree_block_info *tbinfo;
1029 tbinfo = (struct btrfs_tree_block_info *)(ei + 1);
1030 iref = (struct btrfs_extent_inline_ref *)(tbinfo + 1);
1032 iref = (struct btrfs_extent_inline_ref *)(ei + 1);
1035 ptr = (unsigned long)iref;
1036 end = (unsigned long)ei + item_size;
1038 iref = (struct btrfs_extent_inline_ref *)ptr;
1040 parent = root_obj = 0;
1041 offset = btrfs_extent_inline_ref_offset(ei_leaf, iref);
1042 type = btrfs_extent_inline_ref_type(ei_leaf, iref);
1044 case BTRFS_TREE_BLOCK_REF_KEY:
1047 case BTRFS_EXTENT_DATA_REF_KEY:
1048 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1049 root_obj = btrfs_extent_data_ref_root(ei_leaf, dref);
1051 case BTRFS_SHARED_DATA_REF_KEY:
1052 case BTRFS_SHARED_BLOCK_REF_KEY:
1059 if (alloc_ref(bytenr, root_obj, parent, num_bytes) == NULL)
1062 ptr += btrfs_extent_inline_ref_size(type);
1068 static int add_keyed_ref(struct btrfs_fs_info *info,
1069 struct btrfs_key *key,
1070 struct extent_buffer *leaf, int slot,
1071 u64 bytenr, u64 num_bytes)
1073 u64 root_obj = 0, parent = 0;
1074 struct btrfs_extent_data_ref *dref;
1077 case BTRFS_TREE_BLOCK_REF_KEY:
1078 root_obj = key->offset;
1080 case BTRFS_EXTENT_DATA_REF_KEY:
1081 dref = btrfs_item_ptr(leaf, slot, struct btrfs_extent_data_ref);
1082 root_obj = btrfs_extent_data_ref_root(leaf, dref);
1084 case BTRFS_SHARED_DATA_REF_KEY:
1085 case BTRFS_SHARED_BLOCK_REF_KEY:
1086 parent = key->offset;
1092 if (alloc_ref(bytenr, root_obj, parent, num_bytes) == NULL)
1099 * return value of 0 indicates leaf or not meta data. The code that
1100 * calls this does not need to make a distinction between the two as
1101 * it is only concerned with intermediate blocks which will always
1104 static int get_tree_block_level(struct btrfs_key *key,
1105 struct extent_buffer *ei_leaf,
1109 int meta_key = key->type == BTRFS_METADATA_ITEM_KEY;
1111 struct btrfs_extent_item *ei;
1113 ei = btrfs_item_ptr(ei_leaf, slot, struct btrfs_extent_item);
1114 flags = btrfs_extent_flags(ei_leaf, ei);
1116 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK && !meta_key) {
1117 struct btrfs_tree_block_info *tbinfo;
1118 tbinfo = (struct btrfs_tree_block_info *)(ei + 1);
1119 level = btrfs_tree_block_level(ei_leaf, tbinfo);
1120 } else if (meta_key) {
1121 /* skinny metadata */
1122 level = (int)key->offset;
1128 * Walk the extent tree, allocating a ref item for every ref and
1129 * storing it in the bytenr tree.
1131 static int scan_extents(struct btrfs_fs_info *info,
1134 int ret, i, nr, level;
1135 struct btrfs_root *root = info->extent_root;
1136 struct btrfs_key key;
1137 struct btrfs_path path;
1138 struct btrfs_disk_key disk_key;
1139 struct extent_buffer *leaf;
1140 u64 bytenr = 0, num_bytes = 0;
1142 btrfs_init_path(&path);
1144 key.objectid = start;
1148 ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
1150 fprintf(stderr, "ERROR: Couldn't search slot: %d\n", ret);
1156 leaf = path.nodes[0];
1158 nr = btrfs_header_nritems(leaf);
1159 for(i = 0; i < nr; i++) {
1160 btrfs_item_key(leaf, &disk_key, i);
1161 btrfs_disk_key_to_cpu(&key, &disk_key);
1163 if (key.objectid < start)
1166 if (key.objectid > end)
1169 if (key.type == BTRFS_EXTENT_ITEM_KEY ||
1170 key.type == BTRFS_METADATA_ITEM_KEY) {
1173 tot_extents_scanned++;
1175 bytenr = key.objectid;
1176 num_bytes = key.offset;
1177 if (key.type == BTRFS_METADATA_ITEM_KEY) {
1178 num_bytes = info->extent_root->nodesize;
1182 ret = add_inline_refs(info, leaf, i, bytenr,
1187 level = get_tree_block_level(&key, leaf, i);
1189 if (alloc_tree_block(bytenr, num_bytes,
1197 if (key.type > BTRFS_SHARED_DATA_REF_KEY)
1199 if (key.type < BTRFS_TREE_BLOCK_REF_KEY)
1203 * Keyed refs should come after their extent
1204 * item in the tree. As a result, the value of
1205 * bytenr and num_bytes should be unchanged
1206 * from the above block that catches the
1207 * original extent item.
1209 BUG_ON(key.objectid != bytenr);
1211 ret = add_keyed_ref(info, &key, leaf, i, bytenr,
1217 ret = btrfs_next_leaf(root, &path);
1221 "ERROR: Next leaf failed: %d\n", ret);
1230 btrfs_release_path(&path);
1235 static void print_fields(u64 bytes, u64 bytes_compressed, char *prefix,
1238 printf("%s\t\t%s %llu %s compressed %llu\n",
1239 prefix, type, (unsigned long long)bytes, type,
1240 (unsigned long long)bytes_compressed);
1243 static void print_fields_signed(long long bytes,
1244 long long bytes_compressed,
1245 char *prefix, char *type)
1247 printf("%s\t\t%s %lld %s compressed %lld\n",
1248 prefix, type, bytes, type, bytes_compressed);
1251 static inline int qgroup_printable(struct qgroup_count *c)
1253 return !!(c->subvol_exists || btrfs_qgroup_level(c->qgroupid));
1256 static int report_qgroup_difference(struct qgroup_count *count, int verbose)
1259 struct qgroup_info *info = &count->info;
1260 struct qgroup_info *disk = &count->diskinfo;
1261 long long excl_diff = info->exclusive - disk->exclusive;
1262 long long ref_diff = info->referenced - disk->referenced;
1264 is_different = excl_diff || ref_diff;
1266 if (verbose || (is_different && qgroup_printable(count))) {
1267 printf("Counts for qgroup id: %llu/%llu %s\n",
1268 btrfs_qgroup_level(count->qgroupid),
1269 btrfs_qgroup_subvid(count->qgroupid),
1270 is_different ? "are different" : "");
1272 print_fields(info->referenced, info->referenced_compressed,
1273 "our:", "referenced");
1274 print_fields(disk->referenced, disk->referenced_compressed,
1275 "disk:", "referenced");
1277 print_fields_signed(ref_diff, ref_diff,
1278 "diff:", "referenced");
1279 print_fields(info->exclusive, info->exclusive_compressed,
1280 "our:", "exclusive");
1281 print_fields(disk->exclusive, disk->exclusive_compressed,
1282 "disk:", "exclusive");
1284 print_fields_signed(excl_diff, excl_diff,
1285 "diff:", "exclusive");
1288 return is_different;
1291 void report_qgroups(int all)
1293 struct rb_node *node;
1294 struct qgroup_count *c;
1296 if (!repair && counts.rescan_running) {
1299 "Qgroup rescan is running, a difference in qgroup counts is expected\n");
1302 "Qgroup rescan is running, qgroups will not be printed.\n");
1306 if (counts.qgroup_inconsist && !counts.rescan_running)
1307 fprintf(stderr, "Qgroup are marked as inconsistent.\n");
1308 node = rb_first(&counts.root);
1310 c = rb_entry(node, struct qgroup_count, rb_node);
1312 if (report_qgroup_difference(c, all))
1313 list_add_tail(&c->bad_list, &bad_qgroups);
1315 node = rb_next(node);
1319 void free_qgroup_counts(void)
1321 struct rb_node *node;
1322 struct qgroup_count *c;
1323 struct btrfs_qgroup_list *glist, *tmpglist;
1325 node = rb_first(&counts.root);
1327 c = rb_entry(node, struct qgroup_count, rb_node);
1329 list_del(&c->bad_list);
1331 list_for_each_entry_safe(glist, tmpglist, &c->groups,
1333 list_del(&glist->next_group);
1334 list_del(&glist->next_member);
1337 list_for_each_entry_safe(glist, tmpglist, &c->members,
1339 list_del(&glist->next_group);
1340 list_del(&glist->next_member);
1344 node = rb_next(node);
1346 rb_erase(&c->rb_node, &counts.root);
1351 int qgroup_verify_all(struct btrfs_fs_info *info)
1355 if (!info->quota_enabled)
1358 tree_blocks = ulist_alloc(0);
1361 "ERROR: Out of memory while allocating ulist.\n");
1365 ret = load_quota_info(info);
1367 fprintf(stderr, "ERROR: Loading qgroups from disk: %d\n", ret);
1372 * Put all extent refs into our rbtree
1374 ret = scan_extents(info, 0, ~0ULL);
1376 fprintf(stderr, "ERROR: while scanning extent tree: %d\n", ret);
1380 ret = map_implied_refs(info);
1382 fprintf(stderr, "ERROR: while mapping refs: %d\n", ret);
1386 ret = account_all_refs(1, 0);
1390 * Don't free the qgroup count records as they will be walked
1391 * later via the print function.
1394 free_ref_tree(&by_bytenr);
1398 static void __print_subvol_info(u64 bytenr, u64 num_bytes, struct ulist *roots)
1400 int n = roots->nnodes;
1401 struct ulist_iterator uiter;
1402 struct ulist_node *unode;
1404 printf("%llu\t%llu\t%d\t", bytenr, num_bytes, n);
1406 ULIST_ITER_INIT(&uiter);
1407 while ((unode = ulist_next(roots, &uiter))) {
1408 printf("%llu ", unode->val);
1413 static void print_subvol_info(u64 subvolid, u64 bytenr, u64 num_bytes,
1414 struct ulist *roots)
1416 struct ulist_iterator uiter;
1417 struct ulist_node *unode;
1419 ULIST_ITER_INIT(&uiter);
1420 while ((unode = ulist_next(roots, &uiter))) {
1421 BUG_ON(unode->val == 0ULL);
1422 if (unode->val == subvolid) {
1423 __print_subvol_info(bytenr, num_bytes, roots);
1431 int print_extent_state(struct btrfs_fs_info *info, u64 subvol)
1435 tree_blocks = ulist_alloc(0);
1438 "ERROR: Out of memory while allocating ulist.\n");
1443 * Put all extent refs into our rbtree
1445 ret = scan_extents(info, 0, ~0ULL);
1447 fprintf(stderr, "ERROR: while scanning extent tree: %d\n", ret);
1451 ret = map_implied_refs(info);
1453 fprintf(stderr, "ERROR: while mapping refs: %d\n", ret);
1457 printf("Offset\t\tLen\tRoot Refs\tRoots\n");
1458 ret = account_all_refs(0, subvol);
1462 free_ref_tree(&by_bytenr);
1466 static int repair_qgroup_info(struct btrfs_fs_info *info,
1467 struct qgroup_count *count)
1470 struct btrfs_root *root = info->quota_root;
1471 struct btrfs_trans_handle *trans;
1472 struct btrfs_path *path;
1473 struct btrfs_qgroup_info_item *info_item;
1474 struct btrfs_key key;
1476 printf("Repair qgroup %llu/%llu\n", btrfs_qgroup_level(count->qgroupid),
1477 btrfs_qgroup_subvid(count->qgroupid));
1479 path = btrfs_alloc_path();
1483 trans = btrfs_start_transaction(root, 1);
1484 if (IS_ERR(trans)) {
1485 btrfs_free_path(path);
1486 return PTR_ERR(trans);
1490 key.type = BTRFS_QGROUP_INFO_KEY;
1491 key.offset = count->qgroupid;
1492 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
1494 error("Could not find disk item for qgroup %llu/%llu.\n",
1495 btrfs_qgroup_level(count->qgroupid),
1496 btrfs_qgroup_subvid(count->qgroupid));
1502 info_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
1503 struct btrfs_qgroup_info_item);
1505 btrfs_set_qgroup_info_generation(path->nodes[0], info_item,
1508 btrfs_set_qgroup_info_referenced(path->nodes[0], info_item,
1509 count->info.referenced);
1510 btrfs_set_qgroup_info_referenced_compressed(path->nodes[0], info_item,
1511 count->info.referenced_compressed);
1513 btrfs_set_qgroup_info_exclusive(path->nodes[0], info_item,
1514 count->info.exclusive);
1515 btrfs_set_qgroup_info_exclusive_compressed(path->nodes[0], info_item,
1516 count->info.exclusive_compressed);
1518 btrfs_mark_buffer_dirty(path->nodes[0]);
1521 btrfs_commit_transaction(trans, root);
1522 btrfs_free_path(path);
1527 static int repair_qgroup_status(struct btrfs_fs_info *info)
1530 struct btrfs_root *root = info->quota_root;
1531 struct btrfs_trans_handle *trans;
1532 struct btrfs_path *path;
1533 struct btrfs_key key;
1534 struct btrfs_qgroup_status_item *status_item;
1536 printf("Repair qgroup status item\n");
1538 path = btrfs_alloc_path();
1542 trans = btrfs_start_transaction(root, 1);
1543 if (IS_ERR(trans)) {
1544 btrfs_free_path(path);
1545 return PTR_ERR(trans);
1549 key.type = BTRFS_QGROUP_STATUS_KEY;
1551 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
1553 error("Could not find qgroup status item\n");
1559 status_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
1560 struct btrfs_qgroup_status_item);
1561 btrfs_set_qgroup_status_flags(path->nodes[0], status_item,
1562 BTRFS_QGROUP_STATUS_FLAG_ON);
1563 btrfs_set_qgroup_status_rescan(path->nodes[0], status_item, 0);
1564 btrfs_set_qgroup_status_generation(path->nodes[0], status_item,
1567 btrfs_mark_buffer_dirty(path->nodes[0]);
1570 btrfs_commit_transaction(trans, root);
1571 btrfs_free_path(path);
1576 int repair_qgroups(struct btrfs_fs_info *info, int *repaired)
1579 struct qgroup_count *count, *tmpcount;
1586 list_for_each_entry_safe(count, tmpcount, &bad_qgroups, bad_list) {
1587 ret = repair_qgroup_info(info, count);
1594 list_del_init(&count->bad_list);
1598 * Do this step last as we want the latest transaction id on
1599 * our qgroup status to avoid a (useless) warning after
1602 if (*repaired || counts.qgroup_inconsist || counts.rescan_running) {
1603 ret = repair_qgroup_status(info);