btrfs-list.c

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