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