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