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(ri->generation == ri->generation_v2) {
 741                                         t = ri->otime.sec;
 742                                         memcpy(uuid, ri->uuid, BTRFS_UUID_SIZE);
 743                                 } else {
 744                                         t = 0;
 745                                         memset(uuid, 0, BTRFS_UUID_SIZE);
 746                                 }
 747
 748                                 update_root(root_lookup, sh->objectid, gen, t,
 749                                         uuid);
 750                         }
 751
 752                         off += sh->len;
 753
 754                         /*
 755                          * record the mins in sk so we can make sure the
 756                          * next search doesn't repeat this root
 757                          */
 758                         sk->min_objectid = sh->objectid;
 759                         sk->min_type = sh->type;
 760                         sk->min_offset = sh->offset;
 761                 }
 762                 sk->nr_items = 4096;
 763                 /* this iteration is done, step forward one root for the next
 764                  * ioctl
 765                  */
 766                 if (get_gen)
 767                         type = BTRFS_ROOT_ITEM_KEY;
 768                 else
 769                         type = BTRFS_ROOT_BACKREF_KEY;
 770
 771                 if (sk->min_type < type) {
 772                         sk->min_type = type;
 773                         sk->min_offset = 0;
 774                 } else  if (sk->min_objectid < BTRFS_LAST_FREE_OBJECTID) {
 775                         sk->min_objectid++;
 776                         sk->min_type = type;
 777                         sk->min_offset = 0;
 778                 } else
 779                         break;
 780         }
 781
 782         if (!get_gen) {
 783                 memset(&args, 0, sizeof(args));
 784
 785                 sk->tree_id = 1;
 786                 sk->max_type = BTRFS_ROOT_ITEM_KEY;
 787                 sk->min_type = BTRFS_ROOT_ITEM_KEY;
 788
 789                 sk->min_objectid = BTRFS_FIRST_FREE_OBJECTID;
 790
 791                 sk->max_objectid = BTRFS_LAST_FREE_OBJECTID;
 792                 sk->max_offset = (u64)-1;
 793                 sk->max_transid = (u64)-1;
 794
 795                 get_gen = 1;
 796                 goto again;
 797         }
 798         return 0;
 799 }
 800
 801 static int __list_snapshot_search(int fd, struct root_lookup *root_lookup)
 802 {
 803         int ret;
 804         struct btrfs_ioctl_search_args args;
 805         struct btrfs_ioctl_search_key *sk = &args.key;
 806         struct btrfs_ioctl_search_header *sh;
 807         unsigned long off = 0;
 808         u64 gen = 0;
 809         int i;
 810
 811         root_lookup_init(root_lookup);
 812         memset(&args, 0, sizeof(args));
 813
 814         sk->tree_id = 1;
 815         sk->max_type = BTRFS_ROOT_ITEM_KEY;
 816         sk->min_type = BTRFS_ROOT_ITEM_KEY;
 817         sk->min_objectid = BTRFS_FIRST_FREE_OBJECTID;
 818         sk->max_objectid = BTRFS_LAST_FREE_OBJECTID;
 819         sk->max_offset = (u64)-1;
 820         sk->max_transid = (u64)-1;
 821         sk->nr_items = 4096;
 822
 823         while (1) {
 824                 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 825                 if (ret < 0)
 826                         return ret;
 827                 /* the ioctl returns the number of item it found in nr_items */
 828                 if (sk->nr_items == 0)
 829                         break;
 830
 831                 off = 0;
 832
 833                 /*
 834                  * for each item, pull the key out of the header and then
 835                  * read the root_ref item it contains
 836                  */
 837                 for (i = 0; i < sk->nr_items; i++) {
 838                         struct btrfs_root_item *item;
 839                         time_t  t;
 840                         u8 uuid[BTRFS_UUID_SIZE];
 841
 842                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 843                                                                   off);
 844                         off += sizeof(*sh);
 845                         if (sh->type == BTRFS_ROOT_ITEM_KEY && sh->offset) {
 846                                 item = (struct btrfs_root_item *)(args.buf + off);
 847                                 if(item->generation == item->generation_v2) {
 848                                         t = item->otime.sec;
 849                                         memcpy(uuid, item->uuid, BTRFS_UUID_SIZE);
 850                                 } else {
 851                                         t = 0;
 852                                         memset(uuid, 0, BTRFS_UUID_SIZE);
 853                                 }
 854                                 gen = sh->offset;
 855
 856                                 add_root(root_lookup, sh->objectid, 0,
 857                                          0, NULL, 0, &gen, t, uuid);
 858                         }
 859                         off += sh->len;
 860
 861                         /*
 862                          * record the mins in sk so we can make sure the
 863                          * next search doesn't repeat this root
 864                          */
 865                         sk->min_objectid = sh->objectid;
 866                         sk->min_type = sh->type;
 867                         sk->min_offset = sh->offset;
 868                 }
 869                 sk->nr_items = 4096;
 870                 /* this iteration is done, step forward one root for the next
 871                  * ioctl
 872                  */
 873                 if (sk->min_type < BTRFS_ROOT_ITEM_KEY) {
 874                         sk->min_type = BTRFS_ROOT_ITEM_KEY;
 875                         sk->min_offset = 0;
 876                 } else  if (sk->min_objectid < BTRFS_LAST_FREE_OBJECTID) {
 877                         sk->min_objectid++;
 878                         sk->min_type = BTRFS_ROOT_ITEM_KEY;
 879                         sk->min_offset = 0;
 880                 } else
 881                         break;
 882         }
 883         return 0;
 884 }
 885
 886 static int __list_subvol_fill_paths(int fd, struct root_lookup *root_lookup)
 887 {
 888         struct rb_node *n;
 889
 890         n = rb_first(&root_lookup->root);
 891         while (n) {
 892                 struct root_info *entry;
 893                 int ret;
 894                 entry = rb_entry(n, struct root_info, rb_node);
 895                 ret = lookup_ino_path(fd, entry);
 896                 if(ret < 0)
 897                         return ret;
 898                 n = rb_next(n);
 899         }
 900
 901         return 0;
 902 }
 903
 904 int list_subvols(int fd, int print_parent, int get_default, int print_uuid)
 905 {
 906         struct root_lookup root_lookup;
 907         struct rb_node *n;
 908         u64 default_id;
 909         int ret;
 910         char uuidparse[37];
 911
 912         if (get_default) {
 913                 ret = get_default_subvolid(fd, &default_id);
 914                 if (ret) {
 915                         fprintf(stderr, "ERROR: can't perform the search - %s\n",
 916                                 strerror(errno));
 917                         return ret;
 918                 }
 919                 if (default_id == 0) {
 920                         fprintf(stderr, "ERROR: 'default' dir item not found\n");
 921                         return ret;
 922                 }
 923
 924                 /* no need to resolve roots if FS_TREE is default */
 925                 if (default_id == BTRFS_FS_TREE_OBJECTID) {
 926                         printf("ID 5 (FS_TREE)\n");
 927                         return ret;
 928                 }
 929         }
 930
 931         ret = __list_subvol_search(fd, &root_lookup);
 932         if (ret) {
 933                 fprintf(stderr, "ERROR: can't perform the search - %s\n",
 934                                 strerror(errno));
 935                 return ret;
 936         }
 937
 938         /*
 939          * now we have an rbtree full of root_info objects, but we need to fill
 940          * in their path names within the subvol that is referencing each one.
 941          */
 942         ret = __list_subvol_fill_paths(fd, &root_lookup);
 943         if (ret < 0)
 944                 return ret;
 945
 946         /* now that we have all the subvol-relative paths filled in,
 947          * we have to string the subvols together so that we can get
 948          * a path all the way back to the FS root
 949          */
 950         n = rb_last(&root_lookup.root);
 951         while (n) {
 952                 struct root_info *entry;
 953                 u64 level;
 954                 u64 parent_id;
 955                 char *path;
 956
 957                 entry = rb_entry(n, struct root_info, rb_node);
 958                 if (get_default && entry->root_id != default_id) {
 959                         n = rb_prev(n);
 960                         continue;
 961                 }
 962
 963                 resolve_root(&root_lookup, entry, &parent_id, &level, &path);
 964                 if (print_parent) {
 965                         if (print_uuid) {
 966                                 if (uuid_is_null(entry->uuid))
 967                                         strcpy(uuidparse, "-");
 968                                 else
 969                                         uuid_unparse(entry->uuid, uuidparse);
 970                                 printf("ID %llu gen %llu parent %llu top level %llu"
 971                                         " uuid %s path %s\n",
 972                                         (unsigned long long)entry->root_id,
 973                                         (unsigned long long)entry->gen,
 974                                         (unsigned long long)parent_id,
 975                                         (unsigned long long)level,
 976                                         uuidparse, path);
 977                         } else {
 978                                 printf("ID %llu gen %llu parent %llu top level"
 979                                         " %llu path %s\n",
 980                                         (unsigned long long)entry->root_id,
 981                                         (unsigned long long)entry->gen,
 982                                         (unsigned long long)parent_id,
 983                                         (unsigned long long)level, path);
 984                         }
 985                 } else {
 986                         if (print_uuid) {
 987                                 if (uuid_is_null(entry->uuid))
 988                                         strcpy(uuidparse, "-");
 989                                 else
 990                                         uuid_unparse(entry->uuid, uuidparse);
 991                                 printf("ID %llu gen %llu top level %llu"
 992                                         " uuid %s path %s\n",
 993                                         (unsigned long long)entry->root_id,
 994                                         (unsigned long long)entry->gen,
 995                                         (unsigned long long)level,
 996                                         uuidparse, path);
 997                         } else {
 998                                 printf("ID %llu gen %llu top level %llu path %s\n",
 999                                         (unsigned long long)entry->root_id,
1000                                         (unsigned long long)entry->gen,
1001                                         (unsigned long long)level, path);
1002                         }
1003                 }
1004
1005                 free(path);
1006                 n = rb_prev(n);
1007         }
1008
1009         return ret;
1010 }
1011
1012 int list_snapshots(int fd, int print_parent, int order, int print_uuid)
1013 {
1014         struct root_lookup root_lookup;
1015         struct root_lookup root_lookup_snap;
1016         struct rb_node *n;
1017         int ret;
1018
1019         ret = __list_snapshot_search(fd, &root_lookup_snap);
1020         if (ret) {
1021                 fprintf(stderr, "ERROR: can't perform the search - %s\n",
1022                                 strerror(errno));
1023                 return ret;
1024         }
1025
1026         ret = __list_subvol_search(fd, &root_lookup);
1027         if (ret) {
1028                 fprintf(stderr, "ERROR: can't perform the search - %s\n",
1029                                 strerror(errno));
1030                 return ret;
1031         }
1032
1033         /*
1034          * now we have an rbtree full of root_info objects, but we need to fill
1035          * in their path names within the subvol that is referencing each one.
1036          */
1037         ret = __list_subvol_fill_paths(fd, &root_lookup);
1038         if (ret < 0)
1039                 return ret;
1040
1041         /* now that we have all the subvol-relative paths filled in,
1042          * we have to string the subvols together so that we can get
1043          * a path all the way back to the FS root
1044          */
1045         if (!order)
1046                 n = rb_last(&root_lookup_snap.root);
1047         else
1048                 n = rb_first(&root_lookup_snap.root);
1049         while (n) {
1050                 struct root_info *entry_snap;
1051                 struct root_info *entry;
1052                 u64 level;
1053                 u64 parent_id;
1054                 char *path;
1055                 time_t t;
1056                 char tstr[256];
1057                 char uuidparse[37];
1058
1059                 entry_snap = rb_entry(n, struct root_info, rb_node);
1060                 entry = tree_search(&root_lookup.root, entry_snap->root_id);
1061
1062                 resolve_root(&root_lookup, entry, &parent_id, &level, &path);
1063                 t = entry->otime;
1064                 if(t)
1065                         strftime(tstr,256,"%Y-%m-%d %X",localtime(&t));
1066                 else
1067                         strcpy(tstr,"-");
1068                 if (print_parent) {
1069                         if (print_uuid) {
1070                                 if (uuid_is_null(entry->uuid))
1071                                         strcpy(uuidparse, "-");
1072                                 else
1073                                         uuid_unparse(entry->uuid, uuidparse);
1074                                 printf("ID %llu gen %llu cgen %llu parent %llu"
1075                                         " top level %llu otime %s uuid %s path %s\n",
1076                                         (unsigned long long)entry->root_id,
1077                                         (unsigned long long)entry->gen,
1078                                         (unsigned long long)entry_snap->gen,
1079                                         (unsigned long long)parent_id,
1080                                         (unsigned long long)level,
1081                                         tstr, uuidparse, path);
1082                         } else {
1083                                 printf("ID %llu gen %llu cgen %llu parent %llu"
1084                                         " top level %llu otime %s path %s\n",
1085                                         (unsigned long long)entry->root_id,
1086                                         (unsigned long long)entry->gen,
1087                                         (unsigned long long)entry_snap->gen,
1088                                         (unsigned long long)parent_id,
1089                                         (unsigned long long)level, tstr, path);
1090                         }
1091                 } else {
1092                         if (print_uuid) {
1093                                 if (uuid_is_null(entry->uuid))
1094                                         strcpy(uuidparse, "-");
1095                                 else
1096                                         uuid_unparse(entry->uuid, uuidparse);
1097                                 printf("ID %llu gen %llu cgen %llu top level %llu "
1098                                         "otime %s uuid %s path %s\n",
1099                                         (unsigned long long)entry->root_id,
1100                                         (unsigned long long)entry->gen,
1101                                         (unsigned long long)entry_snap->gen,
1102                                         (unsigned long long)level,
1103                                         tstr, uuidparse, path);
1104                         } else {
1105                                 printf("ID %llu gen %llu cgen %llu top level %llu "
1106                                         "otime %s path %s\n",
1107                                         (unsigned long long)entry->root_id,
1108                                         (unsigned long long)entry->gen,
1109                                         (unsigned long long)entry_snap->gen,
1110                                         (unsigned long long)level, tstr, path);
1111                         }
1112                 }
1113
1114                 free(path);
1115                 if (!order)
1116                         n = rb_prev(n);
1117                 else
1118                         n = rb_next(n);
1119         }
1120
1121         return ret;
1122 }
1123
1124 static int print_one_extent(int fd, struct btrfs_ioctl_search_header *sh,
1125                             struct btrfs_file_extent_item *item,
1126                             u64 found_gen, u64 *cache_dirid,
1127                             char **cache_dir_name, u64 *cache_ino,
1128                             char **cache_full_name)
1129 {
1130         u64 len = 0;
1131         u64 disk_start = 0;
1132         u64 disk_offset = 0;
1133         u8 type;
1134         int compressed = 0;
1135         int flags = 0;
1136         char *name = NULL;
1137
1138         if (sh->objectid == *cache_ino) {
1139                 name = *cache_full_name;
1140         } else if (*cache_full_name) {
1141                 free(*cache_full_name);
1142                 *cache_full_name = NULL;
1143         }
1144         if (!name) {
1145                 name = ino_resolve(fd, sh->objectid, cache_dirid,
1146                                    cache_dir_name);
1147                 *cache_full_name = name;
1148                 *cache_ino = sh->objectid;
1149         }
1150         if (!name)
1151                 return -EIO;
1152
1153         type = btrfs_stack_file_extent_type(item);
1154         compressed = btrfs_stack_file_extent_compression(item);
1155
1156         if (type == BTRFS_FILE_EXTENT_REG ||
1157             type == BTRFS_FILE_EXTENT_PREALLOC) {
1158                 disk_start = btrfs_stack_file_extent_disk_bytenr(item);
1159                 disk_offset = btrfs_stack_file_extent_offset(item);
1160                 len = btrfs_stack_file_extent_num_bytes(item);
1161         } else if (type == BTRFS_FILE_EXTENT_INLINE) {
1162                 disk_start = 0;
1163                 disk_offset = 0;
1164                 len = btrfs_stack_file_extent_ram_bytes(item);
1165         } else {
1166                 printf("unhandled extent type %d for inode %llu "
1167                        "file offset %llu gen %llu\n",
1168                         type,
1169                         (unsigned long long)sh->objectid,
1170                         (unsigned long long)sh->offset,
1171                         (unsigned long long)found_gen);
1172
1173                 return -EIO;
1174         }
1175         printf("inode %llu file offset %llu len %llu disk start %llu "
1176                "offset %llu gen %llu flags ",
1177                (unsigned long long)sh->objectid,
1178                (unsigned long long)sh->offset,
1179                (unsigned long long)len,
1180                (unsigned long long)disk_start,
1181                (unsigned long long)disk_offset,
1182                (unsigned long long)found_gen);
1183
1184         if (compressed) {
1185                 printf("COMPRESS");
1186                 flags++;
1187         }
1188         if (type == BTRFS_FILE_EXTENT_PREALLOC) {
1189                 printf("%sPREALLOC", flags ? "|" : "");
1190                 flags++;
1191         }
1192         if (type == BTRFS_FILE_EXTENT_INLINE) {
1193                 printf("%sINLINE", flags ? "|" : "");
1194                 flags++;
1195         }
1196         if (!flags)
1197                 printf("NONE");
1198
1199         printf(" %s\n", name);
1200         return 0;
1201 }
1202
1203 int find_updated_files(int fd, u64 root_id, u64 oldest_gen)
1204 {
1205         int ret;
1206         struct btrfs_ioctl_search_args args;
1207         struct btrfs_ioctl_search_key *sk = &args.key;
1208         struct btrfs_ioctl_search_header *sh;
1209         struct btrfs_file_extent_item *item;
1210         unsigned long off = 0;
1211         u64 found_gen;
1212         u64 max_found = 0;
1213         int i;
1214         int e;
1215         u64 cache_dirid = 0;
1216         u64 cache_ino = 0;
1217         char *cache_dir_name = NULL;
1218         char *cache_full_name = NULL;
1219         struct btrfs_file_extent_item backup;
1220
1221         memset(&backup, 0, sizeof(backup));
1222         memset(&args, 0, sizeof(args));
1223
1224         sk->tree_id = root_id;
1225
1226         /*
1227          * set all the other params to the max, we'll take any objectid
1228          * and any trans
1229          */
1230         sk->max_objectid = (u64)-1;
1231         sk->max_offset = (u64)-1;
1232         sk->max_transid = (u64)-1;
1233         sk->max_type = BTRFS_EXTENT_DATA_KEY;
1234         sk->min_transid = oldest_gen;
1235         /* just a big number, doesn't matter much */
1236         sk->nr_items = 4096;
1237
1238         max_found = find_root_gen(fd);
1239         while(1) {
1240                 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
1241                 e = errno;
1242                 if (ret < 0) {
1243                         fprintf(stderr, "ERROR: can't perform the search- %s\n",
1244                                 strerror(e));
1245                         return ret;
1246                 }
1247                 /* the ioctl returns the number of item it found in nr_items */
1248                 if (sk->nr_items == 0)
1249                         break;
1250
1251                 off = 0;
1252
1253                 /*
1254                  * for each item, pull the key out of the header and then
1255                  * read the root_ref item it contains
1256                  */
1257                 for (i = 0; i < sk->nr_items; i++) {
1258                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
1259                                                                   off);
1260                         off += sizeof(*sh);
1261
1262                         /*
1263                          * just in case the item was too big, pass something other
1264                          * than garbage
1265                          */
1266                         if (sh->len == 0)
1267                                 item = &backup;
1268                         else
1269                                 item = (struct btrfs_file_extent_item *)(args.buf +
1270                                                                  off);
1271                         found_gen = btrfs_stack_file_extent_generation(item);
1272                         if (sh->type == BTRFS_EXTENT_DATA_KEY &&
1273                             found_gen >= oldest_gen) {
1274                                 print_one_extent(fd, sh, item, found_gen,
1275                                                  &cache_dirid, &cache_dir_name,
1276                                                  &cache_ino, &cache_full_name);
1277                         }
1278                         off += sh->len;
1279
1280                         /*
1281                          * record the mins in sk so we can make sure the
1282                          * next search doesn't repeat this root
1283                          */
1284                         sk->min_objectid = sh->objectid;
1285                         sk->min_offset = sh->offset;
1286                         sk->min_type = sh->type;
1287                 }
1288                 sk->nr_items = 4096;
1289                 if (sk->min_offset < (u64)-1)
1290                         sk->min_offset++;
1291                 else if (sk->min_objectid < (u64)-1) {
1292                         sk->min_objectid++;
1293                         sk->min_offset = 0;
1294                         sk->min_type = 0;
1295                 } else
1296                         break;
1297         }
1298         free(cache_dir_name);
1299         free(cache_full_name);
1300         printf("transid marker was %llu\n", (unsigned long long)max_found);
1301         return ret;
1302 }
1303
1304 char *path_for_root(int fd, u64 root)
1305 {
1306         struct root_lookup root_lookup;
1307         struct rb_node *n;
1308         char *ret_path = NULL;
1309         int ret;
1310
1311         ret = __list_subvol_search(fd, &root_lookup);
1312         if (ret < 0)
1313                 return ERR_PTR(ret);
1314
1315         ret = __list_subvol_fill_paths(fd, &root_lookup);
1316         if (ret < 0)
1317                 return ERR_PTR(ret);
1318
1319         n = rb_last(&root_lookup.root);
1320         while (n) {
1321                 struct root_info *entry;
1322                 u64 parent_id;
1323                 u64 level;
1324                 char *path;
1325
1326                 entry = rb_entry(n, struct root_info, rb_node);
1327                 resolve_root(&root_lookup, entry, &parent_id, &level, &path);
1328                 if (entry->root_id == root)
1329                         ret_path = path;
1330                 else
1331                         free(path);
1332
1333                 n = rb_prev(n);
1334         }
1335
1336         return ret_path;
1337 }