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