btrfs-list.c

   1 /*
   2  * Copyright (C) 2010 Oracle.  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
  19 #define _GNU_SOURCE
  20 #ifndef __CHECKER__
  21 #include <sys/ioctl.h>
  22 #include <sys/mount.h>
  23 #include "ioctl.h"
  24 #endif
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <sys/types.h>
  28 #include <sys/stat.h>
  29 #include <fcntl.h>
  30 #include <unistd.h>
  31 #include <dirent.h>
  32 #include <libgen.h>
  33 #include "kerncompat.h"
  34 #include "ctree.h"
  35 #include "transaction.h"
  36 #include "utils.h"
  37
  38 /* we store all the roots we find in an rbtree so that we can
  39  * search for them later.
  40  */
  41 struct root_lookup {
  42         struct rb_root root;
  43 };
  44
  45 /*
  46  * one of these for each root we find.
  47  */
  48 struct root_info {
  49         struct rb_node rb_node;
  50
  51         /* this root's id */
  52         u64 root_id;
  53
  54         /* the id of the root that references this one */
  55         u64 ref_tree;
  56
  57         /* the dir id we're in from ref_tree */
  58         u64 dir_id;
  59
  60         /* path from the subvol we live in to this root, including the
  61          * root's name.  This is null until we do the extra lookup ioctl.
  62          */
  63         char *path;
  64
  65         /* the name of this root in the directory it lives in */
  66         char name[];
  67 };
  68
  69 static void root_lookup_init(struct root_lookup *tree)
  70 {
  71         tree->root.rb_node = NULL;
  72 }
  73
  74 static int comp_entry(struct root_info *entry, u64 root_id, u64 ref_tree)
  75 {
  76         if (entry->root_id > root_id)
  77                 return 1;
  78         if (entry->root_id < root_id)
  79                 return -1;
  80         if (entry->ref_tree > ref_tree)
  81                 return 1;
  82         if (entry->ref_tree < ref_tree)
  83                 return -1;
  84         return 0;
  85 }
  86
  87 /*
  88  * insert a new root into the tree.  returns the existing root entry
  89  * if one is already there.  Both root_id and ref_tree are used
  90  * as the key
  91  */
  92 static struct rb_node *tree_insert(struct rb_root *root, u64 root_id,
  93                                    u64 ref_tree, struct rb_node *node)
  94 {
  95         struct rb_node ** p = &root->rb_node;
  96         struct rb_node * parent = NULL;
  97         struct root_info *entry;
  98         int comp;
  99
 100         while(*p) {
 101                 parent = *p;
 102                 entry = rb_entry(parent, struct root_info, rb_node);
 103
 104                 comp = comp_entry(entry, root_id, ref_tree);
 105
 106                 if (comp < 0)
 107                         p = &(*p)->rb_left;
 108                 else if (comp > 0)
 109                         p = &(*p)->rb_right;
 110                 else
 111                         return parent;
 112         }
 113
 114         entry = rb_entry(parent, struct root_info, rb_node);
 115         rb_link_node(node, parent, p);
 116         rb_insert_color(node, root);
 117         return NULL;
 118 }
 119
 120 /*
 121  * find a given root id in the tree.  We return the smallest one,
 122  * rb_next can be used to move forward looking for more if required
 123  */
 124 static struct root_info *tree_search(struct rb_root *root, u64 root_id)
 125 {
 126         struct rb_node * n = root->rb_node;
 127         struct root_info *entry;
 128
 129         while(n) {
 130                 entry = rb_entry(n, struct root_info, rb_node);
 131
 132                 if (entry->root_id < root_id)
 133                         n = n->rb_left;
 134                 else if (entry->root_id > root_id)
 135                         n = n->rb_right;
 136                 else {
 137                         struct root_info *prev;
 138                         struct rb_node *prev_n;
 139                         while (1) {
 140                                 prev_n = rb_prev(n);
 141                                 if (!prev_n)
 142                                         break;
 143                                 prev = rb_entry(prev_n, struct root_info,
 144                                                       rb_node);
 145                                 if (prev->root_id != root_id)
 146                                         break;
 147                                 entry = prev;
 148                                 n = prev_n;
 149                         }
 150                         return entry;
 151                 }
 152         }
 153         return NULL;
 154 }
 155
 156 /*
 157  * this allocates a new root in the lookup tree.
 158  *
 159  * root_id should be the object id of the root
 160  *
 161  * ref_tree is the objectid of the referring root.
 162  *
 163  * dir_id is the directory in ref_tree where this root_id can be found.
 164  *
 165  * name is the name of root_id in that directory
 166  *
 167  * name_len is the length of name
 168  */
 169 static int add_root(struct root_lookup *root_lookup,
 170                     u64 root_id, u64 ref_tree, u64 dir_id, char *name,
 171                     int name_len)
 172 {
 173         struct root_info *ri;
 174         struct rb_node *ret;
 175         ri = malloc(sizeof(*ri) + name_len + 1);
 176         if (!ri) {
 177                 printf("memory allocation failed\n");
 178                 exit(1);
 179         }
 180         memset(ri, 0, sizeof(*ri) + name_len + 1);
 181         ri->path = NULL;
 182         ri->dir_id = dir_id;
 183         ri->root_id = root_id;
 184         ri->ref_tree = ref_tree;
 185         strncpy(ri->name, name, name_len);
 186         if (name_len > 0)
 187                 ri->name[name_len] = 0;
 188
 189         ret = tree_insert(&root_lookup->root, root_id, ref_tree, &ri->rb_node);
 190         if (ret) {
 191                 printf("failed to insert tree %llu\n", (unsigned long long)root_id);
 192                 exit(1);
 193         }
 194         return 0;
 195 }
 196
 197 /*
 198  * for a given root_info, search through the root_lookup tree to construct
 199  * the full path name to it.
 200  *
 201  * This can't be called until all the root_info->path fields are filled
 202  * in by lookup_ino_path
 203  */
 204 static int resolve_root(struct root_lookup *rl, struct root_info *ri,
 205                         u64 *parent_id, u64 *top_id, char **path)
 206 {
 207         char *full_path = NULL;
 208         int len = 0;
 209         struct root_info *found;
 210
 211         /*
 212          * we go backwards from the root_info object and add pathnames
 213          * from parent directories as we go.
 214          */
 215         *parent_id = 0;
 216         found = ri;
 217         while (1) {
 218                 char *tmp;
 219                 u64 next;
 220                 int add_len = strlen(found->path);
 221
 222                 /* room for / and for null */
 223                 tmp = malloc(add_len + 2 + len);
 224                 if (full_path) {
 225                         memcpy(tmp + add_len + 1, full_path, len);
 226                         tmp[add_len] = '/';
 227                         memcpy(tmp, found->path, add_len);
 228                         tmp [add_len + len + 1] = '\0';
 229                         free(full_path);
 230                         full_path = tmp;
 231                         len += add_len + 1;
 232                 } else {
 233                         full_path = strdup(found->path);
 234                         len = add_len;
 235                 }
 236
 237                 next = found->ref_tree;
 238                 /* record the first parent */
 239                 if (*parent_id == 0)
 240                         *parent_id = next;
 241
 242                 /* if the ref_tree refers to ourselves, we're at the top */
 243                 if (next == found->root_id) {
 244                         *top_id = next;
 245                         break;
 246                 }
 247
 248                 /*
 249                  * if the ref_tree wasn't in our tree of roots, we're
 250                  * at the top
 251                  */
 252                 found = tree_search(&rl->root, next);
 253                 if (!found) {
 254                         *top_id = next;
 255                         break;
 256                 }
 257         }
 258
 259         *path = full_path;
 260
 261         return 0;
 262 }
 263
 264 /*
 265  * for a single root_info, ask the kernel to give us a path name
 266  * inside it's ref_root for the dir_id where it lives.
 267  *
 268  * This fills in root_info->path with the path to the directory and and
 269  * appends this root's name.
 270  */
 271 static int lookup_ino_path(int fd, struct root_info *ri)
 272 {
 273         struct btrfs_ioctl_ino_lookup_args args;
 274         int ret, e;
 275
 276         if (ri->path)
 277                 return 0;
 278
 279         memset(&args, 0, sizeof(args));
 280         args.treeid = ri->ref_tree;
 281         args.objectid = ri->dir_id;
 282
 283         ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &args);
 284         e = errno;
 285         if (ret) {
 286                 fprintf(stderr, "ERROR: Failed to lookup path for root %llu - %s\n",
 287                         (unsigned long long)ri->ref_tree,
 288                         strerror(e));
 289                 return ret;
 290         }
 291
 292         if (args.name[0]) {
 293                 /*
 294                  * we're in a subdirectory of ref_tree, the kernel ioctl
 295                  * puts a / in there for us
 296                  */
 297                 ri->path = malloc(strlen(ri->name) + strlen(args.name) + 1);
 298                 if (!ri->path) {
 299                         perror("malloc failed");
 300                         exit(1);
 301                 }
 302                 strcpy(ri->path, args.name);
 303                 strcat(ri->path, ri->name);
 304         } else {
 305                 /* we're at the root of ref_tree */
 306                 ri->path = strdup(ri->name);
 307                 if (!ri->path) {
 308                         perror("strdup failed");
 309                         exit(1);
 310                 }
 311         }
 312         return 0;
 313 }
 314
 315 /* finding the generation for a given path is a two step process.
 316  * First we use the inode loookup routine to find out the root id
 317  *
 318  * Then we use the tree search ioctl to scan all the root items for a
 319  * given root id and spit out the latest generation we can find
 320  */
 321 static u64 find_root_gen(int fd)
 322 {
 323         struct btrfs_ioctl_ino_lookup_args ino_args;
 324         int ret;
 325         struct btrfs_ioctl_search_args args;
 326         struct btrfs_ioctl_search_key *sk = &args.key;
 327         struct btrfs_ioctl_search_header *sh;
 328         unsigned long off = 0;
 329         u64 max_found = 0;
 330         int i;
 331         int e;
 332
 333         memset(&ino_args, 0, sizeof(ino_args));
 334         ino_args.objectid = BTRFS_FIRST_FREE_OBJECTID;
 335
 336         /* this ioctl fills in ino_args->treeid */
 337         ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &ino_args);
 338         e = errno;
 339         if (ret) {
 340                 fprintf(stderr, "ERROR: Failed to lookup path for dirid %llu - %s\n",
 341                         (unsigned long long)BTRFS_FIRST_FREE_OBJECTID,
 342                         strerror(e));
 343                 return 0;
 344         }
 345
 346         memset(&args, 0, sizeof(args));
 347
 348         sk->tree_id = 1;
 349
 350         /*
 351          * there may be more than one ROOT_ITEM key if there are
 352          * snapshots pending deletion, we have to loop through
 353          * them.
 354          */
 355         sk->min_objectid = ino_args.treeid;
 356         sk->max_objectid = ino_args.treeid;
 357         sk->max_type = BTRFS_ROOT_ITEM_KEY;
 358         sk->min_type = BTRFS_ROOT_ITEM_KEY;
 359         sk->max_offset = (u64)-1;
 360         sk->max_transid = (u64)-1;
 361         sk->nr_items = 4096;
 362
 363         while (1) {
 364                 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 365                 e = errno;
 366                 if (ret < 0) {
 367                         fprintf(stderr, "ERROR: can't perform the search - %s\n",
 368                                 strerror(e));
 369                         return 0;
 370                 }
 371                 /* the ioctl returns the number of item it found in nr_items */
 372                 if (sk->nr_items == 0)
 373                         break;
 374
 375                 off = 0;
 376                 for (i = 0; i < sk->nr_items; i++) {
 377                         struct btrfs_root_item *item;
 378                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 379                                                                   off);
 380
 381                         off += sizeof(*sh);
 382                         item = (struct btrfs_root_item *)(args.buf + off);
 383                         off += sh->len;
 384
 385                         sk->min_objectid = sh->objectid;
 386                         sk->min_type = sh->type;
 387                         sk->min_offset = sh->offset;
 388
 389                         if (sh->objectid > ino_args.treeid)
 390                                 break;
 391
 392                         if (sh->objectid == ino_args.treeid &&
 393                             sh->type == BTRFS_ROOT_ITEM_KEY) {
 394                                 max_found = max(max_found,
 395                                                 btrfs_root_generation(item));
 396                         }
 397                 }
 398                 if (sk->min_offset < (u64)-1)
 399                         sk->min_offset++;
 400                 else
 401                         break;
 402
 403                 if (sk->min_type != BTRFS_ROOT_ITEM_KEY)
 404                         break;
 405                 if (sk->min_objectid != BTRFS_ROOT_ITEM_KEY)
 406                         break;
 407         }
 408         return max_found;
 409 }
 410
 411 /* pass in a directory id and this will return
 412  * the full path of the parent directory inside its
 413  * subvolume root.
 414  *
 415  * It may return NULL if it is in the root, or an ERR_PTR if things
 416  * go badly.
 417  */
 418 static char *__ino_resolve(int fd, u64 dirid)
 419 {
 420         struct btrfs_ioctl_ino_lookup_args args;
 421         int ret;
 422         char *full;
 423         int e;
 424
 425         memset(&args, 0, sizeof(args));
 426         args.objectid = dirid;
 427
 428         ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &args);
 429         e = errno;
 430         if (ret) {
 431                 fprintf(stderr, "ERROR: Failed to lookup path for dirid %llu - %s\n",
 432                         (unsigned long long)dirid, strerror(e) );
 433                 return ERR_PTR(ret);
 434         }
 435
 436         if (args.name[0]) {
 437                 /*
 438                  * we're in a subdirectory of ref_tree, the kernel ioctl
 439                  * puts a / in there for us
 440                  */
 441                 full = strdup(args.name);
 442                 if (!full) {
 443                         perror("malloc failed");
 444                         return ERR_PTR(-ENOMEM);
 445                 }
 446         } else {
 447                 /* we're at the root of ref_tree */
 448                 full = NULL;
 449         }
 450         return full;
 451 }
 452
 453 /*
 454  * simple string builder, returning a new string with both
 455  * dirid and name
 456  */
 457 char *build_name(char *dirid, char *name)
 458 {
 459         char *full;
 460         if (!dirid)
 461                 return strdup(name);
 462
 463         full = malloc(strlen(dirid) + strlen(name) + 1);
 464         if (!full)
 465                 return NULL;
 466         strcpy(full, dirid);
 467         strcat(full, name);
 468         return full;
 469 }
 470
 471 /*
 472  * given an inode number, this returns the full path name inside the subvolume
 473  * to that file/directory.  cache_dirid and cache_name are used to
 474  * cache the results so we can avoid tree searches if a later call goes
 475  * to the same directory or file name
 476  */
 477 static char *ino_resolve(int fd, u64 ino, u64 *cache_dirid, char **cache_name)
 478
 479 {
 480         u64 dirid;
 481         char *dirname;
 482         char *name;
 483         char *full;
 484         int ret;
 485         struct btrfs_ioctl_search_args args;
 486         struct btrfs_ioctl_search_key *sk = &args.key;
 487         struct btrfs_ioctl_search_header *sh;
 488         unsigned long off = 0;
 489         int namelen;
 490         int e;
 491
 492         memset(&args, 0, sizeof(args));
 493
 494         sk->tree_id = 0;
 495
 496         /*
 497          * step one, we search for the inode back ref.  We just use the first
 498          * one
 499          */
 500         sk->min_objectid = ino;
 501         sk->max_objectid = ino;
 502         sk->max_type = BTRFS_INODE_REF_KEY;
 503         sk->max_offset = (u64)-1;
 504         sk->min_type = BTRFS_INODE_REF_KEY;
 505         sk->max_transid = (u64)-1;
 506         sk->nr_items = 1;
 507
 508         ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 509         e = errno;
 510         if (ret < 0) {
 511                 fprintf(stderr, "ERROR: can't perform the search - %s\n",
 512                         strerror(e));
 513                 return NULL;
 514         }
 515         /* the ioctl returns the number of item it found in nr_items */
 516         if (sk->nr_items == 0)
 517                 return NULL;
 518
 519         off = 0;
 520         sh = (struct btrfs_ioctl_search_header *)(args.buf + off);
 521
 522         if (sh->type == BTRFS_INODE_REF_KEY) {
 523                 struct btrfs_inode_ref *ref;
 524                 dirid = sh->offset;
 525
 526                 ref = (struct btrfs_inode_ref *)(sh + 1);
 527                 namelen = btrfs_stack_inode_ref_name_len(ref);
 528
 529                 name = (char *)(ref + 1);
 530                 name = strndup(name, namelen);
 531
 532                 /* use our cached value */
 533                 if (dirid == *cache_dirid && *cache_name) {
 534                         dirname = *cache_name;
 535                         goto build;
 536                 }
 537         } else {
 538                 return NULL;
 539         }
 540         /*
 541          * the inode backref gives us the file name and the parent directory id.
 542          * From here we use __ino_resolve to get the path to the parent
 543          */
 544         dirname = __ino_resolve(fd, dirid);
 545 build:
 546         full = build_name(dirname, name);
 547         if (*cache_name && dirname != *cache_name)
 548                 free(*cache_name);
 549
 550         *cache_name = dirname;
 551         *cache_dirid = dirid;
 552         free(name);
 553
 554         return full;
 555 }
 556
 557 static int get_default_subvolid(int fd, u64 *default_id)
 558 {
 559         struct btrfs_ioctl_search_args args;
 560         struct btrfs_ioctl_search_key *sk = &args.key;
 561         struct btrfs_ioctl_search_header *sh;
 562         u64 found = 0;
 563         int ret;
 564
 565         memset(&args, 0, sizeof(args));
 566
 567         /*
 568          * search for a dir item with a name 'default' in the tree of
 569          * tree roots, it should point us to a default root
 570          */
 571         sk->tree_id = 1;
 572
 573         /* don't worry about ancient format and request only one item */
 574         sk->nr_items = 1;
 575
 576         sk->max_objectid = BTRFS_ROOT_TREE_DIR_OBJECTID;
 577         sk->min_objectid = BTRFS_ROOT_TREE_DIR_OBJECTID;
 578         sk->max_type = BTRFS_DIR_ITEM_KEY;
 579         sk->min_type = BTRFS_DIR_ITEM_KEY;
 580         sk->max_offset = (u64)-1;
 581         sk->max_transid = (u64)-1;
 582
 583         ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 584         if (ret < 0)
 585                 return ret;
 586
 587         /* the ioctl returns the number of items it found in nr_items */
 588         if (sk->nr_items == 0)
 589                 goto out;
 590
 591         sh = (struct btrfs_ioctl_search_header *)args.buf;
 592
 593         if (sh->type == BTRFS_DIR_ITEM_KEY) {
 594                 struct btrfs_dir_item *di;
 595                 int name_len;
 596                 char *name;
 597
 598                 di = (struct btrfs_dir_item *)(sh + 1);
 599                 name_len = btrfs_stack_dir_name_len(di);
 600                 name = (char *)(di + 1);
 601
 602                 if (!strncmp("default", name, name_len))
 603                         found = btrfs_disk_key_objectid(&di->location);
 604         }
 605
 606 out:
 607         *default_id = found;
 608         return 0;
 609 }
 610
 611 static int __list_subvol_search(int fd, struct root_lookup *root_lookup)
 612 {
 613         int ret;
 614         struct btrfs_ioctl_search_args args;
 615         struct btrfs_ioctl_search_key *sk = &args.key;
 616         struct btrfs_ioctl_search_header *sh;
 617         struct btrfs_root_ref *ref;
 618         unsigned long off = 0;
 619         int name_len;
 620         char *name;
 621         u64 dir_id;
 622         int i;
 623
 624         root_lookup_init(root_lookup);
 625         memset(&args, 0, sizeof(args));
 626
 627         /* search in the tree of tree roots */
 628         sk->tree_id = 1;
 629
 630         /*
 631          * set the min and max to backref keys.  The search will
 632          * only send back this type of key now.
 633          */
 634         sk->max_type = BTRFS_ROOT_BACKREF_KEY;
 635         sk->min_type = BTRFS_ROOT_BACKREF_KEY;
 636
 637         sk->min_objectid = BTRFS_FIRST_FREE_OBJECTID;
 638
 639         /*
 640          * set all the other params to the max, we'll take any objectid
 641          * and any trans
 642          */
 643         sk->max_objectid = BTRFS_LAST_FREE_OBJECTID;
 644         sk->max_offset = (u64)-1;
 645         sk->max_transid = (u64)-1;
 646
 647         /* just a big number, doesn't matter much */
 648         sk->nr_items = 4096;
 649
 650         while(1) {
 651                 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 652                 if (ret < 0)
 653                         return ret;
 654                 /* the ioctl returns the number of item it found in nr_items */
 655                 if (sk->nr_items == 0)
 656                         break;
 657
 658                 off = 0;
 659
 660                 /*
 661                  * for each item, pull the key out of the header and then
 662                  * read the root_ref item it contains
 663                  */
 664                 for (i = 0; i < sk->nr_items; i++) {
 665                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 666                                                                   off);
 667                         off += sizeof(*sh);
 668                         if (sh->type == BTRFS_ROOT_BACKREF_KEY) {
 669                                 ref = (struct btrfs_root_ref *)(args.buf + off);
 670                                 name_len = btrfs_stack_root_ref_name_len(ref);
 671                                 name = (char *)(ref + 1);
 672                                 dir_id = btrfs_stack_root_ref_dirid(ref);
 673
 674                                 add_root(root_lookup, sh->objectid, sh->offset,
 675                                          dir_id, name, name_len);
 676                         }
 677
 678                         off += sh->len;
 679
 680                         /*
 681                          * record the mins in sk so we can make sure the
 682                          * next search doesn't repeat this root
 683                          */
 684                         sk->min_objectid = sh->objectid;
 685                         sk->min_type = sh->type;
 686                         sk->min_offset = sh->offset;
 687                 }
 688                 sk->nr_items = 4096;
 689                 /* this iteration is done, step forward one root for the next
 690                  * ioctl
 691                  */
 692                 if (sk->min_type < BTRFS_ROOT_BACKREF_KEY) {
 693                         sk->min_type = BTRFS_ROOT_BACKREF_KEY;
 694                         sk->min_offset = 0;
 695                 } else  if (sk->min_objectid < BTRFS_LAST_FREE_OBJECTID) {
 696                         sk->min_objectid++;
 697                         sk->min_type = BTRFS_ROOT_BACKREF_KEY;
 698                         sk->min_offset = 0;
 699                 } else
 700                         break;
 701         }
 702
 703         return 0;
 704 }
 705
 706 static int __list_subvol_fill_paths(int fd, struct root_lookup *root_lookup)
 707 {
 708         struct rb_node *n;
 709
 710         n = rb_first(&root_lookup->root);
 711         while (n) {
 712                 struct root_info *entry;
 713                 int ret;
 714                 entry = rb_entry(n, struct root_info, rb_node);
 715                 ret = lookup_ino_path(fd, entry);
 716                 if(ret < 0)
 717                         return ret;
 718                 n = rb_next(n);
 719         }
 720
 721         return 0;
 722 }
 723
 724 int list_subvols(int fd, int print_parent, int get_default)
 725 {
 726         struct root_lookup root_lookup;
 727         struct rb_node *n;
 728         u64 default_id;
 729         int ret;
 730
 731         if (get_default) {
 732                 ret = get_default_subvolid(fd, &default_id);
 733                 if (ret) {
 734                         fprintf(stderr, "ERROR: can't perform the search - %s\n",
 735                                 strerror(errno));
 736                         return ret;
 737                 }
 738                 if (default_id == 0) {
 739                         fprintf(stderr, "ERROR: 'default' dir item not found\n");
 740                         return ret;
 741                 }
 742
 743                 /* no need to resolve roots if FS_TREE is default */
 744                 if (default_id == BTRFS_FS_TREE_OBJECTID) {
 745                         printf("ID 5 (FS_TREE)\n");
 746                         return ret;
 747                 }
 748         }
 749
 750         ret = __list_subvol_search(fd, &root_lookup);
 751         if (ret) {
 752                 fprintf(stderr, "ERROR: can't perform the search - %s\n",
 753                                 strerror(errno));
 754                 return ret;
 755         }
 756
 757         /*
 758          * now we have an rbtree full of root_info objects, but we need to fill
 759          * in their path names within the subvol that is referencing each one.
 760          */
 761         ret = __list_subvol_fill_paths(fd, &root_lookup);
 762         if (ret < 0)
 763                 return ret;
 764
 765         /* now that we have all the subvol-relative paths filled in,
 766          * we have to string the subvols together so that we can get
 767          * a path all the way back to the FS root
 768          */
 769         n = rb_last(&root_lookup.root);
 770         while (n) {
 771                 struct root_info *entry;
 772                 u64 level;
 773                 u64 parent_id;
 774                 char *path;
 775
 776                 entry = rb_entry(n, struct root_info, rb_node);
 777                 if (get_default && entry->root_id != default_id) {
 778                         n = rb_prev(n);
 779                         continue;
 780                 }
 781
 782                 resolve_root(&root_lookup, entry, &parent_id, &level, &path);
 783                 if (print_parent) {
 784                         printf("ID %llu parent %llu top level %llu path %s\n",
 785                                 (unsigned long long)entry->root_id,
 786                                 (unsigned long long)parent_id,
 787                                 (unsigned long long)level, path);
 788                 } else {
 789                         printf("ID %llu top level %llu path %s\n",
 790                                 (unsigned long long)entry->root_id,
 791                                 (unsigned long long)level, path);
 792                 }
 793
 794                 free(path);
 795                 n = rb_prev(n);
 796         }
 797
 798         return ret;
 799 }
 800
 801 static int print_one_extent(int fd, struct btrfs_ioctl_search_header *sh,
 802                             struct btrfs_file_extent_item *item,
 803                             u64 found_gen, u64 *cache_dirid,
 804                             char **cache_dir_name, u64 *cache_ino,
 805                             char **cache_full_name)
 806 {
 807         u64 len = 0;
 808         u64 disk_start = 0;
 809         u64 disk_offset = 0;
 810         u8 type;
 811         int compressed = 0;
 812         int flags = 0;
 813         char *name = NULL;
 814
 815         if (sh->objectid == *cache_ino) {
 816                 name = *cache_full_name;
 817         } else if (*cache_full_name) {
 818                 free(*cache_full_name);
 819                 *cache_full_name = NULL;
 820         }
 821         if (!name) {
 822                 name = ino_resolve(fd, sh->objectid, cache_dirid,
 823                                    cache_dir_name);
 824                 *cache_full_name = name;
 825                 *cache_ino = sh->objectid;
 826         }
 827         if (!name)
 828                 return -EIO;
 829
 830         type = btrfs_stack_file_extent_type(item);
 831         compressed = btrfs_stack_file_extent_compression(item);
 832
 833         if (type == BTRFS_FILE_EXTENT_REG ||
 834             type == BTRFS_FILE_EXTENT_PREALLOC) {
 835                 disk_start = btrfs_stack_file_extent_disk_bytenr(item);
 836                 disk_offset = btrfs_stack_file_extent_offset(item);
 837                 len = btrfs_stack_file_extent_num_bytes(item);
 838         } else if (type == BTRFS_FILE_EXTENT_INLINE) {
 839                 disk_start = 0;
 840                 disk_offset = 0;
 841                 len = btrfs_stack_file_extent_ram_bytes(item);
 842         } else {
 843                 printf("unhandled extent type %d for inode %llu "
 844                        "file offset %llu gen %llu\n",
 845                         type,
 846                         (unsigned long long)sh->objectid,
 847                         (unsigned long long)sh->offset,
 848                         (unsigned long long)found_gen);
 849
 850                 return -EIO;
 851         }
 852         printf("inode %llu file offset %llu len %llu disk start %llu "
 853                "offset %llu gen %llu flags ",
 854                (unsigned long long)sh->objectid,
 855                (unsigned long long)sh->offset,
 856                (unsigned long long)len,
 857                (unsigned long long)disk_start,
 858                (unsigned long long)disk_offset,
 859                (unsigned long long)found_gen);
 860
 861         if (compressed) {
 862                 printf("COMPRESS");
 863                 flags++;
 864         }
 865         if (type == BTRFS_FILE_EXTENT_PREALLOC) {
 866                 printf("%sPREALLOC", flags ? "|" : "");
 867                 flags++;
 868         }
 869         if (type == BTRFS_FILE_EXTENT_INLINE) {
 870                 printf("%sINLINE", flags ? "|" : "");
 871                 flags++;
 872         }
 873         if (!flags)
 874                 printf("NONE");
 875
 876         printf(" %s\n", name);
 877         return 0;
 878 }
 879
 880 int find_updated_files(int fd, u64 root_id, u64 oldest_gen)
 881 {
 882         int ret;
 883         struct btrfs_ioctl_search_args args;
 884         struct btrfs_ioctl_search_key *sk = &args.key;
 885         struct btrfs_ioctl_search_header *sh;
 886         struct btrfs_file_extent_item *item;
 887         unsigned long off = 0;
 888         u64 found_gen;
 889         u64 max_found = 0;
 890         int i;
 891         int e;
 892         u64 cache_dirid = 0;
 893         u64 cache_ino = 0;
 894         char *cache_dir_name = NULL;
 895         char *cache_full_name = NULL;
 896         struct btrfs_file_extent_item backup;
 897
 898         memset(&backup, 0, sizeof(backup));
 899         memset(&args, 0, sizeof(args));
 900
 901         sk->tree_id = root_id;
 902
 903         /*
 904          * set all the other params to the max, we'll take any objectid
 905          * and any trans
 906          */
 907         sk->max_objectid = (u64)-1;
 908         sk->max_offset = (u64)-1;
 909         sk->max_transid = (u64)-1;
 910         sk->max_type = BTRFS_EXTENT_DATA_KEY;
 911         sk->min_transid = oldest_gen;
 912         /* just a big number, doesn't matter much */
 913         sk->nr_items = 4096;
 914
 915         max_found = find_root_gen(fd);
 916         while(1) {
 917                 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 918                 e = errno;
 919                 if (ret < 0) {
 920                         fprintf(stderr, "ERROR: can't perform the search- %s\n",
 921                                 strerror(e));
 922                         return ret;
 923                 }
 924                 /* the ioctl returns the number of item it found in nr_items */
 925                 if (sk->nr_items == 0)
 926                         break;
 927
 928                 off = 0;
 929
 930                 /*
 931                  * for each item, pull the key out of the header and then
 932                  * read the root_ref item it contains
 933                  */
 934                 for (i = 0; i < sk->nr_items; i++) {
 935                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 936                                                                   off);
 937                         off += sizeof(*sh);
 938
 939                         /*
 940                          * just in case the item was too big, pass something other
 941                          * than garbage
 942                          */
 943                         if (sh->len == 0)
 944                                 item = &backup;
 945                         else
 946                                 item = (struct btrfs_file_extent_item *)(args.buf +
 947                                                                  off);
 948                         found_gen = btrfs_stack_file_extent_generation(item);
 949                         if (sh->type == BTRFS_EXTENT_DATA_KEY &&
 950                             found_gen >= oldest_gen) {
 951                                 print_one_extent(fd, sh, item, found_gen,
 952                                                  &cache_dirid, &cache_dir_name,
 953                                                  &cache_ino, &cache_full_name);
 954                         }
 955                         off += sh->len;
 956
 957                         /*
 958                          * record the mins in sk so we can make sure the
 959                          * next search doesn't repeat this root
 960                          */
 961                         sk->min_objectid = sh->objectid;
 962                         sk->min_offset = sh->offset;
 963                         sk->min_type = sh->type;
 964                 }
 965                 sk->nr_items = 4096;
 966                 if (sk->min_offset < (u64)-1)
 967                         sk->min_offset++;
 968                 else if (sk->min_objectid < (u64)-1) {
 969                         sk->min_objectid++;
 970                         sk->min_offset = 0;
 971                         sk->min_type = 0;
 972                 } else
 973                         break;
 974         }
 975         free(cache_dir_name);
 976         free(cache_full_name);
 977         printf("transid marker was %llu\n", (unsigned long long)max_found);
 978         return ret;
 979 }
 980
 981 char *path_for_root(int fd, u64 root)
 982 {
 983         struct root_lookup root_lookup;
 984         struct rb_node *n;
 985         char *ret_path = NULL;
 986         int ret;
 987
 988         ret = __list_subvol_search(fd, &root_lookup);
 989         if (ret < 0)
 990                 return ERR_PTR(ret);
 991
 992         ret = __list_subvol_fill_paths(fd, &root_lookup);
 993         if (ret < 0)
 994                 return ERR_PTR(ret);
 995
 996         n = rb_last(&root_lookup.root);
 997         while (n) {
 998                 struct root_info *entry;
 999                 u64 parent_id;
1000                 u64 level;
1001                 char *path;
1002
1003                 entry = rb_entry(n, struct root_info, rb_node);
1004                 resolve_root(&root_lookup, entry, &parent_id, &level, &path);
1005                 if (entry->root_id == root)
1006                         ret_path = path;
1007                 else
1008                         free(path);
1009
1010                 n = rb_prev(n);
1011         }
1012
1013         return ret_path;
1014 }