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