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