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