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