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