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