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"
38 /* we store all the roots we find in an rbtree so that we can
39 * search for them later.
46 * one of these for each root we find.
49 struct rb_node rb_node
;
54 /* the id of the root that references this one */
57 /* the dir id we're in from ref_tree */
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.
65 /* the name of this root in the directory it lives in */
69 static void root_lookup_init(struct root_lookup
*tree
)
71 tree
->root
.rb_node
= NULL
;
74 static int comp_entry(struct root_info
*entry
, u64 root_id
, u64 ref_tree
)
76 if (entry
->root_id
> root_id
)
78 if (entry
->root_id
< root_id
)
80 if (entry
->ref_tree
> ref_tree
)
82 if (entry
->ref_tree
< ref_tree
)
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
92 static struct rb_node
*tree_insert(struct rb_root
*root
, u64 root_id
,
93 u64 ref_tree
, struct rb_node
*node
)
95 struct rb_node
** p
= &root
->rb_node
;
96 struct rb_node
* parent
= NULL
;
97 struct root_info
*entry
;
102 entry
= rb_entry(parent
, struct root_info
, rb_node
);
104 comp
= comp_entry(entry
, root_id
, ref_tree
);
114 entry
= rb_entry(parent
, struct root_info
, rb_node
);
115 rb_link_node(node
, parent
, p
);
116 rb_insert_color(node
, root
);
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
124 static struct root_info
*tree_search(struct rb_root
*root
, u64 root_id
)
126 struct rb_node
* n
= root
->rb_node
;
127 struct root_info
*entry
;
130 entry
= rb_entry(n
, struct root_info
, rb_node
);
132 if (entry
->root_id
< root_id
)
134 else if (entry
->root_id
> root_id
)
137 struct root_info
*prev
;
138 struct rb_node
*prev_n
;
143 prev
= rb_entry(prev_n
, struct root_info
,
145 if (prev
->root_id
!= root_id
)
157 * this allocates a new root in the lookup tree.
159 * root_id should be the object id of the root
161 * ref_tree is the objectid of the referring root.
163 * dir_id is the directory in ref_tree where this root_id can be found.
165 * name is the name of root_id in that directory
167 * name_len is the length of name
169 static int add_root(struct root_lookup
*root_lookup
,
170 u64 root_id
, u64 ref_tree
, u64 dir_id
, char *name
,
173 struct root_info
*ri
;
175 ri
= malloc(sizeof(*ri
) + name_len
+ 1);
177 printf("memory allocation failed\n");
180 memset(ri
, 0, sizeof(*ri
) + name_len
+ 1);
183 ri
->root_id
= root_id
;
184 ri
->ref_tree
= ref_tree
;
185 strncpy(ri
->name
, name
, name_len
);
187 ri
->name
[name_len
] = 0;
189 ret
= tree_insert(&root_lookup
->root
, root_id
, ref_tree
, &ri
->rb_node
);
191 printf("failed to insert tree %llu\n", (unsigned long long)root_id
);
198 * for a given root_info, search through the root_lookup tree to construct
199 * the full path name to it.
201 * This can't be called until all the root_info->path fields are filled
202 * in by lookup_ino_path
204 static int resolve_root(struct root_lookup
*rl
, struct root_info
*ri
,
205 u64
*parent_id
, u64
*top_id
, char **path
)
207 char *full_path
= NULL
;
209 struct root_info
*found
;
212 * we go backwards from the root_info object and add pathnames
213 * from parent directories as we go.
220 int add_len
= strlen(found
->path
);
222 /* room for / and for null */
223 tmp
= malloc(add_len
+ 2 + len
);
225 memcpy(tmp
+ add_len
+ 1, full_path
, len
);
227 memcpy(tmp
, found
->path
, add_len
);
228 tmp
[add_len
+ len
+ 1] = '\0';
233 full_path
= strdup(found
->path
);
237 next
= found
->ref_tree
;
238 /* record the first parent */
242 /* if the ref_tree refers to ourselves, we're at the top */
243 if (next
== found
->root_id
) {
249 * if the ref_tree wasn't in our tree of roots, we're
252 found
= tree_search(&rl
->root
, next
);
265 * for a single root_info, ask the kernel to give us a path name
266 * inside it's ref_root for the dir_id where it lives.
268 * This fills in root_info->path with the path to the directory and and
269 * appends this root's name.
271 static int lookup_ino_path(int fd
, struct root_info
*ri
)
273 struct btrfs_ioctl_ino_lookup_args args
;
279 memset(&args
, 0, sizeof(args
));
280 args
.treeid
= ri
->ref_tree
;
281 args
.objectid
= ri
->dir_id
;
283 ret
= ioctl(fd
, BTRFS_IOC_INO_LOOKUP
, &args
);
286 fprintf(stderr
, "ERROR: Failed to lookup path for root %llu - %s\n",
287 (unsigned long long)ri
->ref_tree
,
294 * we're in a subdirectory of ref_tree, the kernel ioctl
295 * puts a / in there for us
297 ri
->path
= malloc(strlen(ri
->name
) + strlen(args
.name
) + 1);
299 perror("malloc failed");
302 strcpy(ri
->path
, args
.name
);
303 strcat(ri
->path
, ri
->name
);
305 /* we're at the root of ref_tree */
306 ri
->path
= strdup(ri
->name
);
308 perror("strdup failed");
315 /* finding the generation for a given path is a two step process.
316 * First we use the inode loookup routine to find out the root id
318 * Then we use the tree search ioctl to scan all the root items for a
319 * given root id and spit out the latest generation we can find
321 static u64
find_root_gen(int fd
)
323 struct btrfs_ioctl_ino_lookup_args ino_args
;
325 struct btrfs_ioctl_search_args args
;
326 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
327 struct btrfs_ioctl_search_header
*sh
;
328 unsigned long off
= 0;
333 memset(&ino_args
, 0, sizeof(ino_args
));
334 ino_args
.objectid
= BTRFS_FIRST_FREE_OBJECTID
;
336 /* this ioctl fills in ino_args->treeid */
337 ret
= ioctl(fd
, BTRFS_IOC_INO_LOOKUP
, &ino_args
);
340 fprintf(stderr
, "ERROR: Failed to lookup path for dirid %llu - %s\n",
341 (unsigned long long)BTRFS_FIRST_FREE_OBJECTID
,
346 memset(&args
, 0, sizeof(args
));
351 * there may be more than one ROOT_ITEM key if there are
352 * snapshots pending deletion, we have to loop through
355 sk
->min_objectid
= ino_args
.treeid
;
356 sk
->max_objectid
= ino_args
.treeid
;
357 sk
->max_type
= BTRFS_ROOT_ITEM_KEY
;
358 sk
->min_type
= BTRFS_ROOT_ITEM_KEY
;
359 sk
->max_offset
= (u64
)-1;
360 sk
->max_transid
= (u64
)-1;
364 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
367 fprintf(stderr
, "ERROR: can't perform the search - %s\n",
371 /* the ioctl returns the number of item it found in nr_items */
372 if (sk
->nr_items
== 0)
376 for (i
= 0; i
< sk
->nr_items
; i
++) {
377 struct btrfs_root_item
*item
;
378 sh
= (struct btrfs_ioctl_search_header
*)(args
.buf
+
382 item
= (struct btrfs_root_item
*)(args
.buf
+ off
);
385 sk
->min_objectid
= sh
->objectid
;
386 sk
->min_type
= sh
->type
;
387 sk
->min_offset
= sh
->offset
;
389 if (sh
->objectid
> ino_args
.treeid
)
392 if (sh
->objectid
== ino_args
.treeid
&&
393 sh
->type
== BTRFS_ROOT_ITEM_KEY
) {
394 max_found
= max(max_found
,
395 btrfs_root_generation(item
));
398 if (sk
->min_offset
< (u64
)-1)
403 if (sk
->min_type
!= BTRFS_ROOT_ITEM_KEY
)
405 if (sk
->min_objectid
!= BTRFS_ROOT_ITEM_KEY
)
411 /* pass in a directory id and this will return
412 * the full path of the parent directory inside its
415 * It may return NULL if it is in the root, or an ERR_PTR if things
418 static char *__ino_resolve(int fd
, u64 dirid
)
420 struct btrfs_ioctl_ino_lookup_args args
;
425 memset(&args
, 0, sizeof(args
));
426 args
.objectid
= dirid
;
428 ret
= ioctl(fd
, BTRFS_IOC_INO_LOOKUP
, &args
);
431 fprintf(stderr
, "ERROR: Failed to lookup path for dirid %llu - %s\n",
432 (unsigned long long)dirid
, strerror(e
) );
438 * we're in a subdirectory of ref_tree, the kernel ioctl
439 * puts a / in there for us
441 full
= strdup(args
.name
);
443 perror("malloc failed");
444 return ERR_PTR(-ENOMEM
);
447 /* we're at the root of ref_tree */
454 * simple string builder, returning a new string with both
457 char *build_name(char *dirid
, char *name
)
463 full
= malloc(strlen(dirid
) + strlen(name
) + 1);
472 * given an inode number, this returns the full path name inside the subvolume
473 * to that file/directory. cache_dirid and cache_name are used to
474 * cache the results so we can avoid tree searches if a later call goes
475 * to the same directory or file name
477 static char *ino_resolve(int fd
, u64 ino
, u64
*cache_dirid
, char **cache_name
)
485 struct btrfs_ioctl_search_args args
;
486 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
487 struct btrfs_ioctl_search_header
*sh
;
488 unsigned long off
= 0;
492 memset(&args
, 0, sizeof(args
));
497 * step one, we search for the inode back ref. We just use the first
500 sk
->min_objectid
= ino
;
501 sk
->max_objectid
= ino
;
502 sk
->max_type
= BTRFS_INODE_REF_KEY
;
503 sk
->max_offset
= (u64
)-1;
504 sk
->min_type
= BTRFS_INODE_REF_KEY
;
505 sk
->max_transid
= (u64
)-1;
508 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
511 fprintf(stderr
, "ERROR: can't perform the search - %s\n",
515 /* the ioctl returns the number of item it found in nr_items */
516 if (sk
->nr_items
== 0)
520 sh
= (struct btrfs_ioctl_search_header
*)(args
.buf
+ off
);
522 if (sh
->type
== BTRFS_INODE_REF_KEY
) {
523 struct btrfs_inode_ref
*ref
;
526 ref
= (struct btrfs_inode_ref
*)(sh
+ 1);
527 namelen
= btrfs_stack_inode_ref_name_len(ref
);
529 name
= (char *)(ref
+ 1);
530 name
= strndup(name
, namelen
);
532 /* use our cached value */
533 if (dirid
== *cache_dirid
&& *cache_name
) {
534 dirname
= *cache_name
;
541 * the inode backref gives us the file name and the parent directory id.
542 * From here we use __ino_resolve to get the path to the parent
544 dirname
= __ino_resolve(fd
, dirid
);
546 full
= build_name(dirname
, name
);
547 if (*cache_name
&& dirname
!= *cache_name
)
550 *cache_name
= dirname
;
551 *cache_dirid
= dirid
;
557 static int get_default_subvolid(int fd
, u64
*default_id
)
559 struct btrfs_ioctl_search_args args
;
560 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
561 struct btrfs_ioctl_search_header
*sh
;
565 memset(&args
, 0, sizeof(args
));
568 * search for a dir item with a name 'default' in the tree of
569 * tree roots, it should point us to a default root
573 /* don't worry about ancient format and request only one item */
576 sk
->max_objectid
= BTRFS_ROOT_TREE_DIR_OBJECTID
;
577 sk
->min_objectid
= BTRFS_ROOT_TREE_DIR_OBJECTID
;
578 sk
->max_type
= BTRFS_DIR_ITEM_KEY
;
579 sk
->min_type
= BTRFS_DIR_ITEM_KEY
;
580 sk
->max_offset
= (u64
)-1;
581 sk
->max_transid
= (u64
)-1;
583 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
587 /* the ioctl returns the number of items it found in nr_items */
588 if (sk
->nr_items
== 0)
591 sh
= (struct btrfs_ioctl_search_header
*)args
.buf
;
593 if (sh
->type
== BTRFS_DIR_ITEM_KEY
) {
594 struct btrfs_dir_item
*di
;
598 di
= (struct btrfs_dir_item
*)(sh
+ 1);
599 name_len
= btrfs_stack_dir_name_len(di
);
600 name
= (char *)(di
+ 1);
602 if (!strncmp("default", name
, name_len
))
603 found
= btrfs_disk_key_objectid(&di
->location
);
611 static int __list_subvol_search(int fd
, struct root_lookup
*root_lookup
)
614 struct btrfs_ioctl_search_args args
;
615 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
616 struct btrfs_ioctl_search_header
*sh
;
617 struct btrfs_root_ref
*ref
;
618 unsigned long off
= 0;
624 root_lookup_init(root_lookup
);
625 memset(&args
, 0, sizeof(args
));
627 /* search in the tree of tree roots */
631 * set the min and max to backref keys. The search will
632 * only send back this type of key now.
634 sk
->max_type
= BTRFS_ROOT_BACKREF_KEY
;
635 sk
->min_type
= BTRFS_ROOT_BACKREF_KEY
;
638 * set all the other params to the max, we'll take any objectid
641 sk
->max_objectid
= (u64
)-1;
642 sk
->max_offset
= (u64
)-1;
643 sk
->max_transid
= (u64
)-1;
645 /* just a big number, doesn't matter much */
649 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
652 /* the ioctl returns the number of item it found in nr_items */
653 if (sk
->nr_items
== 0)
659 * for each item, pull the key out of the header and then
660 * read the root_ref item it contains
662 for (i
= 0; i
< sk
->nr_items
; i
++) {
663 sh
= (struct btrfs_ioctl_search_header
*)(args
.buf
+
666 if (sh
->type
== BTRFS_ROOT_BACKREF_KEY
) {
667 ref
= (struct btrfs_root_ref
*)(args
.buf
+ off
);
668 name_len
= btrfs_stack_root_ref_name_len(ref
);
669 name
= (char *)(ref
+ 1);
670 dir_id
= btrfs_stack_root_ref_dirid(ref
);
672 add_root(root_lookup
, sh
->objectid
, sh
->offset
,
673 dir_id
, name
, name_len
);
679 * record the mins in sk so we can make sure the
680 * next search doesn't repeat this root
682 sk
->min_objectid
= sh
->objectid
;
683 sk
->min_type
= sh
->type
;
684 sk
->min_offset
= sh
->offset
;
687 /* this iteration is done, step forward one root for the next
690 if (sk
->min_type
< BTRFS_ROOT_BACKREF_KEY
) {
691 sk
->min_type
= BTRFS_ROOT_BACKREF_KEY
;
693 } else if (sk
->min_objectid
< (u64
)-1) {
695 sk
->min_type
= BTRFS_ROOT_BACKREF_KEY
;
704 static int __list_subvol_fill_paths(int fd
, struct root_lookup
*root_lookup
)
708 n
= rb_first(&root_lookup
->root
);
710 struct root_info
*entry
;
712 entry
= rb_entry(n
, struct root_info
, rb_node
);
713 ret
= lookup_ino_path(fd
, entry
);
722 int list_subvols(int fd
, int print_parent
, int get_default
)
724 struct root_lookup root_lookup
;
730 ret
= get_default_subvolid(fd
, &default_id
);
732 fprintf(stderr
, "ERROR: can't perform the search - %s\n",
736 if (default_id
== 0) {
737 fprintf(stderr
, "ERROR: 'default' dir item not found\n");
741 /* no need to resolve roots if FS_TREE is default */
742 if (default_id
== BTRFS_FS_TREE_OBJECTID
) {
743 printf("ID 5 (FS_TREE)\n");
748 ret
= __list_subvol_search(fd
, &root_lookup
);
750 fprintf(stderr
, "ERROR: can't perform the search - %s\n",
756 * now we have an rbtree full of root_info objects, but we need to fill
757 * in their path names within the subvol that is referencing each one.
759 ret
= __list_subvol_fill_paths(fd
, &root_lookup
);
763 /* now that we have all the subvol-relative paths filled in,
764 * we have to string the subvols together so that we can get
765 * a path all the way back to the FS root
767 n
= rb_last(&root_lookup
.root
);
769 struct root_info
*entry
;
774 entry
= rb_entry(n
, struct root_info
, rb_node
);
775 if (get_default
&& entry
->root_id
!= default_id
) {
780 resolve_root(&root_lookup
, entry
, &parent_id
, &level
, &path
);
782 printf("ID %llu parent %llu top level %llu path %s\n",
783 (unsigned long long)entry
->root_id
,
784 (unsigned long long)parent_id
,
785 (unsigned long long)level
, path
);
787 printf("ID %llu top level %llu path %s\n",
788 (unsigned long long)entry
->root_id
,
789 (unsigned long long)level
, path
);
799 static int print_one_extent(int fd
, struct btrfs_ioctl_search_header
*sh
,
800 struct btrfs_file_extent_item
*item
,
801 u64 found_gen
, u64
*cache_dirid
,
802 char **cache_dir_name
, u64
*cache_ino
,
803 char **cache_full_name
)
813 if (sh
->objectid
== *cache_ino
) {
814 name
= *cache_full_name
;
815 } else if (*cache_full_name
) {
816 free(*cache_full_name
);
817 *cache_full_name
= NULL
;
820 name
= ino_resolve(fd
, sh
->objectid
, cache_dirid
,
822 *cache_full_name
= name
;
823 *cache_ino
= sh
->objectid
;
828 type
= btrfs_stack_file_extent_type(item
);
829 compressed
= btrfs_stack_file_extent_compression(item
);
831 if (type
== BTRFS_FILE_EXTENT_REG
||
832 type
== BTRFS_FILE_EXTENT_PREALLOC
) {
833 disk_start
= btrfs_stack_file_extent_disk_bytenr(item
);
834 disk_offset
= btrfs_stack_file_extent_offset(item
);
835 len
= btrfs_stack_file_extent_num_bytes(item
);
836 } else if (type
== BTRFS_FILE_EXTENT_INLINE
) {
839 len
= btrfs_stack_file_extent_ram_bytes(item
);
841 printf("unhandled extent type %d for inode %llu "
842 "file offset %llu gen %llu\n",
844 (unsigned long long)sh
->objectid
,
845 (unsigned long long)sh
->offset
,
846 (unsigned long long)found_gen
);
850 printf("inode %llu file offset %llu len %llu disk start %llu "
851 "offset %llu gen %llu flags ",
852 (unsigned long long)sh
->objectid
,
853 (unsigned long long)sh
->offset
,
854 (unsigned long long)len
,
855 (unsigned long long)disk_start
,
856 (unsigned long long)disk_offset
,
857 (unsigned long long)found_gen
);
863 if (type
== BTRFS_FILE_EXTENT_PREALLOC
) {
864 printf("%sPREALLOC", flags
? "|" : "");
867 if (type
== BTRFS_FILE_EXTENT_INLINE
) {
868 printf("%sINLINE", flags
? "|" : "");
874 printf(" %s\n", name
);
878 int find_updated_files(int fd
, u64 root_id
, u64 oldest_gen
)
881 struct btrfs_ioctl_search_args args
;
882 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
883 struct btrfs_ioctl_search_header
*sh
;
884 struct btrfs_file_extent_item
*item
;
885 unsigned long off
= 0;
892 char *cache_dir_name
= NULL
;
893 char *cache_full_name
= NULL
;
894 struct btrfs_file_extent_item backup
;
896 memset(&backup
, 0, sizeof(backup
));
897 memset(&args
, 0, sizeof(args
));
899 sk
->tree_id
= root_id
;
902 * set all the other params to the max, we'll take any objectid
905 sk
->max_objectid
= (u64
)-1;
906 sk
->max_offset
= (u64
)-1;
907 sk
->max_transid
= (u64
)-1;
908 sk
->max_type
= BTRFS_EXTENT_DATA_KEY
;
909 sk
->min_transid
= oldest_gen
;
910 /* just a big number, doesn't matter much */
913 max_found
= find_root_gen(fd
);
915 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
918 fprintf(stderr
, "ERROR: can't perform the search- %s\n",
922 /* the ioctl returns the number of item it found in nr_items */
923 if (sk
->nr_items
== 0)
929 * for each item, pull the key out of the header and then
930 * read the root_ref item it contains
932 for (i
= 0; i
< sk
->nr_items
; i
++) {
933 sh
= (struct btrfs_ioctl_search_header
*)(args
.buf
+
938 * just in case the item was too big, pass something other
944 item
= (struct btrfs_file_extent_item
*)(args
.buf
+
946 found_gen
= btrfs_stack_file_extent_generation(item
);
947 if (sh
->type
== BTRFS_EXTENT_DATA_KEY
&&
948 found_gen
>= oldest_gen
) {
949 print_one_extent(fd
, sh
, item
, found_gen
,
950 &cache_dirid
, &cache_dir_name
,
951 &cache_ino
, &cache_full_name
);
956 * record the mins in sk so we can make sure the
957 * next search doesn't repeat this root
959 sk
->min_objectid
= sh
->objectid
;
960 sk
->min_offset
= sh
->offset
;
961 sk
->min_type
= sh
->type
;
964 if (sk
->min_offset
< (u64
)-1)
966 else if (sk
->min_objectid
< (u64
)-1) {
973 free(cache_dir_name
);
974 free(cache_full_name
);
975 printf("transid marker was %llu\n", (unsigned long long)max_found
);
979 char *path_for_root(int fd
, u64 root
)
981 struct root_lookup root_lookup
;
983 char *ret_path
= NULL
;
986 ret
= __list_subvol_search(fd
, &root_lookup
);
990 ret
= __list_subvol_fill_paths(fd
, &root_lookup
);
994 n
= rb_last(&root_lookup
.root
);
996 struct root_info
*entry
;
1001 entry
= rb_entry(n
, struct root_info
, rb_node
);
1002 resolve_root(&root_lookup
, entry
, &parent_id
, &level
, &path
);
1003 if (entry
->root_id
== root
)