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 #ifndef __CHECKER__
  20 #include <sys/ioctl.h>
  21 #include <sys/mount.h>
  22 #include "ioctl.h"
  23 #endif
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26 #include <sys/types.h>
  27 #include <sys/stat.h>
  28 #include <fcntl.h>
  29 #include <unistd.h>
  30 #include <dirent.h>
  31 #include <libgen.h>
  32 #include "kerncompat.h"
  33 #include "ctree.h"
  34 #include "transaction.h"
  35 #include "utils.h"
  36 #include "version.h"
  37
  38 /* we store all the roots we find in an rbtree so that we can
  39  * search for them later.
  40  */
  41 struct root_lookup {
  42         struct rb_root root;
  43 };
  44
  45 /*
  46  * one of these for each root we find.
  47  */
  48 struct root_info {
  49         struct rb_node rb_node;
  50
  51         /* this root's id */
  52         u64 root_id;
  53
  54         /* the id of the root that references this one */
  55         u64 ref_tree;
  56
  57         /* the dir id we're in from ref_tree */
  58         u64 dir_id;
  59
  60         /* path from the subvol we live in to this root, including the
  61          * root's name.  This is null until we do the extra lookup ioctl.
  62          */
  63         char *path;
  64
  65         /* the name of this root in the directory it lives in */
  66         char name[];
  67 };
  68
  69 static void root_lookup_init(struct root_lookup *tree)
  70 {
  71         tree->root.rb_node = NULL;
  72 }
  73
  74 static int comp_entry(struct root_info *entry, u64 root_id, u64 ref_tree)
  75 {
  76         if (entry->root_id > root_id)
  77                 return 1;
  78         if (entry->root_id < root_id)
  79                 return -1;
  80         if (entry->ref_tree > ref_tree)
  81                 return 1;
  82         if (entry->ref_tree < ref_tree)
  83                 return -1;
  84         return 0;
  85 }
  86
  87 /*
  88  * insert a new root into the tree.  returns the existing root entry
  89  * if one is already there.  Both root_id and ref_tree are used
  90  * as the key
  91  */
  92 static struct rb_node *tree_insert(struct rb_root *root, u64 root_id,
  93                                    u64 ref_tree, struct rb_node *node)
  94 {
  95         struct rb_node ** p = &root->rb_node;
  96         struct rb_node * parent = NULL;
  97         struct root_info *entry;
  98         int comp;
  99
 100         while(*p) {
 101                 parent = *p;
 102                 entry = rb_entry(parent, struct root_info, rb_node);
 103
 104                 comp = comp_entry(entry, root_id, ref_tree);
 105
 106                 if (comp < 0)
 107                         p = &(*p)->rb_left;
 108                 else if (comp > 0)
 109                         p = &(*p)->rb_right;
 110                 else
 111                         return parent;
 112         }
 113
 114         entry = rb_entry(parent, struct root_info, rb_node);
 115         rb_link_node(node, parent, p);
 116         rb_insert_color(node, root);
 117         return NULL;
 118 }
 119
 120 /*
 121  * find a given root id in the tree.  We return the smallest one,
 122  * rb_next can be used to move forward looking for more if required
 123  */
 124 static struct root_info *tree_search(struct rb_root *root, u64 root_id)
 125 {
 126         struct rb_node * n = root->rb_node;
 127         struct root_info *entry;
 128
 129         while(n) {
 130                 entry = rb_entry(n, struct root_info, rb_node);
 131
 132                 if (entry->root_id < root_id)
 133                         n = n->rb_left;
 134                 else if (entry->root_id > root_id)
 135                         n = n->rb_right;
 136                 else {
 137                         struct root_info *prev;
 138                         struct rb_node *prev_n;
 139                         while (1) {
 140                                 prev_n = rb_prev(n);
 141                                 if (!prev_n)
 142                                         break;
 143                                 prev = rb_entry(prev_n, struct root_info,
 144                                                       rb_node);
 145                                 if (prev->root_id != root_id)
 146                                         break;
 147                                 entry = prev;
 148                                 n = prev_n;
 149                         }
 150                         return entry;
 151                 }
 152         }
 153         return NULL;
 154 }
 155
 156 /*
 157  * this allocates a new root in the lookup tree.
 158  *
 159  * root_id should be the object id of the root
 160  *
 161  * ref_tree is the objectid of the referring root.
 162  *
 163  * dir_id is the directory in ref_tree where this root_id can be found.
 164  *
 165  * name is the name of root_id in that directory
 166  *
 167  * name_len is the length of name
 168  */
 169 static int add_root(struct root_lookup *root_lookup,
 170                     u64 root_id, u64 ref_tree, u64 dir_id, char *name,
 171                     int name_len)
 172 {
 173         struct root_info *ri;
 174         struct rb_node *ret;
 175         ri = malloc(sizeof(*ri) + name_len + 1);
 176         if (!ri) {
 177                 printf("memory allocation failed\n");
 178                 exit(1);
 179         }
 180         memset(ri, 0, sizeof(*ri) + name_len + 1);
 181         ri->path = NULL;
 182         ri->dir_id = dir_id;
 183         ri->root_id = root_id;
 184         ri->ref_tree = ref_tree;
 185         strncpy(ri->name, name, name_len);
 186
 187         ret = tree_insert(&root_lookup->root, root_id, ref_tree, &ri->rb_node);
 188         if (ret) {
 189                 printf("failed to insert tree %llu\n", (unsigned long long)root_id);
 190                 exit(1);
 191         }
 192         return 0;
 193 }
 194
 195 /*
 196  * for a given root_info, search through the root_lookup tree to construct
 197  * the full path name to it.
 198  *
 199  * This can't be called until all the root_info->path fields are filled
 200  * in by lookup_ino_path
 201  */
 202 static int resolve_root(struct root_lookup *rl, struct root_info *ri)
 203 {
 204         u64 top_id;
 205         char *full_path = NULL;
 206         int len = 0;
 207         struct root_info *found;
 208
 209         /*
 210          * we go backwards from the root_info object and add pathnames
 211          * from parent directories as we go.
 212          */
 213         found = ri;
 214         while (1) {
 215                 char *tmp;
 216                 u64 next;
 217                 int add_len = strlen(found->path);
 218
 219                 /* room for / and for null */
 220                 tmp = malloc(add_len + 2 + len);
 221                 if (full_path) {
 222                         memcpy(tmp + add_len + 1, full_path, len);
 223                         tmp[add_len] = '/';
 224                         memcpy(tmp, found->path, add_len);
 225                         tmp [add_len + len + 1] = '\0';
 226                         free(full_path);
 227                         full_path = tmp;
 228                         len += add_len + 1;
 229                 } else {
 230                         full_path = strdup(found->path);
 231                         len = add_len;
 232                 }
 233
 234                 next = found->ref_tree;
 235                 /* if the ref_tree refers to ourselves, we're at the top */
 236                 if (next == found->root_id) {
 237                         top_id = next;
 238                         break;
 239                 }
 240
 241                 /*
 242                  * if the ref_tree wasn't in our tree of roots, we're
 243                  * at the top
 244                  */
 245                 found = tree_search(&rl->root, next);
 246                 if (!found) {
 247                         top_id = next;
 248                         break;
 249                 }
 250         }
 251         printf("ID %llu top level %llu path %s\n", ri->root_id, top_id,
 252                full_path);
 253         free(full_path);
 254         return 0;
 255 }
 256
 257 /*
 258  * for a single root_info, ask the kernel to give us a path name
 259  * inside it's ref_root for the dir_id where it lives.
 260  *
 261  * This fills in root_info->path with the path to the directory and and
 262  * appends this root's name.
 263  */
 264 static int lookup_ino_path(int fd, struct root_info *ri)
 265 {
 266         struct btrfs_ioctl_ino_lookup_args args;
 267         int ret;
 268
 269         if (ri->path)
 270                 return 0;
 271
 272         memset(&args, 0, sizeof(args));
 273         args.treeid = ri->ref_tree;
 274         args.objectid = ri->dir_id;
 275
 276         ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &args);
 277         if (ret) {
 278                 fprintf(stderr, "ERROR: Failed to lookup path for root %llu\n",
 279                         (unsigned long long)ri->ref_tree);
 280                 return ret;
 281         }
 282
 283         if (args.name[0]) {
 284                 /*
 285                  * we're in a subdirectory of ref_tree, the kernel ioctl
 286                  * puts a / in there for us
 287                  */
 288                 ri->path = malloc(strlen(ri->name) + strlen(args.name) + 1);
 289                 if (!ri->path) {
 290                         perror("malloc failed");
 291                         exit(1);
 292                 }
 293                 strcpy(ri->path, args.name);
 294                 strcat(ri->path, ri->name);
 295         } else {
 296                 /* we're at the root of ref_tree */
 297                 ri->path = strdup(ri->name);
 298                 if (!ri->path) {
 299                         perror("strdup failed");
 300                         exit(1);
 301                 }
 302         }
 303         return 0;
 304 }
 305
 306 /* finding the generation for a given path is a two step process.
 307  * First we use the inode loookup routine to find out the root id
 308  *
 309  * Then we use the tree search ioctl to scan all the root items for a
 310  * given root id and spit out the latest generation we can find
 311  */
 312 static u64 find_root_gen(int fd)
 313 {
 314         struct btrfs_ioctl_ino_lookup_args ino_args;
 315         int ret;
 316         struct btrfs_ioctl_search_args args;
 317         struct btrfs_ioctl_search_key *sk = &args.key;
 318         struct btrfs_ioctl_search_header *sh;
 319         unsigned long off = 0;
 320         u64 max_found = 0;
 321         int i;
 322
 323         memset(&ino_args, 0, sizeof(ino_args));
 324         ino_args.objectid = BTRFS_FIRST_FREE_OBJECTID;
 325
 326         /* this ioctl fills in ino_args->treeid */
 327         ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &ino_args);
 328         if (ret) {
 329                 fprintf(stderr, "ERROR: Failed to lookup path for dirid %llu\n",
 330                         (unsigned long long)BTRFS_FIRST_FREE_OBJECTID);
 331                 return 0;
 332         }
 333
 334         memset(&args, 0, sizeof(args));
 335
 336         sk->tree_id = 1;
 337
 338         /*
 339          * there may be more than one ROOT_ITEM key if there are
 340          * snapshots pending deletion, we have to loop through
 341          * them.
 342          */
 343         sk->min_objectid = ino_args.treeid;
 344         sk->max_objectid = ino_args.treeid;
 345         sk->max_type = BTRFS_ROOT_ITEM_KEY;
 346         sk->min_type = BTRFS_ROOT_ITEM_KEY;
 347         sk->max_offset = (u64)-1;
 348         sk->max_transid = (u64)-1;
 349         sk->nr_items = 4096;
 350
 351         while (1) {
 352                 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 353                 if (ret < 0) {
 354                         fprintf(stderr, "ERROR: can't perform the search\n");
 355                         return 0;
 356                 }
 357                 /* the ioctl returns the number of item it found in nr_items */
 358                 if (sk->nr_items == 0)
 359                         break;
 360
 361                 off = 0;
 362                 for (i = 0; i < sk->nr_items; i++) {
 363                         struct btrfs_root_item *item;
 364                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 365                                                                   off);
 366
 367                         off += sizeof(*sh);
 368                         item = (struct btrfs_root_item *)(args.buf + off);
 369                         off += sh->len;
 370
 371                         sk->min_objectid = sh->objectid;
 372                         sk->min_type = sh->type;
 373                         sk->min_offset = sh->offset;
 374
 375                         if (sh->objectid > ino_args.treeid)
 376                                 break;
 377
 378                         if (sh->objectid == ino_args.treeid &&
 379                             sh->type == BTRFS_ROOT_ITEM_KEY) {
 380                                 max_found = max(max_found,
 381                                                 btrfs_root_generation(item));
 382                         }
 383                 }
 384                 if (sk->min_offset < (u64)-1)
 385                         sk->min_offset++;
 386                 else
 387                         break;
 388
 389                 if (sk->min_type != BTRFS_ROOT_ITEM_KEY)
 390                         break;
 391                 if (sk->min_objectid != BTRFS_ROOT_ITEM_KEY)
 392                         break;
 393         }
 394         return max_found;
 395 }
 396
 397 /* pass in a directory id and this will return
 398  * the full path of the parent directory inside its
 399  * subvolume root.
 400  *
 401  * It may return NULL if it is in the root, or an ERR_PTR if things
 402  * go badly.
 403  */
 404 static char *__ino_resolve(int fd, u64 dirid)
 405 {
 406         struct btrfs_ioctl_ino_lookup_args args;
 407         int ret;
 408         char *full;
 409
 410         memset(&args, 0, sizeof(args));
 411         args.objectid = dirid;
 412
 413         ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &args);
 414         if (ret) {
 415                 fprintf(stderr, "ERROR: Failed to lookup path for dirid %llu\n",
 416                         (unsigned long long)dirid);
 417                 return ERR_PTR(ret);
 418         }
 419
 420         if (args.name[0]) {
 421                 /*
 422                  * we're in a subdirectory of ref_tree, the kernel ioctl
 423                  * puts a / in there for us
 424                  */
 425                 full = strdup(args.name);
 426                 if (!full) {
 427                         perror("malloc failed");
 428                         return ERR_PTR(-ENOMEM);
 429                 }
 430         } else {
 431                 /* we're at the root of ref_tree */
 432                 full = NULL;
 433         }
 434         return full;
 435 }
 436
 437 /*
 438  * simple string builder, returning a new string with both
 439  * dirid and name
 440  */
 441 char *build_name(char *dirid, char *name)
 442 {
 443         char *full;
 444         if (!dirid)
 445                 return strdup(name);
 446
 447         full = malloc(strlen(dirid) + strlen(name) + 1);
 448         if (!full)
 449                 return NULL;
 450         strcpy(full, dirid);
 451         strcat(full, name);
 452         return full;
 453 }
 454
 455 /*
 456  * given an inode number, this returns the full path name inside the subvolume
 457  * to that file/directory.  cache_dirid and cache_name are used to
 458  * cache the results so we can avoid tree searches if a later call goes
 459  * to the same directory or file name
 460  */
 461 static char *ino_resolve(int fd, u64 ino, u64 *cache_dirid, char **cache_name)
 462
 463 {
 464         u64 dirid;
 465         char *dirname;
 466         char *name;
 467         char *full;
 468         int ret;
 469         struct btrfs_ioctl_search_args args;
 470         struct btrfs_ioctl_search_key *sk = &args.key;
 471         struct btrfs_ioctl_search_header *sh;
 472         unsigned long off = 0;
 473         int namelen;
 474
 475         memset(&args, 0, sizeof(args));
 476
 477         sk->tree_id = 0;
 478
 479         /*
 480          * step one, we search for the inode back ref.  We just use the first
 481          * one
 482          */
 483         sk->min_objectid = ino;
 484         sk->max_objectid = ino;
 485         sk->max_type = BTRFS_INODE_REF_KEY;
 486         sk->max_offset = (u64)-1;
 487         sk->min_type = BTRFS_INODE_REF_KEY;
 488         sk->max_transid = (u64)-1;
 489         sk->nr_items = 1;
 490
 491         ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 492         if (ret < 0) {
 493                 fprintf(stderr, "ERROR: can't perform the search\n");
 494                 return NULL;
 495         }
 496         /* the ioctl returns the number of item it found in nr_items */
 497         if (sk->nr_items == 0)
 498                 return NULL;
 499
 500         off = 0;
 501         sh = (struct btrfs_ioctl_search_header *)(args.buf + off);
 502
 503         if (sh->type == BTRFS_INODE_REF_KEY) {
 504                 struct btrfs_inode_ref *ref;
 505                 dirid = sh->offset;
 506
 507                 ref = (struct btrfs_inode_ref *)(sh + 1);
 508                 namelen = btrfs_stack_inode_ref_name_len(ref);
 509
 510                 name = (char *)(ref + 1);
 511                 name = strndup(name, namelen);
 512
 513                 /* use our cached value */
 514                 if (dirid == *cache_dirid && *cache_name) {
 515                         dirname = *cache_name;
 516                         goto build;
 517                 }
 518         } else {
 519                 return NULL;
 520         }
 521         /*
 522          * the inode backref gives us the file name and the parent directory id.
 523          * From here we use __ino_resolve to get the path to the parent
 524          */
 525         dirname = __ino_resolve(fd, dirid);
 526 build:
 527         full = build_name(dirname, name);
 528         if (*cache_name && dirname != *cache_name)
 529                 free(*cache_name);
 530
 531         *cache_name = dirname;
 532         *cache_dirid = dirid;
 533         free(name);
 534
 535         return full;
 536 }
 537
 538 int list_subvols(int fd)
 539 {
 540         struct root_lookup root_lookup;
 541         struct rb_node *n;
 542         int ret;
 543         struct btrfs_ioctl_search_args args;
 544         struct btrfs_ioctl_search_key *sk = &args.key;
 545         struct btrfs_ioctl_search_header *sh;
 546         struct btrfs_root_ref *ref;
 547         unsigned long off = 0;
 548         int name_len;
 549         char *name;
 550         u64 dir_id;
 551         int i;
 552
 553         root_lookup_init(&root_lookup);
 554
 555         memset(&args, 0, sizeof(args));
 556
 557         /* search in the tree of tree roots */
 558         sk->tree_id = 1;
 559
 560         /*
 561          * set the min and max to backref keys.  The search will
 562          * only send back this type of key now.
 563          */
 564         sk->max_type = BTRFS_ROOT_BACKREF_KEY;
 565         sk->min_type = BTRFS_ROOT_BACKREF_KEY;
 566
 567         /*
 568          * set all the other params to the max, we'll take any objectid
 569          * and any trans
 570          */
 571         sk->max_objectid = (u64)-1;
 572         sk->max_offset = (u64)-1;
 573         sk->max_transid = (u64)-1;
 574
 575         /* just a big number, doesn't matter much */
 576         sk->nr_items = 4096;
 577
 578         while(1) {
 579                 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 580                 if (ret < 0) {
 581                         fprintf(stderr, "ERROR: can't perform the search\n");
 582                         return ret;
 583                 }
 584                 /* the ioctl returns the number of item it found in nr_items */
 585                 if (sk->nr_items == 0)
 586                         break;
 587
 588                 off = 0;
 589
 590                 /*
 591                  * for each item, pull the key out of the header and then
 592                  * read the root_ref item it contains
 593                  */
 594                 for (i = 0; i < sk->nr_items; i++) {
 595                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 596                                                                   off);
 597                         off += sizeof(*sh);
 598                         if (sh->type == BTRFS_ROOT_BACKREF_KEY) {
 599                                 ref = (struct btrfs_root_ref *)(args.buf + off);
 600                                 name_len = btrfs_stack_root_ref_name_len(ref);
 601                                 name = (char *)(ref + 1);
 602                                 dir_id = btrfs_stack_root_ref_dirid(ref);
 603
 604                                 add_root(&root_lookup, sh->objectid, sh->offset,
 605                                          dir_id, name, name_len);
 606                         }
 607
 608                         off += sh->len;
 609
 610                         /*
 611                          * record the mins in sk so we can make sure the
 612                          * next search doesn't repeat this root
 613                          */
 614                         sk->min_objectid = sh->objectid;
 615                         sk->min_type = sh->type;
 616                         sk->min_offset = sh->offset;
 617                 }
 618                 sk->nr_items = 4096;
 619                 /* this iteration is done, step forward one root for the next
 620                  * ioctl
 621                  */
 622                 if (sk->min_objectid < (u64)-1) {
 623                         sk->min_objectid++;
 624                         sk->min_type = BTRFS_ROOT_BACKREF_KEY;
 625                         sk->min_offset = 0;
 626                 } else
 627                         break;
 628         }
 629         /*
 630          * now we have an rbtree full of root_info objects, but we need to fill
 631          * in their path names within the subvol that is referencing each one.
 632          */
 633         n = rb_first(&root_lookup.root);
 634         while (n) {
 635                 struct root_info *entry;
 636                 int ret;
 637                 entry = rb_entry(n, struct root_info, rb_node);
 638                 ret = lookup_ino_path(fd, entry);
 639                 if(ret < 0)
 640                         return ret;
 641                 n = rb_next(n);
 642         }
 643
 644         /* now that we have all the subvol-relative paths filled in,
 645          * we have to string the subvols together so that we can get
 646          * a path all the way back to the FS root
 647          */
 648         n = rb_last(&root_lookup.root);
 649         while (n) {
 650                 struct root_info *entry;
 651                 entry = rb_entry(n, struct root_info, rb_node);
 652                 resolve_root(&root_lookup, entry);
 653                 n = rb_prev(n);
 654         }
 655
 656         return ret;
 657 }
 658
 659 static int print_one_extent(int fd, struct btrfs_ioctl_search_header *sh,
 660                             struct btrfs_file_extent_item *item,
 661                             u64 found_gen, u64 *cache_dirid,
 662                             char **cache_dir_name, u64 *cache_ino,
 663                             char **cache_full_name)
 664 {
 665         u64 len;
 666         u64 disk_start;
 667         u64 disk_offset;
 668         u8 type;
 669         int compressed = 0;
 670         int flags = 0;
 671         char *name = NULL;
 672
 673         if (sh->objectid == *cache_ino) {
 674                 name = *cache_full_name;
 675         } else if (*cache_full_name) {
 676                 free(*cache_full_name);
 677                 *cache_full_name = NULL;
 678         }
 679         if (!name) {
 680                 name = ino_resolve(fd, sh->objectid, cache_dirid,
 681                                    cache_dir_name);
 682                 *cache_full_name = name;
 683                 *cache_ino = sh->objectid;
 684         }
 685         if (!name)
 686                 return -EIO;
 687
 688         type = btrfs_stack_file_extent_type(item);
 689         compressed = btrfs_stack_file_extent_compression(item);
 690
 691         if (type == BTRFS_FILE_EXTENT_REG ||
 692             type == BTRFS_FILE_EXTENT_PREALLOC) {
 693                 disk_start = btrfs_stack_file_extent_disk_bytenr(item);
 694                 disk_offset = btrfs_stack_file_extent_offset(item);
 695                 len = btrfs_stack_file_extent_num_bytes(item);
 696         } else if (type == BTRFS_FILE_EXTENT_INLINE) {
 697                 disk_start = 0;
 698                 disk_offset = 0;
 699                 len = btrfs_stack_file_extent_ram_bytes(item);
 700         }
 701         printf("inode %llu file offset %llu len %llu disk start %llu "
 702                "offset %llu gen %llu flags ",
 703                (unsigned long long)sh->objectid,
 704                (unsigned long long)sh->offset,
 705                (unsigned long long)len,
 706                (unsigned long long)disk_start,
 707                (unsigned long long)disk_offset,
 708                (unsigned long long)found_gen);
 709
 710         if (compressed) {
 711                 printf("COMPRESS");
 712                 flags++;
 713         }
 714         if (type == BTRFS_FILE_EXTENT_PREALLOC) {
 715                 printf("%sPREALLOC", flags ? "|" : "");
 716                 flags++;
 717         }
 718         if (type == BTRFS_FILE_EXTENT_INLINE) {
 719                 printf("%sINLINE", flags ? "|" : "");
 720                 flags++;
 721         }
 722         if (!flags)
 723                 printf("NONE");
 724
 725         printf(" %s\n", name);
 726         return 0;
 727 }
 728
 729 int find_updated_files(int fd, u64 root_id, u64 oldest_gen)
 730 {
 731         int ret;
 732         struct btrfs_ioctl_search_args args;
 733         struct btrfs_ioctl_search_key *sk = &args.key;
 734         struct btrfs_ioctl_search_header *sh;
 735         struct btrfs_file_extent_item *item;
 736         unsigned long off = 0;
 737         u64 found_gen;
 738         u64 max_found = 0;
 739         int i;
 740         u64 cache_dirid = 0;
 741         u64 cache_ino = 0;
 742         char *cache_dir_name = NULL;
 743         char *cache_full_name = NULL;
 744         struct btrfs_file_extent_item backup;
 745
 746         memset(&backup, 0, sizeof(backup));
 747         memset(&args, 0, sizeof(args));
 748
 749         sk->tree_id = root_id;
 750
 751         /*
 752          * set all the other params to the max, we'll take any objectid
 753          * and any trans
 754          */
 755         sk->max_objectid = (u64)-1;
 756         sk->max_offset = (u64)-1;
 757         sk->max_transid = (u64)-1;
 758         sk->max_type = BTRFS_EXTENT_DATA_KEY;
 759         sk->min_transid = oldest_gen;
 760         /* just a big number, doesn't matter much */
 761         sk->nr_items = 4096;
 762
 763         max_found = find_root_gen(fd);
 764         while(1) {
 765                 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 766                 if (ret < 0) {
 767                         fprintf(stderr, "ERROR: can't perform the search\n");
 768                         return ret;
 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
 776                 /*
 777                  * for each item, pull the key out of the header and then
 778                  * read the root_ref item it contains
 779                  */
 780                 for (i = 0; i < sk->nr_items; i++) {
 781                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 782                                                                   off);
 783                         off += sizeof(*sh);
 784
 785                         /*
 786                          * just in case the item was too big, pass something other
 787                          * than garbage
 788                          */
 789                         if (sh->len == 0)
 790                                 item = &backup;
 791                         else
 792                                 item = (struct btrfs_file_extent_item *)(args.buf +
 793                                                                  off);
 794                         found_gen = btrfs_stack_file_extent_generation(item);
 795                         if (sh->type == BTRFS_EXTENT_DATA_KEY &&
 796                             found_gen >= oldest_gen) {
 797                                 print_one_extent(fd, sh, item, found_gen,
 798                                                  &cache_dirid, &cache_dir_name,
 799                                                  &cache_ino, &cache_full_name);
 800                         }
 801                         off += sh->len;
 802
 803                         /*
 804                          * record the mins in sk so we can make sure the
 805                          * next search doesn't repeat this root
 806                          */
 807                         sk->min_objectid = sh->objectid;
 808                         sk->min_offset = sh->offset;
 809                         sk->min_type = sh->type;
 810                 }
 811                 sk->nr_items = 4096;
 812                 if (sk->min_offset < (u64)-1)
 813                         sk->min_offset++;
 814                 else if (sk->min_objectid < (u64)-1) {
 815                         sk->min_objectid++;
 816                         sk->min_offset = 0;
 817                         sk->min_type = 0;
 818                 } else
 819                         break;
 820         }
 821         free(cache_dir_name);
 822         free(cache_full_name);
 823         printf("transid marker was %llu\n", (unsigned long long)max_found);
 824         return ret;
 825 }