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