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