2 * Copyright (C) 2010 Oracle. All rights reserved.
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.
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.
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.
21 #include <sys/ioctl.h>
22 #include <sys/mount.h>
27 #include <sys/types.h>
33 #include "kerncompat.h"
35 #include "transaction.h"
39 /* we store all the roots we find in an rbtree so that we can
40 * search for them later.
47 * one of these for each root we find.
50 struct rb_node rb_node
;
55 /* the id of the root that references this one */
58 /* the dir id we're in from ref_tree */
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.
66 /* the name of this root in the directory it lives in */
70 static void root_lookup_init(struct root_lookup
*tree
)
72 tree
->root
.rb_node
= NULL
;
75 static int comp_entry(struct root_info
*entry
, u64 root_id
, u64 ref_tree
)
77 if (entry
->root_id
> root_id
)
79 if (entry
->root_id
< root_id
)
81 if (entry
->ref_tree
> ref_tree
)
83 if (entry
->ref_tree
< ref_tree
)
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
93 static struct rb_node
*tree_insert(struct rb_root
*root
, u64 root_id
,
94 u64 ref_tree
, struct rb_node
*node
)
96 struct rb_node
** p
= &root
->rb_node
;
97 struct rb_node
* parent
= NULL
;
98 struct root_info
*entry
;
103 entry
= rb_entry(parent
, struct root_info
, rb_node
);
105 comp
= comp_entry(entry
, root_id
, ref_tree
);
115 entry
= rb_entry(parent
, struct root_info
, rb_node
);
116 rb_link_node(node
, parent
, p
);
117 rb_insert_color(node
, root
);
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
125 static struct root_info
*tree_search(struct rb_root
*root
, u64 root_id
)
127 struct rb_node
* n
= root
->rb_node
;
128 struct root_info
*entry
;
131 entry
= rb_entry(n
, struct root_info
, rb_node
);
133 if (entry
->root_id
< root_id
)
135 else if (entry
->root_id
> root_id
)
138 struct root_info
*prev
;
139 struct rb_node
*prev_n
;
144 prev
= rb_entry(prev_n
, struct root_info
,
146 if (prev
->root_id
!= root_id
)
158 * this allocates a new root in the lookup tree.
160 * root_id should be the object id of the root
162 * ref_tree is the objectid of the referring root.
164 * dir_id is the directory in ref_tree where this root_id can be found.
166 * name is the name of root_id in that directory
168 * name_len is the length of name
170 static int add_root(struct root_lookup
*root_lookup
,
171 u64 root_id
, u64 ref_tree
, u64 dir_id
, char *name
,
174 struct root_info
*ri
;
176 ri
= malloc(sizeof(*ri
) + name_len
+ 1);
178 printf("memory allocation failed\n");
181 memset(ri
, 0, sizeof(*ri
) + name_len
+ 1);
184 ri
->root_id
= root_id
;
185 ri
->ref_tree
= ref_tree
;
186 strncpy(ri
->name
, name
, name_len
);
188 ret
= tree_insert(&root_lookup
->root
, root_id
, ref_tree
, &ri
->rb_node
);
190 printf("failed to insert tree %llu\n", (unsigned long long)root_id
);
197 * for a given root_info, search through the root_lookup tree to construct
198 * the full path name to it.
200 * This can't be called until all the root_info->path fields are filled
201 * in by lookup_ino_path
203 static int resolve_root(struct root_lookup
*rl
, struct root_info
*ri
)
206 char *full_path
= NULL
;
208 struct root_info
*found
;
211 * we go backwards from the root_info object and add pathnames
212 * from parent directories as we go.
218 int add_len
= strlen(found
->path
);
220 /* room for / and for null */
221 tmp
= malloc(add_len
+ 2 + len
);
223 memcpy(tmp
+ add_len
+ 1, full_path
, len
);
225 memcpy(tmp
, found
->path
, add_len
);
226 tmp
[add_len
+ len
+ 1] = '\0';
231 full_path
= strdup(found
->path
);
235 next
= found
->ref_tree
;
236 /* if the ref_tree refers to ourselves, we're at the top */
237 if (next
== found
->root_id
) {
243 * if the ref_tree wasn't in our tree of roots, we're
246 found
= tree_search(&rl
->root
, next
);
252 printf("ID %llu top level %llu path %s\n", ri
->root_id
, top_id
,
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.
262 * This fills in root_info->path with the path to the directory and and
263 * appends this root's name.
265 static int lookup_ino_path(int fd
, struct root_info
*ri
)
267 struct btrfs_ioctl_ino_lookup_args args
;
273 memset(&args
, 0, sizeof(args
));
274 args
.treeid
= ri
->ref_tree
;
275 args
.objectid
= ri
->dir_id
;
277 ret
= ioctl(fd
, BTRFS_IOC_INO_LOOKUP
, &args
);
280 fprintf(stderr
, "ERROR: Failed to lookup path for root %llu - %s\n",
281 (unsigned long long)ri
->ref_tree
,
288 * we're in a subdirectory of ref_tree, the kernel ioctl
289 * puts a / in there for us
291 ri
->path
= malloc(strlen(ri
->name
) + strlen(args
.name
) + 1);
293 perror("malloc failed");
296 strcpy(ri
->path
, args
.name
);
297 strcat(ri
->path
, ri
->name
);
299 /* we're at the root of ref_tree */
300 ri
->path
= strdup(ri
->name
);
302 perror("strdup failed");
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
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
315 static u64
find_root_gen(int fd
)
317 struct btrfs_ioctl_ino_lookup_args ino_args
;
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;
327 memset(&ino_args
, 0, sizeof(ino_args
));
328 ino_args
.objectid
= BTRFS_FIRST_FREE_OBJECTID
;
330 /* this ioctl fills in ino_args->treeid */
331 ret
= ioctl(fd
, BTRFS_IOC_INO_LOOKUP
, &ino_args
);
334 fprintf(stderr
, "ERROR: Failed to lookup path for dirid %llu - %s\n",
335 (unsigned long long)BTRFS_FIRST_FREE_OBJECTID
,
340 memset(&args
, 0, sizeof(args
));
345 * there may be more than one ROOT_ITEM key if there are
346 * snapshots pending deletion, we have to loop through
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;
358 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
361 fprintf(stderr
, "ERROR: can't perform the search - %s\n",
365 /* the ioctl returns the number of item it found in nr_items */
366 if (sk
->nr_items
== 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
+
376 item
= (struct btrfs_root_item
*)(args
.buf
+ off
);
379 sk
->min_objectid
= sh
->objectid
;
380 sk
->min_type
= sh
->type
;
381 sk
->min_offset
= sh
->offset
;
383 if (sh
->objectid
> ino_args
.treeid
)
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
));
392 if (sk
->min_offset
< (u64
)-1)
397 if (sk
->min_type
!= BTRFS_ROOT_ITEM_KEY
)
399 if (sk
->min_objectid
!= BTRFS_ROOT_ITEM_KEY
)
405 /* pass in a directory id and this will return
406 * the full path of the parent directory inside its
409 * It may return NULL if it is in the root, or an ERR_PTR if things
412 static char *__ino_resolve(int fd
, u64 dirid
)
414 struct btrfs_ioctl_ino_lookup_args args
;
419 memset(&args
, 0, sizeof(args
));
420 args
.objectid
= dirid
;
422 ret
= ioctl(fd
, BTRFS_IOC_INO_LOOKUP
, &args
);
425 fprintf(stderr
, "ERROR: Failed to lookup path for dirid %llu - %s\n",
426 (unsigned long long)dirid
, strerror(e
) );
432 * we're in a subdirectory of ref_tree, the kernel ioctl
433 * puts a / in there for us
435 full
= strdup(args
.name
);
437 perror("malloc failed");
438 return ERR_PTR(-ENOMEM
);
441 /* we're at the root of ref_tree */
448 * simple string builder, returning a new string with both
451 char *build_name(char *dirid
, char *name
)
457 full
= malloc(strlen(dirid
) + strlen(name
) + 1);
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
471 static char *ino_resolve(int fd
, u64 ino
, u64
*cache_dirid
, char **cache_name
)
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;
486 memset(&args
, 0, sizeof(args
));
491 * step one, we search for the inode back ref. We just use the first
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;
502 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
505 fprintf(stderr
, "ERROR: can't perform the search - %s\n",
509 /* the ioctl returns the number of item it found in nr_items */
510 if (sk
->nr_items
== 0)
514 sh
= (struct btrfs_ioctl_search_header
*)(args
.buf
+ off
);
516 if (sh
->type
== BTRFS_INODE_REF_KEY
) {
517 struct btrfs_inode_ref
*ref
;
520 ref
= (struct btrfs_inode_ref
*)(sh
+ 1);
521 namelen
= btrfs_stack_inode_ref_name_len(ref
);
523 name
= (char *)(ref
+ 1);
524 name
= strndup(name
, namelen
);
526 /* use our cached value */
527 if (dirid
== *cache_dirid
&& *cache_name
) {
528 dirname
= *cache_name
;
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
538 dirname
= __ino_resolve(fd
, dirid
);
540 full
= build_name(dirname
, name
);
541 if (*cache_name
&& dirname
!= *cache_name
)
544 *cache_name
= dirname
;
545 *cache_dirid
= dirid
;
551 int list_subvols(int fd
)
553 struct root_lookup root_lookup
;
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;
567 root_lookup_init(&root_lookup
);
569 memset(&args
, 0, sizeof(args
));
571 /* search in the tree of tree roots */
575 * set the min and max to backref keys. The search will
576 * only send back this type of key now.
578 sk
->max_type
= BTRFS_ROOT_BACKREF_KEY
;
579 sk
->min_type
= BTRFS_ROOT_BACKREF_KEY
;
582 * set all the other params to the max, we'll take any objectid
585 sk
->max_objectid
= (u64
)-1;
586 sk
->max_offset
= (u64
)-1;
587 sk
->max_transid
= (u64
)-1;
589 /* just a big number, doesn't matter much */
593 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
596 fprintf(stderr
, "ERROR: can't perform the search - %s\n",
600 /* the ioctl returns the number of item it found in nr_items */
601 if (sk
->nr_items
== 0)
607 * for each item, pull the key out of the header and then
608 * read the root_ref item it contains
610 for (i
= 0; i
< sk
->nr_items
; i
++) {
611 sh
= (struct btrfs_ioctl_search_header
*)(args
.buf
+
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
);
620 add_root(&root_lookup
, sh
->objectid
, sh
->offset
,
621 dir_id
, name
, name_len
);
627 * record the mins in sk so we can make sure the
628 * next search doesn't repeat this root
630 sk
->min_objectid
= sh
->objectid
;
631 sk
->min_type
= sh
->type
;
632 sk
->min_offset
= sh
->offset
;
635 /* this iteration is done, step forward one root for the next
638 if (sk
->min_objectid
< (u64
)-1) {
640 sk
->min_type
= BTRFS_ROOT_BACKREF_KEY
;
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.
649 n
= rb_first(&root_lookup
.root
);
651 struct root_info
*entry
;
653 entry
= rb_entry(n
, struct root_info
, rb_node
);
654 ret
= lookup_ino_path(fd
, entry
);
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
664 n
= rb_last(&root_lookup
.root
);
666 struct root_info
*entry
;
667 entry
= rb_entry(n
, struct root_info
, rb_node
);
668 resolve_root(&root_lookup
, entry
);
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
)
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
;
696 name
= ino_resolve(fd
, sh
->objectid
, cache_dirid
,
698 *cache_full_name
= name
;
699 *cache_ino
= sh
->objectid
;
704 type
= btrfs_stack_file_extent_type(item
);
705 compressed
= btrfs_stack_file_extent_compression(item
);
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
) {
715 len
= btrfs_stack_file_extent_ram_bytes(item
);
717 printf("unhandled extent type %d for inode %llu "
718 "file offset %llu gen %llu\n",
720 (unsigned long long)sh
->objectid
,
721 (unsigned long long)sh
->offset
,
722 (unsigned long long)found_gen
);
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
);
739 if (type
== BTRFS_FILE_EXTENT_PREALLOC
) {
740 printf("%sPREALLOC", flags
? "|" : "");
743 if (type
== BTRFS_FILE_EXTENT_INLINE
) {
744 printf("%sINLINE", flags
? "|" : "");
750 printf(" %s\n", name
);
754 int find_updated_files(int fd
, u64 root_id
, u64 oldest_gen
)
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;
768 char *cache_dir_name
= NULL
;
769 char *cache_full_name
= NULL
;
770 struct btrfs_file_extent_item backup
;
772 memset(&backup
, 0, sizeof(backup
));
773 memset(&args
, 0, sizeof(args
));
775 sk
->tree_id
= root_id
;
778 * set all the other params to the max, we'll take any objectid
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 */
789 max_found
= find_root_gen(fd
);
791 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
794 fprintf(stderr
, "ERROR: can't perform the search- %s\n",
798 /* the ioctl returns the number of item it found in nr_items */
799 if (sk
->nr_items
== 0)
805 * for each item, pull the key out of the header and then
806 * read the root_ref item it contains
808 for (i
= 0; i
< sk
->nr_items
; i
++) {
809 sh
= (struct btrfs_ioctl_search_header
*)(args
.buf
+
814 * just in case the item was too big, pass something other
820 item
= (struct btrfs_file_extent_item
*)(args
.buf
+
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
);
832 * record the mins in sk so we can make sure the
833 * next search doesn't repeat this root
835 sk
->min_objectid
= sh
->objectid
;
836 sk
->min_offset
= sh
->offset
;
837 sk
->min_type
= sh
->type
;
840 if (sk
->min_offset
< (u64
)-1)
842 else if (sk
->min_objectid
< (u64
)-1) {
849 free(cache_dir_name
);
850 free(cache_full_name
);
851 printf("transid marker was %llu\n", (unsigned long long)max_found
);