qgroup-verify.c

   1 /*
   2  * Copyright (C) 2014 SUSE.  All rights reserved.
   3  *
   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.
   7  *
   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.
  12  *
  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.
  17  *
  18  * Authors: Mark Fasheh <mfasheh@suse.de>
  19  */
  20
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <uuid/uuid.h>
  24 #include "kerncompat.h"
  25 #include "radix-tree.h"
  26 #include "ctree.h"
  27 #include "disk-io.h"
  28 #include "print-tree.h"
  29 #include "utils.h"
  30 #include "ulist.h"
  31 #include "rbtree-utils.h"
  32 #include "transaction.h"
  33 #include "repair.h"
  34
  35 #include "qgroup-verify.h"
  36
  37 /*#define QGROUP_VERIFY_DEBUG*/
  38 static unsigned long tot_extents_scanned = 0;
  39
  40 struct qgroup_count;
  41 static struct qgroup_count *find_count(u64 qgroupid);
  42
  43 struct qgroup_info {
  44         u64 referenced;
  45         u64 referenced_compressed;
  46         u64 exclusive;
  47         u64 exclusive_compressed;
  48 };
  49
  50 struct qgroup_count {
  51         u64 qgroupid;
  52         int subvol_exists;
  53
  54         struct btrfs_disk_key key;
  55         struct qgroup_info diskinfo;
  56
  57         struct qgroup_info info;
  58
  59         struct rb_node rb_node;
  60
  61         /* Parents when we are a child group */
  62         struct list_head groups;
  63
  64         /*
  65          * Children when we are a parent group (not currently used but
  66          * maintained to mirror kernel handling of qgroups)
  67          */
  68         struct list_head members;
  69
  70         u64 cur_refcnt;
  71
  72         struct list_head bad_list;
  73 };
  74
  75 static struct counts_tree {
  76         struct rb_root          root;
  77         unsigned int            num_groups;
  78         unsigned int            rescan_running:1;
  79         unsigned int            qgroup_inconsist:1;
  80 } counts = { .root = RB_ROOT };
  81
  82 static LIST_HEAD(bad_qgroups);
  83
  84 static struct rb_root by_bytenr = RB_ROOT;
  85
  86 /*
  87  * Glue structure to represent the relations between qgroups. Mirrored
  88  * from kernel.
  89  */
  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;
  95 };
  96
  97 /* Allow us to reset ref counts during accounting without zeroing each group. */
  98 static u64 qgroup_seq = 1ULL;
  99
 100 static inline void update_cur_refcnt(struct qgroup_count *c)
 101 {
 102         if (c->cur_refcnt < qgroup_seq)
 103                 c->cur_refcnt = qgroup_seq;
 104         c->cur_refcnt++;
 105 }
 106
 107 static inline u64 group_get_cur_refcnt(struct qgroup_count *c)
 108 {
 109         if (c->cur_refcnt < qgroup_seq)
 110                 return 0;
 111         return c->cur_refcnt - qgroup_seq;
 112 }
 113
 114 static void inc_qgroup_seq(int root_count)
 115 {
 116         qgroup_seq += root_count + 1;
 117 }
 118
 119 /*
 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.
 125  *
 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.
 130  */
 131 static struct ulist *tree_blocks = NULL;        /* unode->val = bytenr, ->aux
 132                                                  * = tree_block pointer */
 133 struct tree_block {
 134         int                     level;
 135         u64                     num_bytes;
 136 };
 137
 138 struct ref {
 139         u64                     bytenr;
 140         u64                     num_bytes;
 141         u64                     parent;
 142         u64                     root;
 143
 144         struct rb_node          bytenr_node;
 145 };
 146
 147 #ifdef QGROUP_VERIFY_DEBUG
 148 static void print_ref(struct ref *ref)
 149 {
 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);
 153 }
 154
 155 static void print_all_refs(void)
 156 {
 157         unsigned long count = 0;
 158         struct ref *ref;
 159         struct rb_node *node;
 160
 161         node = rb_first(&by_bytenr);
 162         while (node) {
 163                 ref = rb_entry(node, struct ref, bytenr_node);
 164
 165                 print_ref(ref);
 166
 167                 count++;
 168                 node = rb_next(node);
 169         }
 170
 171         printf("%lu extents scanned with %lu refs in total.\n",
 172                tot_extents_scanned, count);
 173 }
 174 #endif
 175
 176 /*
 177  * Store by bytenr in rbtree
 178  *
 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
 181  * shared refs.
 182  */
 183 static int compare_ref(struct ref *orig, u64 bytenr, u64 root, u64 parent)
 184 {
 185         if (bytenr < orig->bytenr)
 186                 return -1;
 187         if (bytenr > orig->bytenr)
 188                 return 1;
 189
 190         if (parent < orig->parent)
 191                 return -1;
 192         if (parent > orig->parent)
 193                 return 1;
 194
 195         if (root < orig->root)
 196                 return -1;
 197         if (root > orig->root)
 198                 return 1;
 199
 200         return 0;
 201 }
 202
 203 /*
 204  * insert a new ref into the tree.  returns the existing ref entry
 205  * if one is already there.
 206  */
 207 static struct ref *insert_ref(struct ref *ref)
 208 {
 209         int ret;
 210         struct rb_node **p = &by_bytenr.rb_node;
 211         struct rb_node *parent = NULL;
 212         struct ref *curr;
 213
 214         while (*p) {
 215                 parent = *p;
 216                 curr = rb_entry(parent, struct ref, bytenr_node);
 217
 218                 ret = compare_ref(curr, ref->bytenr, ref->root, ref->parent);
 219                 if (ret < 0)
 220                         p = &(*p)->rb_left;
 221                 else if (ret > 0)
 222                         p = &(*p)->rb_right;
 223                 else
 224                         return curr;
 225         }
 226
 227         rb_link_node(&ref->bytenr_node, parent, p);
 228         rb_insert_color(&ref->bytenr_node, &by_bytenr);
 229         return ref;
 230 }
 231
 232 /*
 233  * Partial search, returns the first ref with matching bytenr. Caller
 234  * can walk forward from there.
 235  *
 236  * Leftmost refs will be full refs - this is used to our advantage
 237  * when resolving roots.
 238  */
 239 static struct ref *find_ref_bytenr(u64 bytenr)
 240 {
 241         struct rb_node *n = by_bytenr.rb_node;
 242         struct ref *ref;
 243
 244         while (n) {
 245                 ref = rb_entry(n, struct ref, bytenr_node);
 246
 247                 if (bytenr < ref->bytenr)
 248                         n = n->rb_left;
 249                 else if (bytenr > ref->bytenr)
 250                         n = n->rb_right;
 251                 else {
 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;
 255
 256                         while (node_left) {
 257                                 ref_left = rb_entry(node_left, struct ref,
 258                                                     bytenr_node);
 259                                 if (ref_left->bytenr != ref->bytenr)
 260                                         break;
 261                                 ref = ref_left;
 262                                 node_left = rb_prev(node_left);
 263                         }
 264                         return ref;
 265                 }
 266         }
 267         return NULL;
 268 }
 269
 270 static struct ref *find_ref(u64 bytenr, u64 root, u64 parent)
 271 {
 272         struct rb_node *n = by_bytenr.rb_node;
 273         struct ref *ref;
 274         int ret;
 275
 276         while (n) {
 277                 ref = rb_entry(n, struct ref, bytenr_node);
 278
 279                 ret = compare_ref(ref, bytenr, root, parent);
 280                 if (ret < 0)
 281                         n = n->rb_left;
 282                 else if (ret > 0)
 283                         n = n->rb_right;
 284                 else
 285                         return ref;
 286         }
 287         return NULL;
 288 }
 289
 290 static struct ref *alloc_ref(u64 bytenr, u64 root, u64 parent, u64 num_bytes)
 291 {
 292         struct ref *ref = find_ref(bytenr, root, parent);
 293
 294         BUG_ON(parent && root);
 295
 296         if (ref == NULL) {
 297                 ref = calloc(1, sizeof(*ref));
 298                 if (ref) {
 299                         ref->bytenr = bytenr;
 300                         ref->root = root;
 301                         ref->parent = parent;
 302                         ref->num_bytes = num_bytes;
 303
 304                         insert_ref(ref);
 305                 }
 306         }
 307         return ref;
 308 }
 309
 310 static void free_ref_node(struct rb_node *node)
 311 {
 312         struct ref *ref = rb_entry(node, struct ref, bytenr_node);
 313         free(ref);
 314 }
 315
 316 FREE_RB_BASED_TREE(ref, free_ref_node);
 317
 318 /*
 319  * Resolves all the possible roots for the ref at parent.
 320  */
 321 static int find_parent_roots(struct ulist *roots, u64 parent)
 322 {
 323         struct ref *ref;
 324         struct rb_node *node;
 325         int ret;
 326
 327         /*
 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
 331          */
 332         ref = find_ref_bytenr(parent);
 333         if (!ref) {
 334                 error("bytenr ref not found for parent %llu",
 335                                 (unsigned long long)parent);
 336                 return -EIO;
 337         }
 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);
 343                 return -EIO;
 344         }
 345
 346         {
 347                 /*
 348                  * Random sanity check, are we actually getting the
 349                  * leftmost node?
 350                  */
 351                 struct rb_node *prev_node = rb_prev(&ref->bytenr_node);
 352                 struct ref *prev;
 353
 354                 if (prev_node) {
 355                         prev = rb_entry(prev_node, struct ref, bytenr_node);
 356                         if (prev->bytenr == parent) {
 357                                 error(
 358                                 "unexpected: prev bytenr same as parent: %llu",
 359                                                 (unsigned long long)parent);
 360                                 return -EIO;
 361                         }
 362                 }
 363         }
 364
 365         do {
 366                 if (ref->root) {
 367                         if (is_fstree(ref->root)) {
 368                                 ret = ulist_add(roots, ref->root, 0, 0);
 369                                 if (ret < 0)
 370                                         goto out;
 371                         }
 372                 } else if (ref->parent == ref->bytenr) {
 373                         /*
 374                          * Special loop case for tree reloc tree
 375                          */
 376                         ref->root = BTRFS_TREE_RELOC_OBJECTID;
 377                 } else {
 378                         ret = find_parent_roots(roots, ref->parent);
 379                         if (ret < 0)
 380                                 goto out;
 381                 }
 382
 383                 node = rb_next(node);
 384                 if (node)
 385                         ref = rb_entry(node, struct ref, bytenr_node);
 386         } while (node && ref->bytenr == parent);
 387
 388         ret = 0;
 389 out:
 390         return ret;
 391 }
 392
 393 static int account_one_extent(struct ulist *roots, u64 bytenr, u64 num_bytes)
 394 {
 395         int ret;
 396         u64 id, nr_roots, nr_refs;
 397         struct qgroup_count *count;
 398         struct ulist *counts = ulist_alloc(0);
 399         struct ulist *tmp = ulist_alloc(0);
 400         struct ulist_iterator uiter;
 401         struct ulist_iterator tmp_uiter;
 402         struct ulist_node *unode;
 403         struct ulist_node *tmp_unode;
 404         struct btrfs_qgroup_list *glist;
 405
 406         if (!counts || !tmp) {
 407                 ulist_free(counts);
 408                 ulist_free(tmp);
 409                 return ENOMEM;
 410         }
 411
 412         ULIST_ITER_INIT(&uiter);
 413         while ((unode = ulist_next(roots, &uiter))) {
 414                 BUG_ON(unode->val == 0ULL);
 415
 416                 /*
 417                  * For each root, find their corresponding tracking group and
 418                  * add it to our qgroups list.
 419                  */
 420                 count = find_count(unode->val);
 421                 if (!count)
 422                         continue;
 423
 424                 BUG_ON(!is_fstree(unode->val));
 425                 ret = ulist_add(counts, count->qgroupid, ptr_to_u64(count), 0);
 426                 if (ret < 0)
 427                         goto out;
 428
 429                 /*
 430                  * Now we look for parents (and parents of those...). Use a tmp
 431                  * ulist here to avoid re-walking (and re-incrementing) our
 432                  * already added items on every loop iteration.
 433                  */
 434                 ulist_reinit(tmp);
 435                 ret = ulist_add(tmp, count->qgroupid, ptr_to_u64(count), 0);
 436                 if (ret < 0)
 437                         goto out;
 438
 439                 ULIST_ITER_INIT(&tmp_uiter);
 440                 while ((tmp_unode = ulist_next(tmp, &tmp_uiter))) {
 441                         /* Bump the refcount on a node every time we see it. */
 442                         count = u64_to_ptr(tmp_unode->aux);
 443                         update_cur_refcnt(count);
 444
 445                         list_for_each_entry(glist, &count->groups, next_group) {
 446                                 struct qgroup_count *parent;
 447                                 parent = glist->group;
 448                                 id = parent->qgroupid;
 449
 450                                 BUG_ON(!count);
 451
 452                                 ret = ulist_add(counts, id, ptr_to_u64(parent),
 453                                                 0);
 454                                 if (ret < 0)
 455                                         goto out;
 456                                 ret = ulist_add(tmp, id, ptr_to_u64(parent),
 457                                                 0);
 458                                 if (ret < 0)
 459                                         goto out;
 460                         }
 461                 }
 462         }
 463
 464         /*
 465          * Now that we have gathered up and counted all the groups, we
 466          * can add bytes for this ref.
 467          */
 468         nr_roots = roots->nnodes;
 469         ULIST_ITER_INIT(&uiter);
 470         while ((unode = ulist_next(counts, &uiter))) {
 471                 count = u64_to_ptr(unode->aux);
 472
 473                 nr_refs = group_get_cur_refcnt(count);
 474                 if (nr_refs) {
 475                         count->info.referenced += num_bytes;
 476                         count->info.referenced_compressed += num_bytes;
 477
 478                         if (nr_refs == nr_roots) {
 479                                 count->info.exclusive += num_bytes;
 480                                 count->info.exclusive_compressed += num_bytes;
 481                         }
 482                 }
 483 #ifdef QGROUP_VERIFY_DEBUG
 484                 printf("account (%llu, %llu), qgroup %llu/%llu, rfer %llu,"
 485                        " excl %llu, refs %llu, roots %llu\n", bytenr, num_bytes,
 486                        btrfs_qgroup_level(count->qgroupid),
 487                        btrfs_qgroup_subvid(count->qgroupid),
 488                        count->info.referenced, count->info.exclusive, nr_refs,
 489                        nr_roots);
 490 #endif
 491         }
 492
 493         inc_qgroup_seq(roots->nnodes);
 494         ret = 0;
 495 out:
 496         ulist_free(counts);
 497         ulist_free(tmp);
 498         return ret;
 499 }
 500
 501 static void print_subvol_info(u64 subvolid, u64 bytenr, u64 num_bytes,
 502                               struct ulist *roots);
 503 /*
 504  * Account each ref. Walk the refs, for each set of refs in a
 505  * given bytenr:
 506  *
 507  * - add the roots for direct refs to the ref roots ulist
 508  *
 509  * - resolve all possible roots for shared refs, insert each
 510  *   of those into ref_roots ulist (this is a recursive process)
 511  *
 512  * - With all roots resolved we can account the ref - this is done in
 513  *   account_one_extent().
 514  */
 515 static int account_all_refs(int do_qgroups, u64 search_subvol)
 516 {
 517         struct ref *ref;
 518         struct rb_node *node;
 519         u64 bytenr, num_bytes;
 520         struct ulist *roots = ulist_alloc(0);
 521         int ret;
 522
 523         node = rb_first(&by_bytenr);
 524         while (node) {
 525                 ulist_reinit(roots);
 526
 527                 ref = rb_entry(node, struct ref, bytenr_node);
 528                 /*
 529                  * Walk forward through the list of refs for this
 530                  * bytenr, adding roots to our ulist. If it's a full
 531                  * ref, then we have the easy case. Otherwise we need
 532                  * to search for roots.
 533                  */
 534                 bytenr = ref->bytenr;
 535                 num_bytes = ref->num_bytes;
 536                 do {
 537                         BUG_ON(ref->bytenr != bytenr);
 538                         BUG_ON(ref->num_bytes != num_bytes);
 539                         if (ref->root) {
 540                                 if (is_fstree(ref->root)) {
 541                                         if (ulist_add(roots, ref->root, 0, 0) < 0)
 542                                                 goto enomem;
 543                                 }
 544                         } else {
 545                                 ret = find_parent_roots(roots, ref->parent);
 546                                 if (ret < 0)
 547                                         goto enomem;
 548                         }
 549
 550                         /*
 551                          * When we leave this inner loop, node is set
 552                          * to next in our tree and will be turned into
 553                          * a ref object up top
 554                          */
 555                         node = rb_next(node);
 556                         if (node)
 557                                 ref = rb_entry(node, struct ref, bytenr_node);
 558                 } while (node && ref->bytenr == bytenr);
 559
 560                 if (search_subvol)
 561                         print_subvol_info(search_subvol, bytenr, num_bytes,
 562                                           roots);
 563
 564                 if (!do_qgroups)
 565                         continue;
 566
 567                 if (account_one_extent(roots, bytenr, num_bytes))
 568                         goto enomem;
 569         }
 570
 571         ulist_free(roots);
 572         return 0;
 573 enomem:
 574         error("Out of memory while accounting refs for qgroups");
 575         return -ENOMEM;
 576 }
 577
 578 static u64 resolve_one_root(u64 bytenr)
 579 {
 580         struct ref *ref = find_ref_bytenr(bytenr);
 581
 582         BUG_ON(ref == NULL);
 583
 584         if (ref->root)
 585                 return ref->root;
 586         if (ref->parent == bytenr)
 587                 return BTRFS_TREE_RELOC_OBJECTID;
 588         return resolve_one_root(ref->parent);
 589 }
 590
 591 static inline struct tree_block *unode_tree_block(struct ulist_node *unode)
 592 {
 593         return u64_to_ptr(unode->aux);
 594 }
 595 static inline u64 unode_bytenr(struct ulist_node *unode)
 596 {
 597         return unode->val;
 598 }
 599
 600 static int alloc_tree_block(u64 bytenr, u64 num_bytes, int level)
 601 {
 602         struct tree_block *block = calloc(1, sizeof(*block));
 603
 604         if (block) {
 605                 block->num_bytes = num_bytes;
 606                 block->level = level;
 607                 if (ulist_add(tree_blocks, bytenr, ptr_to_u64(block), 0) >= 0)
 608                         return 0;
 609                 free(block);
 610         }
 611         return -ENOMEM;
 612 }
 613
 614 static void free_tree_blocks(void)
 615 {
 616         struct ulist_iterator uiter;
 617         struct ulist_node *unode;
 618
 619         if (!tree_blocks)
 620                 return;
 621
 622         ULIST_ITER_INIT(&uiter);
 623         while ((unode = ulist_next(tree_blocks, &uiter)))
 624                 free(unode_tree_block(unode));
 625         ulist_free(tree_blocks);
 626         tree_blocks = NULL;
 627 }
 628
 629 #ifdef QGROUP_VERIFY_DEBUG
 630 static void print_tree_block(u64 bytenr, struct tree_block *block)
 631 {
 632         struct ref *ref;
 633         struct rb_node *node;
 634
 635         printf("tree block: %llu\t\tlevel: %d\n", (unsigned long long)bytenr,
 636                block->level);
 637
 638         ref = find_ref_bytenr(bytenr);
 639         node = &ref->bytenr_node;
 640         do {
 641                 print_ref(ref);
 642                 node = rb_next(node);
 643                 if (node)
 644                         ref = rb_entry(node, struct ref, bytenr_node);
 645         } while (node && ref->bytenr == bytenr);
 646
 647         printf("\n");
 648 }
 649
 650 static void print_all_tree_blocks(void)
 651 {
 652         struct ulist_iterator uiter;
 653         struct ulist_node *unode;
 654
 655         if (!tree_blocks)
 656                 return;
 657
 658         printf("Listing all found interior tree nodes:\n");
 659
 660         ULIST_ITER_INIT(&uiter);
 661         while ((unode = ulist_next(tree_blocks, &uiter)))
 662                 print_tree_block(unode_bytenr(unode), unode_tree_block(unode));
 663 }
 664 #endif
 665
 666 static int add_refs_for_leaf_items(struct extent_buffer *eb, u64 ref_parent)
 667 {
 668         int nr, i;
 669         int extent_type;
 670         u64 bytenr, num_bytes;
 671         struct btrfs_key key;
 672         struct btrfs_disk_key disk_key;
 673         struct btrfs_file_extent_item *fi;
 674
 675         nr = btrfs_header_nritems(eb);
 676         for (i = 0; i < nr; i++) {
 677                 btrfs_item_key(eb, &disk_key, i);
 678                 btrfs_disk_key_to_cpu(&key, &disk_key);
 679
 680                 if (key.type != BTRFS_EXTENT_DATA_KEY)
 681                         continue;
 682
 683                 fi = btrfs_item_ptr(eb, i, struct btrfs_file_extent_item);
 684                 /* filter out: inline, disk_bytenr == 0, compressed?
 685                  * not if we can avoid it */
 686                 extent_type = btrfs_file_extent_type(eb, fi);
 687
 688                 if (extent_type == BTRFS_FILE_EXTENT_INLINE)
 689                         continue;
 690
 691                 bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
 692                 if (!bytenr)
 693                         continue;
 694
 695                 num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
 696                 if (alloc_ref(bytenr, 0, ref_parent, num_bytes) == NULL)
 697                         return ENOMEM;
 698         }
 699
 700         return 0;
 701 }
 702
 703 static int travel_tree(struct btrfs_fs_info *info, struct btrfs_root *root,
 704                        u64 bytenr, u64 num_bytes, u64 ref_parent)
 705 {
 706         int ret, nr, i;
 707         struct extent_buffer *eb;
 708         u64 new_bytenr;
 709         u64 new_num_bytes;
 710
 711 //      printf("travel_tree: bytenr: %llu\tnum_bytes: %llu\tref_parent: %llu\n",
 712 //             bytenr, num_bytes, ref_parent);
 713
 714         eb = read_tree_block(root, bytenr, num_bytes, 0);
 715         if (!extent_buffer_uptodate(eb))
 716                 return -EIO;
 717
 718         ret = 0;
 719         /* Don't add a ref for our starting tree block to itself */
 720         if (bytenr != ref_parent) {
 721                 if (alloc_ref(bytenr, 0, ref_parent, num_bytes) == NULL)
 722                         return ENOMEM;
 723         }
 724
 725         if (btrfs_is_leaf(eb)) {
 726                 ret = add_refs_for_leaf_items(eb, ref_parent);
 727                 goto out;
 728         }
 729
 730         /*
 731          * Interior nodes are tuples of (key, bytenr) where key is the
 732          * leftmost key in the tree block pointed to by bytenr. We
 733          * don't have to care about key here, just follow the bytenr
 734          * pointer.
 735          */
 736         nr = btrfs_header_nritems(eb);
 737         for (i = 0; i < nr; i++) {
 738                 new_bytenr = btrfs_node_blockptr(eb, i);
 739                 new_num_bytes = root->nodesize;
 740
 741                 ret = travel_tree(info, root, new_bytenr, new_num_bytes,
 742                                   ref_parent);
 743         }
 744
 745 out:
 746         free_extent_buffer(eb);
 747         return ret;
 748 }
 749
 750 static int add_refs_for_implied(struct btrfs_fs_info *info, u64 bytenr,
 751                                 struct tree_block *block)
 752 {
 753         int ret;
 754         u64 root_id = resolve_one_root(bytenr);
 755         struct btrfs_root *root;
 756         struct btrfs_key key;
 757
 758         /* Tree reloc tree doesn't contribute qgroup, skip it */
 759         if (root_id == BTRFS_TREE_RELOC_OBJECTID)
 760                 return 0;
 761         key.objectid = root_id;
 762         key.type = BTRFS_ROOT_ITEM_KEY;
 763         key.offset = (u64)-1;
 764
 765         /*
 766          * XXX: Don't free the root object as we don't know whether it
 767          * came off our fs_info struct or not.
 768          */
 769         root = btrfs_read_fs_root(info, &key);
 770         if (!root || IS_ERR(root))
 771                 return ENOENT;
 772
 773         ret = travel_tree(info, root, bytenr, block->num_bytes, bytenr);
 774         if (ret)
 775                 return ret;
 776
 777         return 0;
 778 }
 779
 780 /*
 781  * Place shared refs in the ref tree for each child of an interior tree node.
 782  */
 783 static int map_implied_refs(struct btrfs_fs_info *info)
 784 {
 785         int ret = 0;
 786         struct ulist_iterator uiter;
 787         struct ulist_node *unode;
 788
 789         ULIST_ITER_INIT(&uiter);
 790         while ((unode = ulist_next(tree_blocks, &uiter))) {
 791                 ret = add_refs_for_implied(info, unode_bytenr(unode),
 792                                            unode_tree_block(unode));
 793                 if (ret)
 794                         goto out;
 795         }
 796 out:
 797         return ret;
 798 }
 799
 800 /*
 801  * insert a new root into the tree.  returns the existing root entry
 802  * if one is already there.  qgroupid is used
 803  * as the key
 804  */
 805 static int insert_count(struct qgroup_count *qc)
 806 {
 807         struct rb_node **p = &counts.root.rb_node;
 808         struct rb_node *parent = NULL;
 809         struct qgroup_count *curr;
 810
 811         while (*p) {
 812                 parent = *p;
 813                 curr = rb_entry(parent, struct qgroup_count, rb_node);
 814
 815                 if (qc->qgroupid < curr->qgroupid)
 816                         p = &(*p)->rb_left;
 817                 else if (qc->qgroupid > curr->qgroupid)
 818                         p = &(*p)->rb_right;
 819                 else
 820                         return EEXIST;
 821         }
 822         counts.num_groups++;
 823         rb_link_node(&qc->rb_node, parent, p);
 824         rb_insert_color(&qc->rb_node, &counts.root);
 825         return 0;
 826 }
 827
 828 static struct qgroup_count *find_count(u64 qgroupid)
 829 {
 830         struct rb_node *n = counts.root.rb_node;
 831         struct qgroup_count *count;
 832
 833         while (n) {
 834                 count = rb_entry(n, struct qgroup_count, rb_node);
 835
 836                 if (qgroupid < count->qgroupid)
 837                         n = n->rb_left;
 838                 else if (qgroupid > count->qgroupid)
 839                         n = n->rb_right;
 840                 else
 841                         return count;
 842         }
 843         return NULL;
 844 }
 845
 846 static struct qgroup_count *alloc_count(struct btrfs_disk_key *key,
 847                                         struct extent_buffer *leaf,
 848                                         struct btrfs_qgroup_info_item *disk)
 849 {
 850         struct qgroup_count *c = calloc(1, sizeof(*c));
 851         struct qgroup_info *item;
 852
 853         if (c) {
 854                 c->qgroupid = btrfs_disk_key_offset(key);
 855                 c->key = *key;
 856
 857                 item = &c->diskinfo;
 858                 item->referenced = btrfs_qgroup_info_referenced(leaf, disk);
 859                 item->referenced_compressed =
 860                         btrfs_qgroup_info_referenced_compressed(leaf, disk);
 861                 item->exclusive = btrfs_qgroup_info_exclusive(leaf, disk);
 862                 item->exclusive_compressed =
 863                         btrfs_qgroup_info_exclusive_compressed(leaf, disk);
 864                 INIT_LIST_HEAD(&c->groups);
 865                 INIT_LIST_HEAD(&c->members);
 866                 INIT_LIST_HEAD(&c->bad_list);
 867
 868                 if (insert_count(c)) {
 869                         free(c);
 870                         c = NULL;
 871                 }
 872         }
 873         return c;
 874 }
 875
 876 static int add_qgroup_relation(u64 memberid, u64 parentid)
 877 {
 878         struct qgroup_count *member;
 879         struct qgroup_count *parent;
 880         struct btrfs_qgroup_list *list;
 881
 882         if (memberid > parentid)
 883                 return 0;
 884
 885         member = find_count(memberid);
 886         parent = find_count(parentid);
 887         if (!member || !parent)
 888                 return -ENOENT;
 889
 890         list = calloc(1, sizeof(*list));
 891         if (!list)
 892                 return -ENOMEM;
 893
 894         list->group = parent;
 895         list->member = member;
 896         list_add_tail(&list->next_group, &member->groups);
 897         list_add_tail(&list->next_member, &parent->members);
 898
 899         return 0;
 900 }
 901
 902 static void read_qgroup_status(struct extent_buffer *eb, int slot,
 903                               struct counts_tree *counts)
 904 {
 905         struct btrfs_qgroup_status_item *status_item;
 906         u64 flags;
 907
 908         status_item = btrfs_item_ptr(eb, slot, struct btrfs_qgroup_status_item);
 909         flags = btrfs_qgroup_status_flags(eb, status_item);
 910         /*
 911          * Since qgroup_inconsist/rescan_running is just one bit,
 912          * assign value directly won't work.
 913          */
 914         counts->qgroup_inconsist = !!(flags &
 915                         BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT);
 916         counts->rescan_running = !!(flags & BTRFS_QGROUP_STATUS_FLAG_RESCAN);
 917 }
 918
 919 static int load_quota_info(struct btrfs_fs_info *info)
 920 {
 921         int ret;
 922         struct btrfs_root *root = info->quota_root;
 923         struct btrfs_root *tmproot;
 924         struct btrfs_path path;
 925         struct btrfs_key key;
 926         struct btrfs_key root_key;
 927         struct btrfs_disk_key disk_key;
 928         struct extent_buffer *leaf;
 929         struct btrfs_qgroup_info_item *item;
 930         struct qgroup_count *count;
 931         int i, nr;
 932         int search_relations = 0;
 933
 934 loop:
 935         /*
 936          * Do 2 passes, the first allocates group counts and reads status
 937          * items. The 2nd pass picks up relation items and glues them to their
 938          * respective count structures.
 939          */
 940         btrfs_init_path(&path);
 941
 942         key.offset = 0;
 943         key.objectid = search_relations ? 0 : BTRFS_QGROUP_RELATION_KEY;
 944         key.type = 0;
 945
 946         ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
 947         if (ret < 0) {
 948                 fprintf(stderr, "ERROR: Couldn't search slot: %d\n", ret);
 949                 goto out;
 950         }
 951
 952         while (1) {
 953                 leaf = path.nodes[0];
 954
 955                 nr = btrfs_header_nritems(leaf);
 956                 for(i = 0; i < nr; i++) {
 957                         btrfs_item_key(leaf, &disk_key, i);
 958                         btrfs_disk_key_to_cpu(&key, &disk_key);
 959
 960                         if (search_relations) {
 961                                 if (key.type == BTRFS_QGROUP_RELATION_KEY) {
 962                                         ret = add_qgroup_relation(key.objectid,
 963                                                                   key.offset);
 964                                         if (ret) {
 965                                                 error("out of memory");
 966                                                 goto out;
 967                                         }
 968                                 }
 969                                 continue;
 970                         }
 971
 972                         if (key.type == BTRFS_QGROUP_STATUS_KEY) {
 973                                 read_qgroup_status(leaf, i, &counts);
 974                                 continue;
 975                         }
 976
 977                         /*
 978                          * At this point, we can ignore anything that
 979                          * isn't a qgroup info.
 980                          */
 981                         if (key.type != BTRFS_QGROUP_INFO_KEY)
 982                                 continue;
 983
 984                         item = btrfs_item_ptr(leaf, i,
 985                                               struct btrfs_qgroup_info_item);
 986
 987                         count = alloc_count(&disk_key, leaf, item);
 988                         if (!count) {
 989                                 ret = ENOMEM;
 990                                 fprintf(stderr, "ERROR: out of memory\n");
 991                                 goto out;
 992                         }
 993
 994                         root_key.objectid = key.offset;
 995                         root_key.type = BTRFS_ROOT_ITEM_KEY;
 996                         root_key.offset = (u64)-1;
 997                         tmproot = btrfs_read_fs_root_no_cache(info, &root_key);
 998                         if (tmproot && !IS_ERR(tmproot)) {
 999                                 count->subvol_exists = 1;
1000                                 btrfs_free_fs_root(tmproot);
1001                         }
1002                 }
1003
1004                 ret = btrfs_next_leaf(root, &path);
1005                 if (ret != 0)
1006                         break;
1007         }
1008
1009         ret = 0;
1010         btrfs_release_path(&path);
1011
1012         if (!search_relations) {
1013                 search_relations = 1;
1014                 goto loop;
1015         }
1016
1017 out:
1018         return ret;
1019 }
1020
1021 static int add_inline_refs(struct btrfs_fs_info *info,
1022                            struct extent_buffer *ei_leaf, int slot,
1023                            u64 bytenr, u64 num_bytes, int meta_item)
1024 {
1025         struct btrfs_extent_item *ei;
1026         struct btrfs_extent_inline_ref *iref;
1027         struct btrfs_extent_data_ref *dref;
1028         u64 flags, root_obj, offset, parent;
1029         u32 item_size = btrfs_item_size_nr(ei_leaf, slot);
1030         int type;
1031         unsigned long end;
1032         unsigned long ptr;
1033
1034         ei = btrfs_item_ptr(ei_leaf, slot, struct btrfs_extent_item);
1035         flags = btrfs_extent_flags(ei_leaf, ei);
1036
1037         if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK && !meta_item) {
1038                 struct btrfs_tree_block_info *tbinfo;
1039                 tbinfo = (struct btrfs_tree_block_info *)(ei + 1);
1040                 iref = (struct btrfs_extent_inline_ref *)(tbinfo + 1);
1041         } else {
1042                 iref = (struct btrfs_extent_inline_ref *)(ei + 1);
1043         }
1044
1045         ptr = (unsigned long)iref;
1046         end = (unsigned long)ei + item_size;
1047         while (ptr < end) {
1048                 iref = (struct btrfs_extent_inline_ref *)ptr;
1049
1050                 parent = root_obj = 0;
1051                 offset = btrfs_extent_inline_ref_offset(ei_leaf, iref);
1052                 type = btrfs_extent_inline_ref_type(ei_leaf, iref);
1053                 switch (type) {
1054                 case BTRFS_TREE_BLOCK_REF_KEY:
1055                         root_obj = offset;
1056                         break;
1057                 case BTRFS_EXTENT_DATA_REF_KEY:
1058                         dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1059                         root_obj = btrfs_extent_data_ref_root(ei_leaf, dref);
1060                         break;
1061                 case BTRFS_SHARED_DATA_REF_KEY:
1062                 case BTRFS_SHARED_BLOCK_REF_KEY:
1063                         parent = offset;
1064                         break;
1065                 default:
1066                         return 1;
1067                 }
1068
1069                 if (alloc_ref(bytenr, root_obj, parent, num_bytes) == NULL)
1070                         return ENOMEM;
1071
1072                 ptr += btrfs_extent_inline_ref_size(type);
1073         }
1074
1075         return 0;
1076 }
1077
1078 static int add_keyed_ref(struct btrfs_fs_info *info,
1079                          struct btrfs_key *key,
1080                          struct extent_buffer *leaf, int slot,
1081                          u64 bytenr, u64 num_bytes)
1082 {
1083         u64 root_obj = 0, parent = 0;
1084         struct btrfs_extent_data_ref *dref;
1085
1086         switch(key->type) {
1087         case BTRFS_TREE_BLOCK_REF_KEY:
1088                 root_obj = key->offset;
1089                 break;
1090         case BTRFS_EXTENT_DATA_REF_KEY:
1091                 dref = btrfs_item_ptr(leaf, slot, struct btrfs_extent_data_ref);
1092                 root_obj = btrfs_extent_data_ref_root(leaf, dref);
1093                 break;
1094         case BTRFS_SHARED_DATA_REF_KEY:
1095         case BTRFS_SHARED_BLOCK_REF_KEY:
1096                 parent = key->offset;
1097                 break;
1098         default:
1099                 return 1;
1100         }
1101
1102         if (alloc_ref(bytenr, root_obj, parent, num_bytes) == NULL)
1103                 return ENOMEM;
1104
1105         return 0;
1106 }
1107
1108 /*
1109  * return value of 0 indicates leaf or not meta data. The code that
1110  * calls this does not need to make a distinction between the two as
1111  * it is only concerned with intermediate blocks which will always
1112  * have level > 0.
1113  */
1114 static int get_tree_block_level(struct btrfs_key *key,
1115                                 struct extent_buffer *ei_leaf,
1116                                 int slot)
1117 {
1118         int level = 0;
1119         int meta_key = key->type == BTRFS_METADATA_ITEM_KEY;
1120         u64 flags;
1121         struct btrfs_extent_item *ei;
1122
1123         ei = btrfs_item_ptr(ei_leaf, slot, struct btrfs_extent_item);
1124         flags = btrfs_extent_flags(ei_leaf, ei);
1125
1126         if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK && !meta_key) {
1127                 struct btrfs_tree_block_info *tbinfo;
1128                 tbinfo = (struct btrfs_tree_block_info *)(ei + 1);
1129                 level = btrfs_tree_block_level(ei_leaf, tbinfo);
1130         } else if (meta_key) {
1131                 /* skinny metadata */
1132                 level = (int)key->offset;
1133         }
1134         return level;
1135 }
1136
1137 /*
1138  * Walk the extent tree, allocating a ref item for every ref and
1139  * storing it in the bytenr tree.
1140  */
1141 static int scan_extents(struct btrfs_fs_info *info,
1142                         u64 start, u64 end)
1143 {
1144         int ret, i, nr, level;
1145         struct btrfs_root *root = info->extent_root;
1146         struct btrfs_key key;
1147         struct btrfs_path path;
1148         struct btrfs_disk_key disk_key;
1149         struct extent_buffer *leaf;
1150         u64 bytenr = 0, num_bytes = 0;
1151
1152         btrfs_init_path(&path);
1153
1154         key.objectid = start;
1155         key.type = 0;
1156         key.offset = 0;
1157
1158         ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
1159         if (ret < 0) {
1160                 fprintf(stderr, "ERROR: Couldn't search slot: %d\n", ret);
1161                 goto out;
1162         }
1163         path.reada = 1;
1164
1165         while (1) {
1166                 leaf = path.nodes[0];
1167
1168                 nr = btrfs_header_nritems(leaf);
1169                 for(i = 0; i < nr; i++) {
1170                         btrfs_item_key(leaf, &disk_key, i);
1171                         btrfs_disk_key_to_cpu(&key, &disk_key);
1172
1173                         if (key.objectid < start)
1174                                 continue;
1175
1176                         if (key.objectid > end)
1177                                 goto done;
1178
1179                         if (key.type == BTRFS_EXTENT_ITEM_KEY ||
1180                             key.type == BTRFS_METADATA_ITEM_KEY) {
1181                                 int meta = 0;
1182
1183                                 tot_extents_scanned++;
1184
1185                                 bytenr = key.objectid;
1186                                 num_bytes = key.offset;
1187                                 if (key.type == BTRFS_METADATA_ITEM_KEY) {
1188                                         num_bytes = info->extent_root->nodesize;
1189                                         meta = 1;
1190                                 }
1191
1192                                 ret = add_inline_refs(info, leaf, i, bytenr,
1193                                                       num_bytes, meta);
1194                                 if (ret)
1195                                         goto out;
1196
1197                                 level = get_tree_block_level(&key, leaf, i);
1198                                 if (level) {
1199                                         if (alloc_tree_block(bytenr, num_bytes,
1200                                                              level))
1201                                                 return ENOMEM;
1202                                 }
1203
1204                                 continue;
1205                         }
1206
1207                         if (key.type > BTRFS_SHARED_DATA_REF_KEY)
1208                                 continue;
1209                         if (key.type < BTRFS_TREE_BLOCK_REF_KEY)
1210                                 continue;
1211
1212                         /*
1213                          * Keyed refs should come after their extent
1214                          * item in the tree. As a result, the value of
1215                          * bytenr and num_bytes should be unchanged
1216                          * from the above block that catches the
1217                          * original extent item.
1218                          */
1219                         BUG_ON(key.objectid != bytenr);
1220
1221                         ret = add_keyed_ref(info, &key, leaf, i, bytenr,
1222                                             num_bytes);
1223                         if (ret)
1224                                 goto out;
1225                 }
1226
1227                 ret = btrfs_next_leaf(root, &path);
1228                 if (ret != 0) {
1229                         if (ret < 0) {
1230                                 fprintf(stderr,
1231                                         "ERROR: Next leaf failed: %d\n", ret);
1232                                 goto out;
1233                         }
1234                         break;
1235                 }
1236         }
1237 done:
1238         ret = 0;
1239 out:
1240         btrfs_release_path(&path);
1241
1242         return ret;
1243 }
1244
1245 static void print_fields(u64 bytes, u64 bytes_compressed, char *prefix,
1246                          char *type)
1247 {
1248         printf("%s\t\t%s %llu %s compressed %llu\n",
1249                prefix, type, (unsigned long long)bytes, type,
1250                (unsigned long long)bytes_compressed);
1251 }
1252
1253 static void print_fields_signed(long long bytes,
1254                                 long long bytes_compressed,
1255                                 char *prefix, char *type)
1256 {
1257         printf("%s\t\t%s %lld %s compressed %lld\n",
1258                prefix, type, bytes, type, bytes_compressed);
1259 }
1260
1261 static inline int qgroup_printable(struct qgroup_count *c)
1262 {
1263         return !!(c->subvol_exists || btrfs_qgroup_level(c->qgroupid));
1264 }
1265
1266 static int report_qgroup_difference(struct qgroup_count *count, int verbose)
1267 {
1268         int is_different;
1269         struct qgroup_info *info = &count->info;
1270         struct qgroup_info *disk = &count->diskinfo;
1271         long long excl_diff = info->exclusive - disk->exclusive;
1272         long long ref_diff = info->referenced - disk->referenced;
1273
1274         is_different = excl_diff || ref_diff;
1275
1276         if (verbose || (is_different && qgroup_printable(count))) {
1277                 printf("Counts for qgroup id: %llu/%llu %s\n",
1278                        btrfs_qgroup_level(count->qgroupid),
1279                        btrfs_qgroup_subvid(count->qgroupid),
1280                        is_different ? "are different" : "");
1281
1282                 print_fields(info->referenced, info->referenced_compressed,
1283                              "our:", "referenced");
1284                 print_fields(disk->referenced, disk->referenced_compressed,
1285                              "disk:", "referenced");
1286                 if (ref_diff)
1287                         print_fields_signed(ref_diff, ref_diff,
1288                                             "diff:", "referenced");
1289                 print_fields(info->exclusive, info->exclusive_compressed,
1290                              "our:", "exclusive");
1291                 print_fields(disk->exclusive, disk->exclusive_compressed,
1292                              "disk:", "exclusive");
1293                 if (excl_diff)
1294                         print_fields_signed(excl_diff, excl_diff,
1295                                             "diff:", "exclusive");
1296         }
1297
1298         return is_different;
1299 }
1300
1301 void report_qgroups(int all)
1302 {
1303         struct rb_node *node;
1304         struct qgroup_count *c;
1305
1306         if (!repair && counts.rescan_running) {
1307                 if (all) {
1308                         printf(
1309         "Qgroup rescan is running, a difference in qgroup counts is expected\n");
1310                 } else {
1311                         printf(
1312         "Qgroup rescan is running, qgroups will not be printed.\n");
1313                         return;
1314                 }
1315         }
1316         if (counts.qgroup_inconsist && !counts.rescan_running)
1317                 fprintf(stderr, "Qgroup are marked as inconsistent.\n");
1318         node = rb_first(&counts.root);
1319         while (node) {
1320                 c = rb_entry(node, struct qgroup_count, rb_node);
1321
1322                 if (report_qgroup_difference(c, all))
1323                         list_add_tail(&c->bad_list, &bad_qgroups);
1324
1325                 node = rb_next(node);
1326         }
1327 }
1328
1329 void free_qgroup_counts(void)
1330 {
1331         struct rb_node *node;
1332         struct qgroup_count *c;
1333         struct btrfs_qgroup_list *glist, *tmpglist;
1334
1335         node = rb_first(&counts.root);
1336         while (node) {
1337                 c = rb_entry(node, struct qgroup_count, rb_node);
1338
1339                 list_del(&c->bad_list);
1340
1341                 list_for_each_entry_safe(glist, tmpglist, &c->groups,
1342                                          next_group) {
1343                         list_del(&glist->next_group);
1344                         list_del(&glist->next_member);
1345                         free(glist);
1346                 }
1347                 list_for_each_entry_safe(glist, tmpglist, &c->members,
1348                                          next_group) {
1349                         list_del(&glist->next_group);
1350                         list_del(&glist->next_member);
1351                         free(glist);
1352                 }
1353
1354                 node = rb_next(node);
1355
1356                 rb_erase(&c->rb_node, &counts.root);
1357                 free(c);
1358         }
1359 }
1360
1361 int qgroup_verify_all(struct btrfs_fs_info *info)
1362 {
1363         int ret;
1364
1365         if (!info->quota_enabled)
1366                 return 0;
1367
1368         tree_blocks = ulist_alloc(0);
1369         if (!tree_blocks) {
1370                 fprintf(stderr,
1371                         "ERROR: Out of memory while allocating ulist.\n");
1372                 return ENOMEM;
1373         }
1374
1375         ret = load_quota_info(info);
1376         if (ret) {
1377                 fprintf(stderr, "ERROR: Loading qgroups from disk: %d\n", ret);
1378                 goto out;
1379         }
1380
1381         /*
1382          * Put all extent refs into our rbtree
1383          */
1384         ret = scan_extents(info, 0, ~0ULL);
1385         if (ret) {
1386                 fprintf(stderr, "ERROR: while scanning extent tree: %d\n", ret);
1387                 goto out;
1388         }
1389
1390         ret = map_implied_refs(info);
1391         if (ret) {
1392                 fprintf(stderr, "ERROR: while mapping refs: %d\n", ret);
1393                 goto out;
1394         }
1395
1396         ret = account_all_refs(1, 0);
1397
1398 out:
1399         /*
1400          * Don't free the qgroup count records as they will be walked
1401          * later via the print function.
1402          */
1403         free_tree_blocks();
1404         free_ref_tree(&by_bytenr);
1405         return ret;
1406 }
1407
1408 static void __print_subvol_info(u64 bytenr, u64 num_bytes, struct ulist *roots)
1409 {
1410         int n = roots->nnodes;
1411         struct ulist_iterator uiter;
1412         struct ulist_node *unode;
1413
1414         printf("%llu\t%llu\t%d\t", bytenr, num_bytes, n);
1415
1416         ULIST_ITER_INIT(&uiter);
1417         while ((unode = ulist_next(roots, &uiter))) {
1418                 printf("%llu ", unode->val);
1419         }
1420         printf("\n");
1421 }
1422
1423 static void print_subvol_info(u64 subvolid, u64 bytenr, u64 num_bytes,
1424                               struct ulist *roots)
1425 {
1426         struct ulist_iterator uiter;
1427         struct ulist_node *unode;
1428
1429         ULIST_ITER_INIT(&uiter);
1430         while ((unode = ulist_next(roots, &uiter))) {
1431                 BUG_ON(unode->val == 0ULL);
1432                 if (unode->val == subvolid) {
1433                         __print_subvol_info(bytenr, num_bytes, roots);
1434                         return;
1435                 }
1436         }
1437
1438
1439 }
1440
1441 int print_extent_state(struct btrfs_fs_info *info, u64 subvol)
1442 {
1443         int ret;
1444
1445         tree_blocks = ulist_alloc(0);
1446         if (!tree_blocks) {
1447                 fprintf(stderr,
1448                         "ERROR: Out of memory while allocating ulist.\n");
1449                 return ENOMEM;
1450         }
1451
1452         /*
1453          * Put all extent refs into our rbtree
1454          */
1455         ret = scan_extents(info, 0, ~0ULL);
1456         if (ret) {
1457                 fprintf(stderr, "ERROR: while scanning extent tree: %d\n", ret);
1458                 goto out;
1459         }
1460
1461         ret = map_implied_refs(info);
1462         if (ret) {
1463                 fprintf(stderr, "ERROR: while mapping refs: %d\n", ret);
1464                 goto out;
1465         }
1466
1467         printf("Offset\t\tLen\tRoot Refs\tRoots\n");
1468         ret = account_all_refs(0, subvol);
1469
1470 out:
1471         free_tree_blocks();
1472         free_ref_tree(&by_bytenr);
1473         return ret;
1474 }
1475
1476 static int repair_qgroup_info(struct btrfs_fs_info *info,
1477                               struct qgroup_count *count)
1478 {
1479         int ret;
1480         struct btrfs_root *root = info->quota_root;
1481         struct btrfs_trans_handle *trans;
1482         struct btrfs_path *path;
1483         struct btrfs_qgroup_info_item *info_item;
1484         struct btrfs_key key;
1485
1486         printf("Repair qgroup %llu/%llu\n", btrfs_qgroup_level(count->qgroupid),
1487                btrfs_qgroup_subvid(count->qgroupid));
1488
1489         path = btrfs_alloc_path();
1490         if (!path)
1491                 return -ENOMEM;
1492
1493         trans = btrfs_start_transaction(root, 1);
1494         if (IS_ERR(trans)) {
1495                 btrfs_free_path(path);
1496                 return PTR_ERR(trans);
1497         }
1498
1499         key.objectid = 0;
1500         key.type = BTRFS_QGROUP_INFO_KEY;
1501         key.offset = count->qgroupid;
1502         ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
1503         if (ret) {
1504                 error("Could not find disk item for qgroup %llu/%llu.\n",
1505                       btrfs_qgroup_level(count->qgroupid),
1506                       btrfs_qgroup_subvid(count->qgroupid));
1507                 if (ret > 0)
1508                         ret = -ENOENT;
1509                 goto out;
1510         }
1511
1512         info_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
1513                                    struct btrfs_qgroup_info_item);
1514
1515         btrfs_set_qgroup_info_generation(path->nodes[0], info_item,
1516                                          trans->transid);
1517
1518         btrfs_set_qgroup_info_referenced(path->nodes[0], info_item,
1519                                          count->info.referenced);
1520         btrfs_set_qgroup_info_referenced_compressed(path->nodes[0], info_item,
1521                                             count->info.referenced_compressed);
1522
1523         btrfs_set_qgroup_info_exclusive(path->nodes[0], info_item,
1524                                         count->info.exclusive);
1525         btrfs_set_qgroup_info_exclusive_compressed(path->nodes[0], info_item,
1526                                            count->info.exclusive_compressed);
1527
1528         btrfs_mark_buffer_dirty(path->nodes[0]);
1529
1530 out:
1531         btrfs_commit_transaction(trans, root);
1532         btrfs_free_path(path);
1533
1534         return ret;
1535 }
1536
1537 static int repair_qgroup_status(struct btrfs_fs_info *info)
1538 {
1539         int ret;
1540         struct btrfs_root *root = info->quota_root;
1541         struct btrfs_trans_handle *trans;
1542         struct btrfs_path *path;
1543         struct btrfs_key key;
1544         struct btrfs_qgroup_status_item *status_item;
1545
1546         printf("Repair qgroup status item\n");
1547
1548         path = btrfs_alloc_path();
1549         if (!path)
1550                 return -ENOMEM;
1551
1552         trans = btrfs_start_transaction(root, 1);
1553         if (IS_ERR(trans)) {
1554                 btrfs_free_path(path);
1555                 return PTR_ERR(trans);
1556         }
1557
1558         key.objectid = 0;
1559         key.type = BTRFS_QGROUP_STATUS_KEY;
1560         key.offset = 0;
1561         ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
1562         if (ret) {
1563                 error("Could not find qgroup status item\n");
1564                 if (ret > 0)
1565                         ret = -ENOENT;
1566                 goto out;
1567         }
1568
1569         status_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
1570                                      struct btrfs_qgroup_status_item);
1571         btrfs_set_qgroup_status_flags(path->nodes[0], status_item,
1572                                       BTRFS_QGROUP_STATUS_FLAG_ON);
1573         btrfs_set_qgroup_status_rescan(path->nodes[0], status_item, 0);
1574         btrfs_set_qgroup_status_generation(path->nodes[0], status_item,
1575                                            trans->transid);
1576
1577         btrfs_mark_buffer_dirty(path->nodes[0]);
1578
1579 out:
1580         btrfs_commit_transaction(trans, root);
1581         btrfs_free_path(path);
1582
1583         return ret;
1584 }
1585
1586 int repair_qgroups(struct btrfs_fs_info *info, int *repaired)
1587 {
1588         int ret;
1589         struct qgroup_count *count, *tmpcount;
1590
1591         *repaired = 0;
1592
1593         if (!repair)
1594                 return 0;
1595
1596         list_for_each_entry_safe(count, tmpcount, &bad_qgroups, bad_list) {
1597                 ret = repair_qgroup_info(info, count);
1598                 if (ret) {
1599                         goto out;
1600                 }
1601
1602                 (*repaired)++;
1603
1604                 list_del_init(&count->bad_list);
1605         }
1606
1607         /*
1608          * Do this step last as we want the latest transaction id on
1609          * our qgroup status to avoid a (useless) warning after
1610          * mount.
1611          */
1612         if (*repaired || counts.qgroup_inconsist || counts.rescan_running) {
1613                 ret = repair_qgroup_status(info);
1614                 if (ret)
1615                         goto out;
1616
1617                 (*repaired)++;
1618         }
1619
1620 out:
1621         return ret;
1622 }