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