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