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
 187         ret = tree_insert(&root_lookup->root, root_id, ref_tree, &ri->rb_node);
 188         if (ret) {
 189                 printf("failed to insert tree %llu\n", (unsigned long long)root_id);
 190                 exit(1);
 191         }
 192         return 0;
 193 }
 194
 195 /*
 196  * for a given root_info, search through the root_lookup tree to construct
 197  * the full path name to it.
 198  *
 199  * This can't be called until all the root_info->path fields are filled
 200  * in by lookup_ino_path
 201  */
 202 static int resolve_root(struct root_lookup *rl, struct root_info *ri, int print_parent)
 203 {
 204         u64 top_id;
 205         u64 parent_id = 0;
 206         char *full_path = NULL;
 207         int len = 0;
 208         struct root_info *found;
 209
 210         /*
 211          * we go backwards from the root_info object and add pathnames
 212          * from parent directories as we go.
 213          */
 214         found = ri;
 215         while (1) {
 216                 char *tmp;
 217                 u64 next;
 218                 int add_len = strlen(found->path);
 219
 220                 /* room for / and for null */
 221                 tmp = malloc(add_len + 2 + len);
 222                 if (full_path) {
 223                         memcpy(tmp + add_len + 1, full_path, len);
 224                         tmp[add_len] = '/';
 225                         memcpy(tmp, found->path, add_len);
 226                         tmp [add_len + len + 1] = '\0';
 227                         free(full_path);
 228                         full_path = tmp;
 229                         len += add_len + 1;
 230                 } else {
 231                         full_path = strdup(found->path);
 232                         len = add_len;
 233                 }
 234
 235                 next = found->ref_tree;
 236                 /* record the first parent */
 237                 if ( parent_id == 0 ) {
 238                         parent_id = next;
 239                 }
 240
 241                 /* if the ref_tree refers to ourselves, we're at the top */
 242                 if (next == found->root_id) {
 243                         top_id = next;
 244                         break;
 245                 }
 246
 247                 /*
 248                  * if the ref_tree wasn't in our tree of roots, we're
 249                  * at the top
 250                  */
 251                 found = tree_search(&rl->root, next);
 252                 if (!found) {
 253                         top_id = next;
 254                         break;
 255                 }
 256         }
 257         if (print_parent) {
 258                 printf("ID %llu parent %llu top level %llu path %s\n",
 259                        (unsigned long long)ri->root_id, (unsigned long long)parent_id, (unsigned long long)top_id,
 260                         full_path);
 261         } else {
 262                 printf("ID %llu top level %llu path %s\n",
 263                        (unsigned long long)ri->root_id, (unsigned long long)top_id,
 264                         full_path);
 265         }
 266         free(full_path);
 267         return 0;
 268 }
 269
 270 /*
 271  * for a single root_info, ask the kernel to give us a path name
 272  * inside it's ref_root for the dir_id where it lives.
 273  *
 274  * This fills in root_info->path with the path to the directory and and
 275  * appends this root's name.
 276  */
 277 static int lookup_ino_path(int fd, struct root_info *ri)
 278 {
 279         struct btrfs_ioctl_ino_lookup_args args;
 280         int ret, e;
 281
 282         if (ri->path)
 283                 return 0;
 284
 285         memset(&args, 0, sizeof(args));
 286         args.treeid = ri->ref_tree;
 287         args.objectid = ri->dir_id;
 288
 289         ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &args);
 290         e = errno;
 291         if (ret) {
 292                 fprintf(stderr, "ERROR: Failed to lookup path for root %llu - %s\n",
 293                         (unsigned long long)ri->ref_tree,
 294                         strerror(e));
 295                 return ret;
 296         }
 297
 298         if (args.name[0]) {
 299                 /*
 300                  * we're in a subdirectory of ref_tree, the kernel ioctl
 301                  * puts a / in there for us
 302                  */
 303                 ri->path = malloc(strlen(ri->name) + strlen(args.name) + 1);
 304                 if (!ri->path) {
 305                         perror("malloc failed");
 306                         exit(1);
 307                 }
 308                 strcpy(ri->path, args.name);
 309                 strcat(ri->path, ri->name);
 310         } else {
 311                 /* we're at the root of ref_tree */
 312                 ri->path = strdup(ri->name);
 313                 if (!ri->path) {
 314                         perror("strdup failed");
 315                         exit(1);
 316                 }
 317         }
 318         return 0;
 319 }
 320
 321 /* finding the generation for a given path is a two step process.
 322  * First we use the inode loookup routine to find out the root id
 323  *
 324  * Then we use the tree search ioctl to scan all the root items for a
 325  * given root id and spit out the latest generation we can find
 326  */
 327 static u64 find_root_gen(int fd)
 328 {
 329         struct btrfs_ioctl_ino_lookup_args ino_args;
 330         int ret;
 331         struct btrfs_ioctl_search_args args;
 332         struct btrfs_ioctl_search_key *sk = &args.key;
 333         struct btrfs_ioctl_search_header *sh;
 334         unsigned long off = 0;
 335         u64 max_found = 0;
 336         int i;
 337         int e;
 338
 339         memset(&ino_args, 0, sizeof(ino_args));
 340         ino_args.objectid = BTRFS_FIRST_FREE_OBJECTID;
 341
 342         /* this ioctl fills in ino_args->treeid */
 343         ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &ino_args);
 344         e = errno;
 345         if (ret) {
 346                 fprintf(stderr, "ERROR: Failed to lookup path for dirid %llu - %s\n",
 347                         (unsigned long long)BTRFS_FIRST_FREE_OBJECTID,
 348                         strerror(e));
 349                 return 0;
 350         }
 351
 352         memset(&args, 0, sizeof(args));
 353
 354         sk->tree_id = 1;
 355
 356         /*
 357          * there may be more than one ROOT_ITEM key if there are
 358          * snapshots pending deletion, we have to loop through
 359          * them.
 360          */
 361         sk->min_objectid = ino_args.treeid;
 362         sk->max_objectid = ino_args.treeid;
 363         sk->max_type = BTRFS_ROOT_ITEM_KEY;
 364         sk->min_type = BTRFS_ROOT_ITEM_KEY;
 365         sk->max_offset = (u64)-1;
 366         sk->max_transid = (u64)-1;
 367         sk->nr_items = 4096;
 368
 369         while (1) {
 370                 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 371                 e = errno;
 372                 if (ret < 0) {
 373                         fprintf(stderr, "ERROR: can't perform the search - %s\n",
 374                                 strerror(e));
 375                         return 0;
 376                 }
 377                 /* the ioctl returns the number of item it found in nr_items */
 378                 if (sk->nr_items == 0)
 379                         break;
 380
 381                 off = 0;
 382                 for (i = 0; i < sk->nr_items; i++) {
 383                         struct btrfs_root_item *item;
 384                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 385                                                                   off);
 386
 387                         off += sizeof(*sh);
 388                         item = (struct btrfs_root_item *)(args.buf + off);
 389                         off += sh->len;
 390
 391                         sk->min_objectid = sh->objectid;
 392                         sk->min_type = sh->type;
 393                         sk->min_offset = sh->offset;
 394
 395                         if (sh->objectid > ino_args.treeid)
 396                                 break;
 397
 398                         if (sh->objectid == ino_args.treeid &&
 399                             sh->type == BTRFS_ROOT_ITEM_KEY) {
 400                                 max_found = max(max_found,
 401                                                 btrfs_root_generation(item));
 402                         }
 403                 }
 404                 if (sk->min_offset < (u64)-1)
 405                         sk->min_offset++;
 406                 else
 407                         break;
 408
 409                 if (sk->min_type != BTRFS_ROOT_ITEM_KEY)
 410                         break;
 411                 if (sk->min_objectid != BTRFS_ROOT_ITEM_KEY)
 412                         break;
 413         }
 414         return max_found;
 415 }
 416
 417 /* pass in a directory id and this will return
 418  * the full path of the parent directory inside its
 419  * subvolume root.
 420  *
 421  * It may return NULL if it is in the root, or an ERR_PTR if things
 422  * go badly.
 423  */
 424 static char *__ino_resolve(int fd, u64 dirid)
 425 {
 426         struct btrfs_ioctl_ino_lookup_args args;
 427         int ret;
 428         char *full;
 429         int e;
 430
 431         memset(&args, 0, sizeof(args));
 432         args.objectid = dirid;
 433
 434         ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &args);
 435         e = errno;
 436         if (ret) {
 437                 fprintf(stderr, "ERROR: Failed to lookup path for dirid %llu - %s\n",
 438                         (unsigned long long)dirid, strerror(e) );
 439                 return ERR_PTR(ret);
 440         }
 441
 442         if (args.name[0]) {
 443                 /*
 444                  * we're in a subdirectory of ref_tree, the kernel ioctl
 445                  * puts a / in there for us
 446                  */
 447                 full = strdup(args.name);
 448                 if (!full) {
 449                         perror("malloc failed");
 450                         return ERR_PTR(-ENOMEM);
 451                 }
 452         } else {
 453                 /* we're at the root of ref_tree */
 454                 full = NULL;
 455         }
 456         return full;
 457 }
 458
 459 /*
 460  * simple string builder, returning a new string with both
 461  * dirid and name
 462  */
 463 char *build_name(char *dirid, char *name)
 464 {
 465         char *full;
 466         if (!dirid)
 467                 return strdup(name);
 468
 469         full = malloc(strlen(dirid) + strlen(name) + 1);
 470         if (!full)
 471                 return NULL;
 472         strcpy(full, dirid);
 473         strcat(full, name);
 474         return full;
 475 }
 476
 477 /*
 478  * given an inode number, this returns the full path name inside the subvolume
 479  * to that file/directory.  cache_dirid and cache_name are used to
 480  * cache the results so we can avoid tree searches if a later call goes
 481  * to the same directory or file name
 482  */
 483 static char *ino_resolve(int fd, u64 ino, u64 *cache_dirid, char **cache_name)
 484
 485 {
 486         u64 dirid;
 487         char *dirname;
 488         char *name;
 489         char *full;
 490         int ret;
 491         struct btrfs_ioctl_search_args args;
 492         struct btrfs_ioctl_search_key *sk = &args.key;
 493         struct btrfs_ioctl_search_header *sh;
 494         unsigned long off = 0;
 495         int namelen;
 496         int e;
 497
 498         memset(&args, 0, sizeof(args));
 499
 500         sk->tree_id = 0;
 501
 502         /*
 503          * step one, we search for the inode back ref.  We just use the first
 504          * one
 505          */
 506         sk->min_objectid = ino;
 507         sk->max_objectid = ino;
 508         sk->max_type = BTRFS_INODE_REF_KEY;
 509         sk->max_offset = (u64)-1;
 510         sk->min_type = BTRFS_INODE_REF_KEY;
 511         sk->max_transid = (u64)-1;
 512         sk->nr_items = 1;
 513
 514         ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 515         e = errno;
 516         if (ret < 0) {
 517                 fprintf(stderr, "ERROR: can't perform the search - %s\n",
 518                         strerror(e));
 519                 return NULL;
 520         }
 521         /* the ioctl returns the number of item it found in nr_items */
 522         if (sk->nr_items == 0)
 523                 return NULL;
 524
 525         off = 0;
 526         sh = (struct btrfs_ioctl_search_header *)(args.buf + off);
 527
 528         if (sh->type == BTRFS_INODE_REF_KEY) {
 529                 struct btrfs_inode_ref *ref;
 530                 dirid = sh->offset;
 531
 532                 ref = (struct btrfs_inode_ref *)(sh + 1);
 533                 namelen = btrfs_stack_inode_ref_name_len(ref);
 534
 535                 name = (char *)(ref + 1);
 536                 name = strndup(name, namelen);
 537
 538                 /* use our cached value */
 539                 if (dirid == *cache_dirid && *cache_name) {
 540                         dirname = *cache_name;
 541                         goto build;
 542                 }
 543         } else {
 544                 return NULL;
 545         }
 546         /*
 547          * the inode backref gives us the file name and the parent directory id.
 548          * From here we use __ino_resolve to get the path to the parent
 549          */
 550         dirname = __ino_resolve(fd, dirid);
 551 build:
 552         full = build_name(dirname, name);
 553         if (*cache_name && dirname != *cache_name)
 554                 free(*cache_name);
 555
 556         *cache_name = dirname;
 557         *cache_dirid = dirid;
 558         free(name);
 559
 560         return full;
 561 }
 562
 563 int list_subvols(int fd, int print_parent, int get_default)
 564 {
 565         struct root_lookup root_lookup;
 566         struct rb_node *n;
 567         int ret;
 568         struct btrfs_ioctl_search_args args;
 569         struct btrfs_ioctl_search_key *sk = &args.key;
 570         struct btrfs_ioctl_search_header *sh;
 571         struct btrfs_root_ref *ref;
 572         struct btrfs_dir_item *di;
 573         unsigned long off = 0;
 574         int name_len;
 575         char *name;
 576         u64 dir_id;
 577         u64 subvol_id = 0;
 578         int i;
 579         int e;
 580
 581         root_lookup_init(&root_lookup);
 582
 583         memset(&args, 0, sizeof(args));
 584
 585         /* search in the tree of tree roots */
 586         sk->tree_id = 1;
 587
 588         /*
 589          * set the min and max to backref keys.  The search will
 590          * only send back this type of key now.
 591          */
 592         sk->max_type = BTRFS_ROOT_BACKREF_KEY;
 593         sk->min_type = BTRFS_ROOT_BACKREF_KEY;
 594
 595         /*
 596          * set all the other params to the max, we'll take any objectid
 597          * and any trans
 598          */
 599         sk->max_objectid = (u64)-1;
 600         sk->max_offset = (u64)-1;
 601         sk->max_transid = (u64)-1;
 602
 603         /* just a big number, doesn't matter much */
 604         sk->nr_items = 4096;
 605
 606         while(1) {
 607                 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 608                 e = errno;
 609                 if (ret < 0) {
 610                         fprintf(stderr, "ERROR: can't perform the search - %s\n",
 611                                 strerror(e));
 612                         return ret;
 613                 }
 614                 /* the ioctl returns the number of item it found in nr_items */
 615                 if (sk->nr_items == 0)
 616                         break;
 617
 618                 off = 0;
 619
 620                 /*
 621                  * for each item, pull the key out of the header and then
 622                  * read the root_ref item it contains
 623                  */
 624                 for (i = 0; i < sk->nr_items; i++) {
 625                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 626                                                                   off);
 627                         off += sizeof(*sh);
 628                         if (sh->type == BTRFS_ROOT_BACKREF_KEY) {
 629                                 ref = (struct btrfs_root_ref *)(args.buf + off);
 630                                 name_len = btrfs_stack_root_ref_name_len(ref);
 631                                 name = (char *)(ref + 1);
 632                                 dir_id = btrfs_stack_root_ref_dirid(ref);
 633
 634                                 add_root(&root_lookup, sh->objectid, sh->offset,
 635                                          dir_id, name, name_len);
 636                         }
 637
 638                         off += sh->len;
 639
 640                         /*
 641                          * record the mins in sk so we can make sure the
 642                          * next search doesn't repeat this root
 643                          */
 644                         sk->min_objectid = sh->objectid;
 645                         sk->min_type = sh->type;
 646                         sk->min_offset = sh->offset;
 647                 }
 648                 sk->nr_items = 4096;
 649                 /* this iteration is done, step forward one root for the next
 650                  * ioctl
 651                  */
 652                 if (sk->min_objectid < (u64)-1) {
 653                         sk->min_objectid++;
 654                         sk->min_type = BTRFS_ROOT_BACKREF_KEY;
 655                         sk->min_offset = 0;
 656                 } else
 657                         break;
 658         }
 659         /*
 660          * now we have an rbtree full of root_info objects, but we need to fill
 661          * in their path names within the subvol that is referencing each one.
 662          */
 663         n = rb_first(&root_lookup.root);
 664         while (n) {
 665                 struct root_info *entry;
 666                 int ret;
 667                 entry = rb_entry(n, struct root_info, rb_node);
 668                 ret = lookup_ino_path(fd, entry);
 669                 if(ret < 0)
 670                         return ret;
 671                 n = rb_next(n);
 672         }
 673
 674         memset(&args, 0, sizeof(args));
 675
 676         /* search in the tree of tree roots */
 677         sk->tree_id = BTRFS_ROOT_TREE_OBJECTID;
 678
 679         /* search dir item */
 680         sk->max_type = BTRFS_DIR_ITEM_KEY;
 681         sk->min_type = BTRFS_DIR_ITEM_KEY;
 682
 683         sk->max_objectid = BTRFS_ROOT_TREE_DIR_OBJECTID;
 684         sk->min_objectid = BTRFS_ROOT_TREE_DIR_OBJECTID;
 685         sk->max_offset = (u64)-1;
 686         sk->max_transid = (u64)-1;
 687
 688         /* just a big number, doesn't matter much */
 689         sk->nr_items = 4096;
 690
 691         /* try to get the objectid of default subvolume */
 692         if (get_default) {
 693                 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 694                 if (ret < 0) {
 695                         fprintf(stderr, "ERROR: can't perform the search\n");
 696                         return ret;
 697                 }
 698
 699                 off = 0;
 700                 /* go through each item to find dir item named "default" */
 701                 for (i = 0; i < sk->nr_items; i++) {
 702                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 703                                                                   off);
 704                         off += sizeof(*sh);
 705                         if (sh->type == BTRFS_DIR_ITEM_KEY) {
 706                                 di = (struct btrfs_dir_item *)(args.buf + off);
 707                                 name_len = le16_to_cpu(di->name_len);
 708                                 name = (char *)di + sizeof(struct btrfs_dir_item);
 709                                 if (!strncmp("default", name, name_len)) {
 710                                         subvol_id = btrfs_disk_key_objectid(
 711                                                 &di->location);
 712                                         break;
 713                                 }
 714                         }
 715
 716                         off += sh->len;
 717                 }
 718         }
 719
 720         /* now that we have all the subvol-relative paths filled in,
 721          * we have to string the subvols together so that we can get
 722          * a path all the way back to the FS root
 723          */
 724         n = rb_last(&root_lookup.root);
 725         while (n) {
 726                 struct root_info *entry;
 727                 entry = rb_entry(n, struct root_info, rb_node);
 728                 if (!get_default)
 729                         resolve_root(&root_lookup, entry, print_parent);
 730                 /* we only want the default subvolume */
 731                 else if (subvol_id == entry->root_id)
 732                         resolve_root(&root_lookup, entry, print_parent);
 733                 else if (subvol_id == 0)
 734                         break;
 735                 n = rb_prev(n);
 736         }
 737
 738         return ret;
 739 }
 740
 741 static int print_one_extent(int fd, struct btrfs_ioctl_search_header *sh,
 742                             struct btrfs_file_extent_item *item,
 743                             u64 found_gen, u64 *cache_dirid,
 744                             char **cache_dir_name, u64 *cache_ino,
 745                             char **cache_full_name)
 746 {
 747         u64 len = 0;
 748         u64 disk_start = 0;
 749         u64 disk_offset = 0;
 750         u8 type;
 751         int compressed = 0;
 752         int flags = 0;
 753         char *name = NULL;
 754
 755         if (sh->objectid == *cache_ino) {
 756                 name = *cache_full_name;
 757         } else if (*cache_full_name) {
 758                 free(*cache_full_name);
 759                 *cache_full_name = NULL;
 760         }
 761         if (!name) {
 762                 name = ino_resolve(fd, sh->objectid, cache_dirid,
 763                                    cache_dir_name);
 764                 *cache_full_name = name;
 765                 *cache_ino = sh->objectid;
 766         }
 767         if (!name)
 768                 return -EIO;
 769
 770         type = btrfs_stack_file_extent_type(item);
 771         compressed = btrfs_stack_file_extent_compression(item);
 772
 773         if (type == BTRFS_FILE_EXTENT_REG ||
 774             type == BTRFS_FILE_EXTENT_PREALLOC) {
 775                 disk_start = btrfs_stack_file_extent_disk_bytenr(item);
 776                 disk_offset = btrfs_stack_file_extent_offset(item);
 777                 len = btrfs_stack_file_extent_num_bytes(item);
 778         } else if (type == BTRFS_FILE_EXTENT_INLINE) {
 779                 disk_start = 0;
 780                 disk_offset = 0;
 781                 len = btrfs_stack_file_extent_ram_bytes(item);
 782         } else {
 783                 printf("unhandled extent type %d for inode %llu "
 784                        "file offset %llu gen %llu\n",
 785                         type,
 786                         (unsigned long long)sh->objectid,
 787                         (unsigned long long)sh->offset,
 788                         (unsigned long long)found_gen);
 789
 790                 return -EIO;
 791         }
 792         printf("inode %llu file offset %llu len %llu disk start %llu "
 793                "offset %llu gen %llu flags ",
 794                (unsigned long long)sh->objectid,
 795                (unsigned long long)sh->offset,
 796                (unsigned long long)len,
 797                (unsigned long long)disk_start,
 798                (unsigned long long)disk_offset,
 799                (unsigned long long)found_gen);
 800
 801         if (compressed) {
 802                 printf("COMPRESS");
 803                 flags++;
 804         }
 805         if (type == BTRFS_FILE_EXTENT_PREALLOC) {
 806                 printf("%sPREALLOC", flags ? "|" : "");
 807                 flags++;
 808         }
 809         if (type == BTRFS_FILE_EXTENT_INLINE) {
 810                 printf("%sINLINE", flags ? "|" : "");
 811                 flags++;
 812         }
 813         if (!flags)
 814                 printf("NONE");
 815
 816         printf(" %s\n", name);
 817         return 0;
 818 }
 819
 820 int find_updated_files(int fd, u64 root_id, u64 oldest_gen)
 821 {
 822         int ret;
 823         struct btrfs_ioctl_search_args args;
 824         struct btrfs_ioctl_search_key *sk = &args.key;
 825         struct btrfs_ioctl_search_header *sh;
 826         struct btrfs_file_extent_item *item;
 827         unsigned long off = 0;
 828         u64 found_gen;
 829         u64 max_found = 0;
 830         int i;
 831         int e;
 832         u64 cache_dirid = 0;
 833         u64 cache_ino = 0;
 834         char *cache_dir_name = NULL;
 835         char *cache_full_name = NULL;
 836         struct btrfs_file_extent_item backup;
 837
 838         memset(&backup, 0, sizeof(backup));
 839         memset(&args, 0, sizeof(args));
 840
 841         sk->tree_id = root_id;
 842
 843         /*
 844          * set all the other params to the max, we'll take any objectid
 845          * and any trans
 846          */
 847         sk->max_objectid = (u64)-1;
 848         sk->max_offset = (u64)-1;
 849         sk->max_transid = (u64)-1;
 850         sk->max_type = BTRFS_EXTENT_DATA_KEY;
 851         sk->min_transid = oldest_gen;
 852         /* just a big number, doesn't matter much */
 853         sk->nr_items = 4096;
 854
 855         max_found = find_root_gen(fd);
 856         while(1) {
 857                 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 858                 e = errno;
 859                 if (ret < 0) {
 860                         fprintf(stderr, "ERROR: can't perform the search- %s\n",
 861                                 strerror(e));
 862                         return ret;
 863                 }
 864                 /* the ioctl returns the number of item it found in nr_items */
 865                 if (sk->nr_items == 0)
 866                         break;
 867
 868                 off = 0;
 869
 870                 /*
 871                  * for each item, pull the key out of the header and then
 872                  * read the root_ref item it contains
 873                  */
 874                 for (i = 0; i < sk->nr_items; i++) {
 875                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 876                                                                   off);
 877                         off += sizeof(*sh);
 878
 879                         /*
 880                          * just in case the item was too big, pass something other
 881                          * than garbage
 882                          */
 883                         if (sh->len == 0)
 884                                 item = &backup;
 885                         else
 886                                 item = (struct btrfs_file_extent_item *)(args.buf +
 887                                                                  off);
 888                         found_gen = btrfs_stack_file_extent_generation(item);
 889                         if (sh->type == BTRFS_EXTENT_DATA_KEY &&
 890                             found_gen >= oldest_gen) {
 891                                 print_one_extent(fd, sh, item, found_gen,
 892                                                  &cache_dirid, &cache_dir_name,
 893                                                  &cache_ino, &cache_full_name);
 894                         }
 895                         off += sh->len;
 896
 897                         /*
 898                          * record the mins in sk so we can make sure the
 899                          * next search doesn't repeat this root
 900                          */
 901                         sk->min_objectid = sh->objectid;
 902                         sk->min_offset = sh->offset;
 903                         sk->min_type = sh->type;
 904                 }
 905                 sk->nr_items = 4096;
 906                 if (sk->min_offset < (u64)-1)
 907                         sk->min_offset++;
 908                 else if (sk->min_objectid < (u64)-1) {
 909                         sk->min_objectid++;
 910                         sk->min_offset = 0;
 911                         sk->min_type = 0;
 912                 } else
 913                         break;
 914         }
 915         free(cache_dir_name);
 916         free(cache_full_name);
 917         printf("transid marker was %llu\n", (unsigned long long)max_found);
 918         return ret;
 919 }