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 ret
= tree_insert(&root_lookup
->root
, root_id
, ref_tree
, &ri
->rb_node
);
189 printf("failed to insert tree %llu\n", (unsigned long long)root_id
);
196 * for a given root_info, search through the root_lookup tree to construct
197 * the full path name to it.
199 * This can't be called until all the root_info->path fields are filled
200 * in by lookup_ino_path
202 static int resolve_root(struct root_lookup
*rl
, struct root_info
*ri
,
203 u64
*root_id
, u64
*parent_id
, u64
*top_id
, char **path
)
205 char *full_path
= NULL
;
207 struct root_info
*found
;
210 * we go backwards from the root_info object and add pathnames
211 * 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 /* record the first parent */
240 /* if the ref_tree refers to ourselves, we're at the top */
241 if (next
== found
->root_id
) {
247 * if the ref_tree wasn't in our tree of roots, we're
250 found
= tree_search(&rl
->root
, next
);
257 *root_id
= ri
->root_id
;
264 * for a single root_info, ask the kernel to give us a path name
265 * inside it's ref_root for the dir_id where it lives.
267 * This fills in root_info->path with the path to the directory and and
268 * appends this root's name.
270 static int lookup_ino_path(int fd
, struct root_info
*ri
)
272 struct btrfs_ioctl_ino_lookup_args args
;
278 memset(&args
, 0, sizeof(args
));
279 args
.treeid
= ri
->ref_tree
;
280 args
.objectid
= ri
->dir_id
;
282 ret
= ioctl(fd
, BTRFS_IOC_INO_LOOKUP
, &args
);
285 fprintf(stderr
, "ERROR: Failed to lookup path for root %llu - %s\n",
286 (unsigned long long)ri
->ref_tree
,
293 * we're in a subdirectory of ref_tree, the kernel ioctl
294 * puts a / in there for us
296 ri
->path
= malloc(strlen(ri
->name
) + strlen(args
.name
) + 1);
298 perror("malloc failed");
301 strcpy(ri
->path
, args
.name
);
302 strcat(ri
->path
, ri
->name
);
304 /* we're at the root of ref_tree */
305 ri
->path
= strdup(ri
->name
);
307 perror("strdup failed");
314 /* finding the generation for a given path is a two step process.
315 * First we use the inode loookup routine to find out the root id
317 * Then we use the tree search ioctl to scan all the root items for a
318 * given root id and spit out the latest generation we can find
320 static u64
find_root_gen(int fd
)
322 struct btrfs_ioctl_ino_lookup_args ino_args
;
324 struct btrfs_ioctl_search_args args
;
325 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
326 struct btrfs_ioctl_search_header
*sh
;
327 unsigned long off
= 0;
332 memset(&ino_args
, 0, sizeof(ino_args
));
333 ino_args
.objectid
= BTRFS_FIRST_FREE_OBJECTID
;
335 /* this ioctl fills in ino_args->treeid */
336 ret
= ioctl(fd
, BTRFS_IOC_INO_LOOKUP
, &ino_args
);
339 fprintf(stderr
, "ERROR: Failed to lookup path for dirid %llu - %s\n",
340 (unsigned long long)BTRFS_FIRST_FREE_OBJECTID
,
345 memset(&args
, 0, sizeof(args
));
350 * there may be more than one ROOT_ITEM key if there are
351 * snapshots pending deletion, we have to loop through
354 sk
->min_objectid
= ino_args
.treeid
;
355 sk
->max_objectid
= ino_args
.treeid
;
356 sk
->max_type
= BTRFS_ROOT_ITEM_KEY
;
357 sk
->min_type
= BTRFS_ROOT_ITEM_KEY
;
358 sk
->max_offset
= (u64
)-1;
359 sk
->max_transid
= (u64
)-1;
363 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
366 fprintf(stderr
, "ERROR: can't perform the search - %s\n",
370 /* the ioctl returns the number of item it found in nr_items */
371 if (sk
->nr_items
== 0)
375 for (i
= 0; i
< sk
->nr_items
; i
++) {
376 struct btrfs_root_item
*item
;
377 sh
= (struct btrfs_ioctl_search_header
*)(args
.buf
+
381 item
= (struct btrfs_root_item
*)(args
.buf
+ off
);
384 sk
->min_objectid
= sh
->objectid
;
385 sk
->min_type
= sh
->type
;
386 sk
->min_offset
= sh
->offset
;
388 if (sh
->objectid
> ino_args
.treeid
)
391 if (sh
->objectid
== ino_args
.treeid
&&
392 sh
->type
== BTRFS_ROOT_ITEM_KEY
) {
393 max_found
= max(max_found
,
394 btrfs_root_generation(item
));
397 if (sk
->min_offset
< (u64
)-1)
402 if (sk
->min_type
!= BTRFS_ROOT_ITEM_KEY
)
404 if (sk
->min_objectid
!= BTRFS_ROOT_ITEM_KEY
)
410 /* pass in a directory id and this will return
411 * the full path of the parent directory inside its
414 * It may return NULL if it is in the root, or an ERR_PTR if things
417 static char *__ino_resolve(int fd
, u64 dirid
)
419 struct btrfs_ioctl_ino_lookup_args args
;
424 memset(&args
, 0, sizeof(args
));
425 args
.objectid
= dirid
;
427 ret
= ioctl(fd
, BTRFS_IOC_INO_LOOKUP
, &args
);
430 fprintf(stderr
, "ERROR: Failed to lookup path for dirid %llu - %s\n",
431 (unsigned long long)dirid
, strerror(e
) );
437 * we're in a subdirectory of ref_tree, the kernel ioctl
438 * puts a / in there for us
440 full
= strdup(args
.name
);
442 perror("malloc failed");
443 return ERR_PTR(-ENOMEM
);
446 /* we're at the root of ref_tree */
453 * simple string builder, returning a new string with both
456 char *build_name(char *dirid
, char *name
)
462 full
= malloc(strlen(dirid
) + strlen(name
) + 1);
471 * given an inode number, this returns the full path name inside the subvolume
472 * to that file/directory. cache_dirid and cache_name are used to
473 * cache the results so we can avoid tree searches if a later call goes
474 * to the same directory or file name
476 static char *ino_resolve(int fd
, u64 ino
, u64
*cache_dirid
, char **cache_name
)
484 struct btrfs_ioctl_search_args args
;
485 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
486 struct btrfs_ioctl_search_header
*sh
;
487 unsigned long off
= 0;
491 memset(&args
, 0, sizeof(args
));
496 * step one, we search for the inode back ref. We just use the first
499 sk
->min_objectid
= ino
;
500 sk
->max_objectid
= ino
;
501 sk
->max_type
= BTRFS_INODE_REF_KEY
;
502 sk
->max_offset
= (u64
)-1;
503 sk
->min_type
= BTRFS_INODE_REF_KEY
;
504 sk
->max_transid
= (u64
)-1;
507 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
510 fprintf(stderr
, "ERROR: can't perform the search - %s\n",
514 /* the ioctl returns the number of item it found in nr_items */
515 if (sk
->nr_items
== 0)
519 sh
= (struct btrfs_ioctl_search_header
*)(args
.buf
+ off
);
521 if (sh
->type
== BTRFS_INODE_REF_KEY
) {
522 struct btrfs_inode_ref
*ref
;
525 ref
= (struct btrfs_inode_ref
*)(sh
+ 1);
526 namelen
= btrfs_stack_inode_ref_name_len(ref
);
528 name
= (char *)(ref
+ 1);
529 name
= strndup(name
, namelen
);
531 /* use our cached value */
532 if (dirid
== *cache_dirid
&& *cache_name
) {
533 dirname
= *cache_name
;
540 * the inode backref gives us the file name and the parent directory id.
541 * From here we use __ino_resolve to get the path to the parent
543 dirname
= __ino_resolve(fd
, dirid
);
545 full
= build_name(dirname
, name
);
546 if (*cache_name
&& dirname
!= *cache_name
)
549 *cache_name
= dirname
;
550 *cache_dirid
= dirid
;
556 static int __list_subvol_search(int fd
, struct root_lookup
*root_lookup
)
559 struct btrfs_ioctl_search_args args
;
560 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
561 struct btrfs_ioctl_search_header
*sh
;
562 struct btrfs_root_ref
*ref
;
563 unsigned long off
= 0;
569 root_lookup_init(root_lookup
);
570 memset(&args
, 0, sizeof(args
));
572 root_lookup_init(root_lookup
);
574 memset(&args
, 0, sizeof(args
));
576 /* search in the tree of tree roots */
580 * set the min and max to backref keys. The search will
581 * only send back this type of key now.
583 sk
->max_type
= BTRFS_ROOT_BACKREF_KEY
;
584 sk
->min_type
= BTRFS_ROOT_BACKREF_KEY
;
587 * set all the other params to the max, we'll take any objectid
590 sk
->max_objectid
= (u64
)-1;
591 sk
->max_offset
= (u64
)-1;
592 sk
->max_transid
= (u64
)-1;
594 /* just a big number, doesn't matter much */
598 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
601 /* the ioctl returns the number of item it found in nr_items */
602 if (sk
->nr_items
== 0)
608 * for each item, pull the key out of the header and then
609 * read the root_ref item it contains
611 for (i
= 0; i
< sk
->nr_items
; i
++) {
612 sh
= (struct btrfs_ioctl_search_header
*)(args
.buf
+
615 if (sh
->type
== BTRFS_ROOT_BACKREF_KEY
) {
616 ref
= (struct btrfs_root_ref
*)(args
.buf
+ off
);
617 name_len
= btrfs_stack_root_ref_name_len(ref
);
618 name
= (char *)(ref
+ 1);
619 dir_id
= btrfs_stack_root_ref_dirid(ref
);
621 add_root(root_lookup
, sh
->objectid
, sh
->offset
,
622 dir_id
, name
, name_len
);
628 * record the mins in sk so we can make sure the
629 * next search doesn't repeat this root
631 sk
->min_objectid
= sh
->objectid
;
632 sk
->min_type
= sh
->type
;
633 sk
->min_offset
= sh
->offset
;
636 /* this iteration is done, step forward one root for the next
639 if (sk
->min_type
< BTRFS_ROOT_BACKREF_KEY
) {
640 sk
->min_type
= BTRFS_ROOT_BACKREF_KEY
;
642 } else if (sk
->min_objectid
< (u64
)-1) {
644 sk
->min_type
= BTRFS_ROOT_BACKREF_KEY
;
653 static int __list_subvol_fill_paths(int fd
, struct root_lookup
*root_lookup
)
657 n
= rb_first(&root_lookup
->root
);
659 struct root_info
*entry
;
661 entry
= rb_entry(n
, struct root_info
, rb_node
);
662 ret
= lookup_ino_path(fd
, entry
);
671 int list_subvols(int fd
, int print_parent
)
673 struct root_lookup root_lookup
;
677 ret
= __list_subvol_search(fd
, &root_lookup
);
679 fprintf(stderr
, "ERROR: can't perform the search - %s\n",
685 * now we have an rbtree full of root_info objects, but we need to fill
686 * in their path names within the subvol that is referencing each one.
688 ret
= __list_subvol_fill_paths(fd
, &root_lookup
);
692 /* now that we have all the subvol-relative paths filled in,
693 * we have to string the subvols together so that we can get
694 * a path all the way back to the FS root
696 n
= rb_last(&root_lookup
.root
);
698 struct root_info
*entry
;
703 entry
= rb_entry(n
, struct root_info
, rb_node
);
704 resolve_root(&root_lookup
, entry
, &root_id
, &parent_id
,
707 printf("ID %llu parent %llu top level %llu path %s\n",
708 (unsigned long long)root_id
,
709 (unsigned long long)parent_id
,
710 (unsigned long long)level
, path
);
712 printf("ID %llu top level %llu path %s\n",
713 (unsigned long long)root_id
,
714 (unsigned long long)level
, path
);
723 static int print_one_extent(int fd
, struct btrfs_ioctl_search_header
*sh
,
724 struct btrfs_file_extent_item
*item
,
725 u64 found_gen
, u64
*cache_dirid
,
726 char **cache_dir_name
, u64
*cache_ino
,
727 char **cache_full_name
)
737 if (sh
->objectid
== *cache_ino
) {
738 name
= *cache_full_name
;
739 } else if (*cache_full_name
) {
740 free(*cache_full_name
);
741 *cache_full_name
= NULL
;
744 name
= ino_resolve(fd
, sh
->objectid
, cache_dirid
,
746 *cache_full_name
= name
;
747 *cache_ino
= sh
->objectid
;
752 type
= btrfs_stack_file_extent_type(item
);
753 compressed
= btrfs_stack_file_extent_compression(item
);
755 if (type
== BTRFS_FILE_EXTENT_REG
||
756 type
== BTRFS_FILE_EXTENT_PREALLOC
) {
757 disk_start
= btrfs_stack_file_extent_disk_bytenr(item
);
758 disk_offset
= btrfs_stack_file_extent_offset(item
);
759 len
= btrfs_stack_file_extent_num_bytes(item
);
760 } else if (type
== BTRFS_FILE_EXTENT_INLINE
) {
763 len
= btrfs_stack_file_extent_ram_bytes(item
);
765 printf("unhandled extent type %d for inode %llu "
766 "file offset %llu gen %llu\n",
768 (unsigned long long)sh
->objectid
,
769 (unsigned long long)sh
->offset
,
770 (unsigned long long)found_gen
);
774 printf("inode %llu file offset %llu len %llu disk start %llu "
775 "offset %llu gen %llu flags ",
776 (unsigned long long)sh
->objectid
,
777 (unsigned long long)sh
->offset
,
778 (unsigned long long)len
,
779 (unsigned long long)disk_start
,
780 (unsigned long long)disk_offset
,
781 (unsigned long long)found_gen
);
787 if (type
== BTRFS_FILE_EXTENT_PREALLOC
) {
788 printf("%sPREALLOC", flags
? "|" : "");
791 if (type
== BTRFS_FILE_EXTENT_INLINE
) {
792 printf("%sINLINE", flags
? "|" : "");
798 printf(" %s\n", name
);
802 int find_updated_files(int fd
, u64 root_id
, u64 oldest_gen
)
805 struct btrfs_ioctl_search_args args
;
806 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
807 struct btrfs_ioctl_search_header
*sh
;
808 struct btrfs_file_extent_item
*item
;
809 unsigned long off
= 0;
816 char *cache_dir_name
= NULL
;
817 char *cache_full_name
= NULL
;
818 struct btrfs_file_extent_item backup
;
820 memset(&backup
, 0, sizeof(backup
));
821 memset(&args
, 0, sizeof(args
));
823 sk
->tree_id
= root_id
;
826 * set all the other params to the max, we'll take any objectid
829 sk
->max_objectid
= (u64
)-1;
830 sk
->max_offset
= (u64
)-1;
831 sk
->max_transid
= (u64
)-1;
832 sk
->max_type
= BTRFS_EXTENT_DATA_KEY
;
833 sk
->min_transid
= oldest_gen
;
834 /* just a big number, doesn't matter much */
837 max_found
= find_root_gen(fd
);
839 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
842 fprintf(stderr
, "ERROR: can't perform the search- %s\n",
846 /* the ioctl returns the number of item it found in nr_items */
847 if (sk
->nr_items
== 0)
853 * for each item, pull the key out of the header and then
854 * read the root_ref item it contains
856 for (i
= 0; i
< sk
->nr_items
; i
++) {
857 sh
= (struct btrfs_ioctl_search_header
*)(args
.buf
+
862 * just in case the item was too big, pass something other
868 item
= (struct btrfs_file_extent_item
*)(args
.buf
+
870 found_gen
= btrfs_stack_file_extent_generation(item
);
871 if (sh
->type
== BTRFS_EXTENT_DATA_KEY
&&
872 found_gen
>= oldest_gen
) {
873 print_one_extent(fd
, sh
, item
, found_gen
,
874 &cache_dirid
, &cache_dir_name
,
875 &cache_ino
, &cache_full_name
);
880 * record the mins in sk so we can make sure the
881 * next search doesn't repeat this root
883 sk
->min_objectid
= sh
->objectid
;
884 sk
->min_offset
= sh
->offset
;
885 sk
->min_type
= sh
->type
;
888 if (sk
->min_offset
< (u64
)-1)
890 else if (sk
->min_objectid
< (u64
)-1) {
897 free(cache_dir_name
);
898 free(cache_full_name
);
899 printf("transid marker was %llu\n", (unsigned long long)max_found
);
903 char *path_for_root(int fd
, u64 root
)
905 struct root_lookup root_lookup
;
907 char *ret_path
= NULL
;
910 ret
= __list_subvol_search(fd
, &root_lookup
);
914 ret
= __list_subvol_fill_paths(fd
, &root_lookup
);
918 n
= rb_last(&root_lookup
.root
);
920 struct root_info
*entry
;
925 entry
= rb_entry(n
, struct root_info
, rb_node
);
926 resolve_root(&root_lookup
, entry
, &root_id
, &parent_id
, &level
,