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