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