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