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.
19 #include <sys/ioctl.h>
20 #include <sys/mount.h>
23 #include <sys/types.h>
30 #include "transaction.h"
33 #include <uuid/uuid.h>
34 #include "btrfs-list.h"
35 #include "rbtree-utils.h"
37 #define BTRFS_LIST_NFILTERS_INCREASE (2 * BTRFS_LIST_FILTER_MAX)
38 #define BTRFS_LIST_NCOMPS_INCREASE (2 * BTRFS_LIST_COMP_MAX)
40 /* we store all the roots we find in an rbtree so that we can
41 * search for them later.
51 } btrfs_list_columns
[] = {
64 .column_name
= "CGen",
69 .column_name
= "Parent",
74 .column_name
= "Top Level",
79 .column_name
= "OTime",
83 .name
= "parent_uuid",
84 .column_name
= "Parent UUID",
88 .name
= "received_uuid",
89 .column_name
= "Received UUID",
94 .column_name
= "UUID",
99 .column_name
= "Path",
109 static btrfs_list_filter_func all_filter_funcs
[];
110 static btrfs_list_comp_func all_comp_funcs
[];
112 void btrfs_list_setup_print_column(enum btrfs_list_column_enum column
)
116 BUG_ON(column
< 0 || column
> BTRFS_LIST_ALL
);
118 if (column
< BTRFS_LIST_ALL
) {
119 btrfs_list_columns
[column
].need_print
= 1;
123 for (i
= 0; i
< BTRFS_LIST_ALL
; i
++)
124 btrfs_list_columns
[i
].need_print
= 1;
127 static void root_lookup_init(struct root_lookup
*tree
)
129 tree
->root
.rb_node
= NULL
;
132 static int comp_entry_with_rootid(struct root_info
*entry1
,
133 struct root_info
*entry2
,
138 if (entry1
->root_id
> entry2
->root_id
)
140 else if (entry1
->root_id
< entry2
->root_id
)
145 return is_descending
? -ret
: ret
;
148 static int comp_entry_with_gen(struct root_info
*entry1
,
149 struct root_info
*entry2
,
154 if (entry1
->gen
> entry2
->gen
)
156 else if (entry1
->gen
< entry2
->gen
)
161 return is_descending
? -ret
: ret
;
164 static int comp_entry_with_ogen(struct root_info
*entry1
,
165 struct root_info
*entry2
,
170 if (entry1
->ogen
> entry2
->ogen
)
172 else if (entry1
->ogen
< entry2
->ogen
)
177 return is_descending
? -ret
: ret
;
180 static int comp_entry_with_path(struct root_info
*entry1
,
181 struct root_info
*entry2
,
186 if (strcmp(entry1
->full_path
, entry2
->full_path
) > 0)
188 else if (strcmp(entry1
->full_path
, entry2
->full_path
) < 0)
193 return is_descending
? -ret
: ret
;
196 static btrfs_list_comp_func all_comp_funcs
[] = {
197 [BTRFS_LIST_COMP_ROOTID
] = comp_entry_with_rootid
,
198 [BTRFS_LIST_COMP_OGEN
] = comp_entry_with_ogen
,
199 [BTRFS_LIST_COMP_GEN
] = comp_entry_with_gen
,
200 [BTRFS_LIST_COMP_PATH
] = comp_entry_with_path
,
203 static char *all_sort_items
[] = {
204 [BTRFS_LIST_COMP_ROOTID
] = "rootid",
205 [BTRFS_LIST_COMP_OGEN
] = "ogen",
206 [BTRFS_LIST_COMP_GEN
] = "gen",
207 [BTRFS_LIST_COMP_PATH
] = "path",
208 [BTRFS_LIST_COMP_MAX
] = NULL
,
211 static int btrfs_list_get_sort_item(char *sort_name
)
215 for (i
= 0; i
< BTRFS_LIST_COMP_MAX
; i
++) {
216 if (strcmp(sort_name
, all_sort_items
[i
]) == 0)
222 struct btrfs_list_comparer_set
*btrfs_list_alloc_comparer_set(void)
224 struct btrfs_list_comparer_set
*set
;
227 size
= sizeof(struct btrfs_list_comparer_set
) +
228 BTRFS_LIST_NCOMPS_INCREASE
* sizeof(struct btrfs_list_comparer
);
231 fprintf(stderr
, "memory allocation failed\n");
235 memset(set
, 0, size
);
236 set
->total
= BTRFS_LIST_NCOMPS_INCREASE
;
241 void btrfs_list_free_comparer_set(struct btrfs_list_comparer_set
*comp_set
)
246 static int btrfs_list_setup_comparer(struct btrfs_list_comparer_set
**comp_set
,
247 enum btrfs_list_comp_enum comparer
, int is_descending
)
249 struct btrfs_list_comparer_set
*set
= *comp_set
;
253 BUG_ON(comparer
>= BTRFS_LIST_COMP_MAX
);
254 BUG_ON(set
->ncomps
> set
->total
);
256 if (set
->ncomps
== set
->total
) {
259 size
= set
->total
+ BTRFS_LIST_NCOMPS_INCREASE
;
260 size
= sizeof(*set
) + size
* sizeof(struct btrfs_list_comparer
);
262 set
= realloc(set
, size
);
264 fprintf(stderr
, "memory allocation failed\n");
269 memset(&set
->comps
[set
->total
], 0,
270 BTRFS_LIST_NCOMPS_INCREASE
*
271 sizeof(struct btrfs_list_comparer
));
272 set
->total
+= BTRFS_LIST_NCOMPS_INCREASE
;
276 BUG_ON(set
->comps
[set
->ncomps
].comp_func
);
278 set
->comps
[set
->ncomps
].comp_func
= all_comp_funcs
[comparer
];
279 set
->comps
[set
->ncomps
].is_descending
= is_descending
;
284 static int sort_comp(struct root_info
*entry1
, struct root_info
*entry2
,
285 struct btrfs_list_comparer_set
*set
)
287 int rootid_compared
= 0;
290 if (!set
|| !set
->ncomps
)
293 for (i
= 0; i
< set
->ncomps
; i
++) {
294 if (!set
->comps
[i
].comp_func
)
297 ret
= set
->comps
[i
].comp_func(entry1
, entry2
,
298 set
->comps
[i
].is_descending
);
302 if (set
->comps
[i
].comp_func
== comp_entry_with_rootid
)
306 if (!rootid_compared
) {
308 ret
= comp_entry_with_rootid(entry1
, entry2
, 0);
314 static int sort_tree_insert(struct root_lookup
*sort_tree
,
315 struct root_info
*ins
,
316 struct btrfs_list_comparer_set
*comp_set
)
318 struct rb_node
**p
= &sort_tree
->root
.rb_node
;
319 struct rb_node
*parent
= NULL
;
320 struct root_info
*curr
;
325 curr
= rb_entry(parent
, struct root_info
, sort_node
);
327 ret
= sort_comp(ins
, curr
, comp_set
);
336 rb_link_node(&ins
->sort_node
, parent
, p
);
337 rb_insert_color(&ins
->sort_node
, &sort_tree
->root
);
342 * insert a new root into the tree. returns the existing root entry
343 * if one is already there. Both root_id and ref_tree are used
346 static int root_tree_insert(struct root_lookup
*root_tree
,
347 struct root_info
*ins
)
349 struct rb_node
**p
= &root_tree
->root
.rb_node
;
350 struct rb_node
* parent
= NULL
;
351 struct root_info
*curr
;
356 curr
= rb_entry(parent
, struct root_info
, rb_node
);
358 ret
= comp_entry_with_rootid(ins
, curr
, 0);
367 rb_link_node(&ins
->rb_node
, parent
, p
);
368 rb_insert_color(&ins
->rb_node
, &root_tree
->root
);
373 * find a given root id in the tree. We return the smallest one,
374 * rb_next can be used to move forward looking for more if required
376 static struct root_info
*root_tree_search(struct root_lookup
*root_tree
,
379 struct rb_node
*n
= root_tree
->root
.rb_node
;
380 struct root_info
*entry
;
381 struct root_info tmp
;
384 tmp
.root_id
= root_id
;
387 entry
= rb_entry(n
, struct root_info
, rb_node
);
389 ret
= comp_entry_with_rootid(&tmp
, entry
, 0);
400 static int update_root(struct root_lookup
*root_lookup
,
401 u64 root_id
, u64 ref_tree
, u64 root_offset
, u64 flags
,
402 u64 dir_id
, char *name
, int name_len
, u64 ogen
, u64 gen
,
403 time_t ot
, void *uuid
, void *puuid
, void *ruuid
)
405 struct root_info
*ri
;
407 ri
= root_tree_search(root_lookup
, root_id
);
408 if (!ri
|| ri
->root_id
!= root_id
)
410 if (name
&& name_len
> 0) {
413 ri
->name
= malloc(name_len
+ 1);
415 fprintf(stderr
, "memory allocation failed\n");
418 strncpy(ri
->name
, name
, name_len
);
419 ri
->name
[name_len
] = 0;
422 ri
->ref_tree
= ref_tree
;
424 ri
->root_offset
= root_offset
;
433 if (!ri
->ogen
&& root_offset
)
434 ri
->ogen
= root_offset
;
438 memcpy(&ri
->uuid
, uuid
, BTRFS_UUID_SIZE
);
440 memcpy(&ri
->puuid
, puuid
, BTRFS_UUID_SIZE
);
442 memcpy(&ri
->ruuid
, ruuid
, BTRFS_UUID_SIZE
);
448 * add_root - update the existed root, or allocate a new root and insert it
449 * into the lookup tree.
450 * root_id: object id of the root
451 * ref_tree: object id of the referring root.
452 * root_offset: offset value of the root'key
453 * dir_id: inode id of the directory in ref_tree where this root can be found.
454 * name: the name of root_id in that directory
455 * name_len: the length of name
456 * ogen: the original generation of the root
457 * gen: the current generation of the root
458 * ot: the original time(create time) of the root
459 * uuid: uuid of the root
460 * puuid: uuid of the root parent if any
461 * ruuid: uuid of the received subvol, if any
463 static int add_root(struct root_lookup
*root_lookup
,
464 u64 root_id
, u64 ref_tree
, u64 root_offset
, u64 flags
,
465 u64 dir_id
, char *name
, int name_len
, u64 ogen
, u64 gen
,
466 time_t ot
, void *uuid
, void *puuid
, void *ruuid
)
468 struct root_info
*ri
;
471 ret
= update_root(root_lookup
, root_id
, ref_tree
, root_offset
, flags
,
472 dir_id
, name
, name_len
, ogen
, gen
, ot
,
477 ri
= malloc(sizeof(*ri
));
479 printf("memory allocation failed\n");
482 memset(ri
, 0, sizeof(*ri
));
483 ri
->root_id
= root_id
;
485 if (name
&& name_len
> 0) {
486 ri
->name
= malloc(name_len
+ 1);
488 fprintf(stderr
, "memory allocation failed\n");
491 strncpy(ri
->name
, name
, name_len
);
492 ri
->name
[name_len
] = 0;
495 ri
->ref_tree
= ref_tree
;
499 ri
->root_offset
= root_offset
;
506 if (!ri
->ogen
&& root_offset
)
507 ri
->ogen
= root_offset
;
512 memcpy(&ri
->uuid
, uuid
, BTRFS_UUID_SIZE
);
515 memcpy(&ri
->puuid
, puuid
, BTRFS_UUID_SIZE
);
518 memcpy(&ri
->ruuid
, ruuid
, BTRFS_UUID_SIZE
);
520 ret
= root_tree_insert(root_lookup
, ri
);
522 printf("failed to insert tree %llu\n", (unsigned long long)root_id
);
528 static void __free_root_info(struct rb_node
*node
)
530 struct root_info
*ri
;
532 ri
= rb_entry(node
, struct root_info
, rb_node
);
539 static inline void __free_all_subvolumn(struct root_lookup
*root_tree
)
541 rb_free_nodes(&root_tree
->root
, __free_root_info
);
545 * for a given root_info, search through the root_lookup tree to construct
546 * the full path name to it.
548 * This can't be called until all the root_info->path fields are filled
549 * in by lookup_ino_path
551 static int resolve_root(struct root_lookup
*rl
, struct root_info
*ri
,
554 char *full_path
= NULL
;
556 struct root_info
*found
;
559 * we go backwards from the root_info object and add pathnames
560 * from parent directories as we go.
569 * ref_tree = 0 indicates the subvolumes
572 if (!found
->ref_tree
) {
577 add_len
= strlen(found
->path
);
580 /* room for / and for null */
581 tmp
= malloc(add_len
+ 2 + len
);
583 perror("malloc failed");
586 memcpy(tmp
+ add_len
+ 1, full_path
, len
);
588 memcpy(tmp
, found
->path
, add_len
);
589 tmp
[add_len
+ len
+ 1] = '\0';
594 full_path
= strdup(found
->path
);
598 ri
->top_id
= found
->ref_tree
;
600 next
= found
->ref_tree
;
604 * if the ref_tree = BTRFS_FS_TREE_OBJECTID,
607 if (next
== BTRFS_FS_TREE_OBJECTID
)
610 * if the ref_tree wasn't in our tree of roots, the
611 * subvolume was deleted.
613 found
= root_tree_search(rl
, next
);
620 ri
->full_path
= full_path
;
626 * for a single root_info, ask the kernel to give us a path name
627 * inside it's ref_root for the dir_id where it lives.
629 * This fills in root_info->path with the path to the directory and and
630 * appends this root's name.
632 static int lookup_ino_path(int fd
, struct root_info
*ri
)
634 struct btrfs_ioctl_ino_lookup_args args
;
643 memset(&args
, 0, sizeof(args
));
644 args
.treeid
= ri
->ref_tree
;
645 args
.objectid
= ri
->dir_id
;
647 ret
= ioctl(fd
, BTRFS_IOC_INO_LOOKUP
, &args
);
654 fprintf(stderr
, "ERROR: Failed to lookup path for root %llu - %s\n",
655 (unsigned long long)ri
->ref_tree
,
662 * we're in a subdirectory of ref_tree, the kernel ioctl
663 * puts a / in there for us
665 ri
->path
= malloc(strlen(ri
->name
) + strlen(args
.name
) + 1);
667 perror("malloc failed");
670 strcpy(ri
->path
, args
.name
);
671 strcat(ri
->path
, ri
->name
);
673 /* we're at the root of ref_tree */
674 ri
->path
= strdup(ri
->name
);
676 perror("strdup failed");
683 /* finding the generation for a given path is a two step process.
684 * First we use the inode loookup routine to find out the root id
686 * Then we use the tree search ioctl to scan all the root items for a
687 * given root id and spit out the latest generation we can find
689 static u64
find_root_gen(int fd
)
691 struct btrfs_ioctl_ino_lookup_args ino_args
;
693 struct btrfs_ioctl_search_args args
;
694 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
695 struct btrfs_ioctl_search_header sh
;
696 unsigned long off
= 0;
701 memset(&ino_args
, 0, sizeof(ino_args
));
702 ino_args
.objectid
= BTRFS_FIRST_FREE_OBJECTID
;
704 /* this ioctl fills in ino_args->treeid */
705 ret
= ioctl(fd
, BTRFS_IOC_INO_LOOKUP
, &ino_args
);
708 fprintf(stderr
, "ERROR: Failed to lookup path for dirid %llu - %s\n",
709 (unsigned long long)BTRFS_FIRST_FREE_OBJECTID
,
714 memset(&args
, 0, sizeof(args
));
719 * there may be more than one ROOT_ITEM key if there are
720 * snapshots pending deletion, we have to loop through
723 sk
->min_objectid
= ino_args
.treeid
;
724 sk
->max_objectid
= ino_args
.treeid
;
725 sk
->max_type
= BTRFS_ROOT_ITEM_KEY
;
726 sk
->min_type
= BTRFS_ROOT_ITEM_KEY
;
727 sk
->max_offset
= (u64
)-1;
728 sk
->max_transid
= (u64
)-1;
732 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
735 fprintf(stderr
, "ERROR: can't perform the search - %s\n",
739 /* the ioctl returns the number of item it found in nr_items */
740 if (sk
->nr_items
== 0)
744 for (i
= 0; i
< sk
->nr_items
; i
++) {
745 struct btrfs_root_item
*item
;
747 memcpy(&sh
, args
.buf
+ off
, sizeof(sh
));
749 item
= (struct btrfs_root_item
*)(args
.buf
+ off
);
752 sk
->min_objectid
= sh
.objectid
;
753 sk
->min_type
= sh
.type
;
754 sk
->min_offset
= sh
.offset
;
756 if (sh
.objectid
> ino_args
.treeid
)
759 if (sh
.objectid
== ino_args
.treeid
&&
760 sh
.type
== BTRFS_ROOT_ITEM_KEY
) {
761 max_found
= max(max_found
,
762 btrfs_root_generation(item
));
765 if (sk
->min_offset
< (u64
)-1)
770 if (sk
->min_type
!= BTRFS_ROOT_ITEM_KEY
)
772 if (sk
->min_objectid
!= ino_args
.treeid
)
778 /* pass in a directory id and this will return
779 * the full path of the parent directory inside its
782 * It may return NULL if it is in the root, or an ERR_PTR if things
785 static char *__ino_resolve(int fd
, u64 dirid
)
787 struct btrfs_ioctl_ino_lookup_args args
;
792 memset(&args
, 0, sizeof(args
));
793 args
.objectid
= dirid
;
795 ret
= ioctl(fd
, BTRFS_IOC_INO_LOOKUP
, &args
);
798 fprintf(stderr
, "ERROR: Failed to lookup path for dirid %llu - %s\n",
799 (unsigned long long)dirid
, strerror(e
) );
805 * we're in a subdirectory of ref_tree, the kernel ioctl
806 * puts a / in there for us
808 full
= strdup(args
.name
);
810 perror("malloc failed");
811 return ERR_PTR(-ENOMEM
);
814 /* we're at the root of ref_tree */
821 * simple string builder, returning a new string with both
824 static char *build_name(char *dirid
, char *name
)
830 full
= malloc(strlen(dirid
) + strlen(name
) + 1);
839 * given an inode number, this returns the full path name inside the subvolume
840 * to that file/directory. cache_dirid and cache_name are used to
841 * cache the results so we can avoid tree searches if a later call goes
842 * to the same directory or file name
844 static char *ino_resolve(int fd
, u64 ino
, u64
*cache_dirid
, char **cache_name
)
852 struct btrfs_ioctl_search_args args
;
853 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
854 struct btrfs_ioctl_search_header
*sh
;
855 unsigned long off
= 0;
859 memset(&args
, 0, sizeof(args
));
864 * step one, we search for the inode back ref. We just use the first
867 sk
->min_objectid
= ino
;
868 sk
->max_objectid
= ino
;
869 sk
->max_type
= BTRFS_INODE_REF_KEY
;
870 sk
->max_offset
= (u64
)-1;
871 sk
->min_type
= BTRFS_INODE_REF_KEY
;
872 sk
->max_transid
= (u64
)-1;
875 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
878 fprintf(stderr
, "ERROR: can't perform the search - %s\n",
882 /* the ioctl returns the number of item it found in nr_items */
883 if (sk
->nr_items
== 0)
887 sh
= (struct btrfs_ioctl_search_header
*)(args
.buf
+ off
);
889 if (sh
->type
== BTRFS_INODE_REF_KEY
) {
890 struct btrfs_inode_ref
*ref
;
893 ref
= (struct btrfs_inode_ref
*)(sh
+ 1);
894 namelen
= btrfs_stack_inode_ref_name_len(ref
);
896 name
= (char *)(ref
+ 1);
897 name
= strndup(name
, namelen
);
899 /* use our cached value */
900 if (dirid
== *cache_dirid
&& *cache_name
) {
901 dirname
= *cache_name
;
908 * the inode backref gives us the file name and the parent directory id.
909 * From here we use __ino_resolve to get the path to the parent
911 dirname
= __ino_resolve(fd
, dirid
);
913 full
= build_name(dirname
, name
);
914 if (*cache_name
&& dirname
!= *cache_name
)
917 *cache_name
= dirname
;
918 *cache_dirid
= dirid
;
924 int btrfs_list_get_default_subvolume(int fd
, u64
*default_id
)
926 struct btrfs_ioctl_search_args args
;
927 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
928 struct btrfs_ioctl_search_header
*sh
;
932 memset(&args
, 0, sizeof(args
));
935 * search for a dir item with a name 'default' in the tree of
936 * tree roots, it should point us to a default root
940 /* don't worry about ancient format and request only one item */
943 sk
->max_objectid
= BTRFS_ROOT_TREE_DIR_OBJECTID
;
944 sk
->min_objectid
= BTRFS_ROOT_TREE_DIR_OBJECTID
;
945 sk
->max_type
= BTRFS_DIR_ITEM_KEY
;
946 sk
->min_type
= BTRFS_DIR_ITEM_KEY
;
947 sk
->max_offset
= (u64
)-1;
948 sk
->max_transid
= (u64
)-1;
950 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
954 /* the ioctl returns the number of items it found in nr_items */
955 if (sk
->nr_items
== 0)
958 sh
= (struct btrfs_ioctl_search_header
*)args
.buf
;
960 if (sh
->type
== BTRFS_DIR_ITEM_KEY
) {
961 struct btrfs_dir_item
*di
;
965 di
= (struct btrfs_dir_item
*)(sh
+ 1);
966 name_len
= btrfs_stack_dir_name_len(di
);
967 name
= (char *)(di
+ 1);
969 if (!strncmp("default", name
, name_len
))
970 found
= btrfs_disk_key_objectid(&di
->location
);
978 static int __list_subvol_search(int fd
, struct root_lookup
*root_lookup
)
981 struct btrfs_ioctl_search_args args
;
982 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
983 struct btrfs_ioctl_search_header sh
;
984 struct btrfs_root_ref
*ref
;
985 struct btrfs_root_item
*ri
;
986 unsigned long off
= 0;
995 u8 uuid
[BTRFS_UUID_SIZE
];
996 u8 puuid
[BTRFS_UUID_SIZE
];
997 u8 ruuid
[BTRFS_UUID_SIZE
];
999 root_lookup_init(root_lookup
);
1000 memset(&args
, 0, sizeof(args
));
1002 /* search in the tree of tree roots */
1006 * set the min and max to backref keys. The search will
1007 * only send back this type of key now.
1009 sk
->max_type
= BTRFS_ROOT_BACKREF_KEY
;
1010 sk
->min_type
= BTRFS_ROOT_ITEM_KEY
;
1012 sk
->min_objectid
= BTRFS_FIRST_FREE_OBJECTID
;
1015 * set all the other params to the max, we'll take any objectid
1018 sk
->max_objectid
= BTRFS_LAST_FREE_OBJECTID
;
1019 sk
->max_offset
= (u64
)-1;
1020 sk
->max_transid
= (u64
)-1;
1022 /* just a big number, doesn't matter much */
1023 sk
->nr_items
= 4096;
1026 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
1029 /* the ioctl returns the number of item it found in nr_items */
1030 if (sk
->nr_items
== 0)
1036 * for each item, pull the key out of the header and then
1037 * read the root_ref item it contains
1039 for (i
= 0; i
< sk
->nr_items
; i
++) {
1040 memcpy(&sh
, args
.buf
+ off
, sizeof(sh
));
1042 if (sh
.type
== BTRFS_ROOT_BACKREF_KEY
) {
1043 ref
= (struct btrfs_root_ref
*)(args
.buf
+ off
);
1044 name_len
= btrfs_stack_root_ref_name_len(ref
);
1045 name
= (char *)(ref
+ 1);
1046 dir_id
= btrfs_stack_root_ref_dirid(ref
);
1048 add_root(root_lookup
, sh
.objectid
, sh
.offset
,
1049 0, 0, dir_id
, name
, name_len
, 0, 0, 0,
1051 } else if (sh
.type
== BTRFS_ROOT_ITEM_KEY
) {
1052 ri
= (struct btrfs_root_item
*)(args
.buf
+ off
);
1053 gen
= btrfs_root_generation(ri
);
1054 flags
= btrfs_root_flags(ri
);
1056 sizeof(struct btrfs_root_item_v0
)) {
1057 t
= btrfs_stack_timespec_sec(&ri
->otime
);
1058 ogen
= btrfs_root_otransid(ri
);
1059 memcpy(uuid
, ri
->uuid
, BTRFS_UUID_SIZE
);
1060 memcpy(puuid
, ri
->parent_uuid
, BTRFS_UUID_SIZE
);
1061 memcpy(ruuid
, ri
->received_uuid
, BTRFS_UUID_SIZE
);
1065 memset(uuid
, 0, BTRFS_UUID_SIZE
);
1066 memset(puuid
, 0, BTRFS_UUID_SIZE
);
1067 memset(ruuid
, 0, BTRFS_UUID_SIZE
);
1070 add_root(root_lookup
, sh
.objectid
, 0,
1071 sh
.offset
, flags
, 0, NULL
, 0, ogen
,
1072 gen
, t
, uuid
, puuid
, ruuid
);
1078 * record the mins in sk so we can make sure the
1079 * next search doesn't repeat this root
1081 sk
->min_objectid
= sh
.objectid
;
1082 sk
->min_type
= sh
.type
;
1083 sk
->min_offset
= sh
.offset
;
1085 sk
->nr_items
= 4096;
1087 if (!sk
->min_offset
) /* overflow */
1092 if (sk
->min_type
> BTRFS_ROOT_BACKREF_KEY
) {
1093 sk
->min_type
= BTRFS_ROOT_ITEM_KEY
;
1098 if (sk
->min_objectid
> sk
->max_objectid
)
1105 static int filter_by_rootid(struct root_info
*ri
, u64 data
)
1107 return ri
->root_id
== data
;
1110 static int filter_snapshot(struct root_info
*ri
, u64 data
)
1112 return !!ri
->root_offset
;
1115 static int filter_flags(struct root_info
*ri
, u64 flags
)
1117 return ri
->flags
& flags
;
1120 static int filter_gen_more(struct root_info
*ri
, u64 data
)
1122 return ri
->gen
>= data
;
1125 static int filter_gen_less(struct root_info
*ri
, u64 data
)
1127 return ri
->gen
<= data
;
1130 static int filter_gen_equal(struct root_info
*ri
, u64 data
)
1132 return ri
->gen
== data
;
1135 static int filter_cgen_more(struct root_info
*ri
, u64 data
)
1137 return ri
->ogen
>= data
;
1140 static int filter_cgen_less(struct root_info
*ri
, u64 data
)
1142 return ri
->ogen
<= data
;
1145 static int filter_cgen_equal(struct root_info
*ri
, u64 data
)
1147 return ri
->ogen
== data
;
1150 static int filter_topid_equal(struct root_info
*ri
, u64 data
)
1152 return ri
->top_id
== data
;
1155 static int filter_full_path(struct root_info
*ri
, u64 data
)
1157 if (ri
->full_path
&& ri
->top_id
!= data
) {
1159 char p
[] = "<FS_TREE>";
1160 int add_len
= strlen(p
);
1161 int len
= strlen(ri
->full_path
);
1163 tmp
= malloc(len
+ add_len
+ 2);
1165 fprintf(stderr
, "memory allocation failed\n");
1168 memcpy(tmp
+ add_len
+ 1, ri
->full_path
, len
);
1169 tmp
[len
+ add_len
+ 1] = '\0';
1171 memcpy(tmp
, p
, add_len
);
1172 free(ri
->full_path
);
1173 ri
->full_path
= tmp
;
1178 static int filter_by_parent(struct root_info
*ri
, u64 data
)
1180 return !uuid_compare(ri
->puuid
, (u8
*)(unsigned long)data
);
1183 static int filter_deleted(struct root_info
*ri
, u64 data
)
1188 static btrfs_list_filter_func all_filter_funcs
[] = {
1189 [BTRFS_LIST_FILTER_ROOTID
] = filter_by_rootid
,
1190 [BTRFS_LIST_FILTER_SNAPSHOT_ONLY
] = filter_snapshot
,
1191 [BTRFS_LIST_FILTER_FLAGS
] = filter_flags
,
1192 [BTRFS_LIST_FILTER_GEN_MORE
] = filter_gen_more
,
1193 [BTRFS_LIST_FILTER_GEN_LESS
] = filter_gen_less
,
1194 [BTRFS_LIST_FILTER_GEN_EQUAL
] = filter_gen_equal
,
1195 [BTRFS_LIST_FILTER_CGEN_MORE
] = filter_cgen_more
,
1196 [BTRFS_LIST_FILTER_CGEN_LESS
] = filter_cgen_less
,
1197 [BTRFS_LIST_FILTER_CGEN_EQUAL
] = filter_cgen_equal
,
1198 [BTRFS_LIST_FILTER_TOPID_EQUAL
] = filter_topid_equal
,
1199 [BTRFS_LIST_FILTER_FULL_PATH
] = filter_full_path
,
1200 [BTRFS_LIST_FILTER_BY_PARENT
] = filter_by_parent
,
1201 [BTRFS_LIST_FILTER_DELETED
] = filter_deleted
,
1204 struct btrfs_list_filter_set
*btrfs_list_alloc_filter_set(void)
1206 struct btrfs_list_filter_set
*set
;
1209 size
= sizeof(struct btrfs_list_filter_set
) +
1210 BTRFS_LIST_NFILTERS_INCREASE
* sizeof(struct btrfs_list_filter
);
1213 fprintf(stderr
, "memory allocation failed\n");
1217 memset(set
, 0, size
);
1218 set
->total
= BTRFS_LIST_NFILTERS_INCREASE
;
1223 void btrfs_list_free_filter_set(struct btrfs_list_filter_set
*filter_set
)
1228 int btrfs_list_setup_filter(struct btrfs_list_filter_set
**filter_set
,
1229 enum btrfs_list_filter_enum filter
, u64 data
)
1231 struct btrfs_list_filter_set
*set
= *filter_set
;
1235 BUG_ON(filter
>= BTRFS_LIST_FILTER_MAX
);
1236 BUG_ON(set
->nfilters
> set
->total
);
1238 if (set
->nfilters
== set
->total
) {
1241 size
= set
->total
+ BTRFS_LIST_NFILTERS_INCREASE
;
1242 size
= sizeof(*set
) + size
* sizeof(struct btrfs_list_filter
);
1244 set
= realloc(set
, size
);
1246 fprintf(stderr
, "memory allocation failed\n");
1251 memset(&set
->filters
[set
->total
], 0,
1252 BTRFS_LIST_NFILTERS_INCREASE
*
1253 sizeof(struct btrfs_list_filter
));
1254 set
->total
+= BTRFS_LIST_NFILTERS_INCREASE
;
1258 BUG_ON(set
->filters
[set
->nfilters
].filter_func
);
1260 if (filter
== BTRFS_LIST_FILTER_DELETED
)
1261 set
->only_deleted
= 1;
1263 set
->filters
[set
->nfilters
].filter_func
= all_filter_funcs
[filter
];
1264 set
->filters
[set
->nfilters
].data
= data
;
1269 static int filter_root(struct root_info
*ri
,
1270 struct btrfs_list_filter_set
*set
)
1277 if (set
->only_deleted
&& !ri
->deleted
)
1280 if (!set
->only_deleted
&& ri
->deleted
)
1283 for (i
= 0; i
< set
->nfilters
; i
++) {
1284 if (!set
->filters
[i
].filter_func
)
1286 ret
= set
->filters
[i
].filter_func(ri
, set
->filters
[i
].data
);
1293 static void __filter_and_sort_subvol(struct root_lookup
*all_subvols
,
1294 struct root_lookup
*sort_tree
,
1295 struct btrfs_list_filter_set
*filter_set
,
1296 struct btrfs_list_comparer_set
*comp_set
,
1300 struct root_info
*entry
;
1303 root_lookup_init(sort_tree
);
1305 n
= rb_last(&all_subvols
->root
);
1307 entry
= rb_entry(n
, struct root_info
, rb_node
);
1309 ret
= resolve_root(all_subvols
, entry
, top_id
);
1310 if (ret
== -ENOENT
) {
1311 entry
->full_path
= strdup("DELETED");
1314 ret
= filter_root(entry
, filter_set
);
1316 sort_tree_insert(sort_tree
, entry
, comp_set
);
1321 static int __list_subvol_fill_paths(int fd
, struct root_lookup
*root_lookup
)
1325 n
= rb_first(&root_lookup
->root
);
1327 struct root_info
*entry
;
1329 entry
= rb_entry(n
, struct root_info
, rb_node
);
1330 ret
= lookup_ino_path(fd
, entry
);
1331 if (ret
&& ret
!= -ENOENT
)
1339 static void print_subvolume_column(struct root_info
*subv
,
1340 enum btrfs_list_column_enum column
)
1343 char uuidparse
[BTRFS_UUID_UNPARSED_SIZE
];
1345 BUG_ON(column
>= BTRFS_LIST_ALL
|| column
< 0);
1348 case BTRFS_LIST_OBJECTID
:
1349 printf("%llu", subv
->root_id
);
1351 case BTRFS_LIST_GENERATION
:
1352 printf("%llu", subv
->gen
);
1354 case BTRFS_LIST_OGENERATION
:
1355 printf("%llu", subv
->ogen
);
1357 case BTRFS_LIST_PARENT
:
1358 printf("%llu", subv
->ref_tree
);
1360 case BTRFS_LIST_TOP_LEVEL
:
1361 printf("%llu", subv
->top_id
);
1363 case BTRFS_LIST_OTIME
:
1367 localtime_r(&subv
->otime
, &tm
);
1368 strftime(tstr
, 256, "%Y-%m-%d %X", &tm
);
1373 case BTRFS_LIST_UUID
:
1374 if (uuid_is_null(subv
->uuid
))
1375 strcpy(uuidparse
, "-");
1377 uuid_unparse(subv
->uuid
, uuidparse
);
1378 printf("%s", uuidparse
);
1380 case BTRFS_LIST_PUUID
:
1381 if (uuid_is_null(subv
->puuid
))
1382 strcpy(uuidparse
, "-");
1384 uuid_unparse(subv
->puuid
, uuidparse
);
1385 printf("%s", uuidparse
);
1387 case BTRFS_LIST_RUUID
:
1388 if (uuid_is_null(subv
->ruuid
))
1389 strcpy(uuidparse
, "-");
1391 uuid_unparse(subv
->ruuid
, uuidparse
);
1392 printf("%s", uuidparse
);
1394 case BTRFS_LIST_PATH
:
1395 BUG_ON(!subv
->full_path
);
1396 printf("%s", subv
->full_path
);
1403 static void print_single_volume_info_raw(struct root_info
*subv
, char *raw_prefix
)
1407 for (i
= 0; i
< BTRFS_LIST_ALL
; i
++) {
1408 if (!btrfs_list_columns
[i
].need_print
)
1412 printf("%s",raw_prefix
);
1414 print_subvolume_column(subv
, i
);
1419 static void print_single_volume_info_table(struct root_info
*subv
)
1423 for (i
= 0; i
< BTRFS_LIST_ALL
; i
++) {
1424 if (!btrfs_list_columns
[i
].need_print
)
1427 print_subvolume_column(subv
, i
);
1429 if (i
!= BTRFS_LIST_PATH
)
1432 if (i
== BTRFS_LIST_TOP_LEVEL
)
1438 static void print_single_volume_info_default(struct root_info
*subv
)
1442 for (i
= 0; i
< BTRFS_LIST_ALL
; i
++) {
1443 if (!btrfs_list_columns
[i
].need_print
)
1446 printf("%s ", btrfs_list_columns
[i
].name
);
1447 print_subvolume_column(subv
, i
);
1449 if (i
!= BTRFS_LIST_PATH
)
1455 static void print_all_volume_info_tab_head(void)
1461 for (i
= 0; i
< BTRFS_LIST_ALL
; i
++) {
1462 if (btrfs_list_columns
[i
].need_print
)
1463 printf("%s\t", btrfs_list_columns
[i
].name
);
1465 if (i
== BTRFS_LIST_ALL
-1)
1469 for (i
= 0; i
< BTRFS_LIST_ALL
; i
++) {
1470 memset(barrier
, 0, sizeof(barrier
));
1472 if (btrfs_list_columns
[i
].need_print
) {
1473 len
= strlen(btrfs_list_columns
[i
].name
);
1475 strcat(barrier
, "-");
1477 printf("%s\t", barrier
);
1479 if (i
== BTRFS_LIST_ALL
-1)
1484 static void print_all_volume_info(struct root_lookup
*sorted_tree
,
1485 int layout
, char *raw_prefix
)
1488 struct root_info
*entry
;
1490 if (layout
== BTRFS_LIST_LAYOUT_TABLE
)
1491 print_all_volume_info_tab_head();
1493 n
= rb_first(&sorted_tree
->root
);
1495 entry
= rb_entry(n
, struct root_info
, sort_node
);
1497 case BTRFS_LIST_LAYOUT_DEFAULT
:
1498 print_single_volume_info_default(entry
);
1500 case BTRFS_LIST_LAYOUT_TABLE
:
1501 print_single_volume_info_table(entry
);
1503 case BTRFS_LIST_LAYOUT_RAW
:
1504 print_single_volume_info_raw(entry
, raw_prefix
);
1511 static int btrfs_list_subvols(int fd
, struct root_lookup
*root_lookup
)
1515 ret
= __list_subvol_search(fd
, root_lookup
);
1517 fprintf(stderr
, "ERROR: can't perform the search - %s\n",
1523 * now we have an rbtree full of root_info objects, but we need to fill
1524 * in their path names within the subvol that is referencing each one.
1526 ret
= __list_subvol_fill_paths(fd
, root_lookup
);
1530 int btrfs_list_subvols_print(int fd
, struct btrfs_list_filter_set
*filter_set
,
1531 struct btrfs_list_comparer_set
*comp_set
,
1532 int layout
, int full_path
, char *raw_prefix
)
1534 struct root_lookup root_lookup
;
1535 struct root_lookup root_sort
;
1540 ret
= btrfs_list_get_path_rootid(fd
, &top_id
);
1544 ret
= btrfs_list_subvols(fd
, &root_lookup
);
1547 __filter_and_sort_subvol(&root_lookup
, &root_sort
, filter_set
,
1550 print_all_volume_info(&root_sort
, layout
, raw_prefix
);
1551 __free_all_subvolumn(&root_lookup
);
1556 static char *strdup_or_null(const char *s
)
1563 int btrfs_get_subvol(int fd
, struct root_info
*the_ri
)
1566 struct root_lookup rl
;
1567 struct rb_node
*rbn
;
1568 struct root_info
*ri
;
1571 ret
= btrfs_list_get_path_rootid(fd
, &root_id
);
1575 ret
= btrfs_list_subvols(fd
, &rl
);
1579 rbn
= rb_first(&rl
.root
);
1581 ri
= rb_entry(rbn
, struct root_info
, rb_node
);
1582 rr
= resolve_root(&rl
, ri
, root_id
);
1583 if (rr
== -ENOENT
) {
1588 if (!comp_entry_with_rootid(the_ri
, ri
, 0)) {
1589 memcpy(the_ri
, ri
, offsetof(struct root_info
, path
));
1590 the_ri
->path
= strdup_or_null(ri
->path
);
1591 the_ri
->name
= strdup_or_null(ri
->name
);
1592 the_ri
->full_path
= strdup_or_null(ri
->full_path
);
1598 __free_all_subvolumn(&rl
);
1602 static int print_one_extent(int fd
, struct btrfs_ioctl_search_header
*sh
,
1603 struct btrfs_file_extent_item
*item
,
1604 u64 found_gen
, u64
*cache_dirid
,
1605 char **cache_dir_name
, u64
*cache_ino
,
1606 char **cache_full_name
)
1610 u64 disk_offset
= 0;
1616 if (sh
->objectid
== *cache_ino
) {
1617 name
= *cache_full_name
;
1618 } else if (*cache_full_name
) {
1619 free(*cache_full_name
);
1620 *cache_full_name
= NULL
;
1623 name
= ino_resolve(fd
, sh
->objectid
, cache_dirid
,
1625 *cache_full_name
= name
;
1626 *cache_ino
= sh
->objectid
;
1631 type
= btrfs_stack_file_extent_type(item
);
1632 compressed
= btrfs_stack_file_extent_compression(item
);
1634 if (type
== BTRFS_FILE_EXTENT_REG
||
1635 type
== BTRFS_FILE_EXTENT_PREALLOC
) {
1636 disk_start
= btrfs_stack_file_extent_disk_bytenr(item
);
1637 disk_offset
= btrfs_stack_file_extent_offset(item
);
1638 len
= btrfs_stack_file_extent_num_bytes(item
);
1639 } else if (type
== BTRFS_FILE_EXTENT_INLINE
) {
1642 len
= btrfs_stack_file_extent_ram_bytes(item
);
1644 printf("unhandled extent type %d for inode %llu "
1645 "file offset %llu gen %llu\n",
1647 (unsigned long long)sh
->objectid
,
1648 (unsigned long long)sh
->offset
,
1649 (unsigned long long)found_gen
);
1653 printf("inode %llu file offset %llu len %llu disk start %llu "
1654 "offset %llu gen %llu flags ",
1655 (unsigned long long)sh
->objectid
,
1656 (unsigned long long)sh
->offset
,
1657 (unsigned long long)len
,
1658 (unsigned long long)disk_start
,
1659 (unsigned long long)disk_offset
,
1660 (unsigned long long)found_gen
);
1666 if (type
== BTRFS_FILE_EXTENT_PREALLOC
) {
1667 printf("%sPREALLOC", flags
? "|" : "");
1670 if (type
== BTRFS_FILE_EXTENT_INLINE
) {
1671 printf("%sINLINE", flags
? "|" : "");
1677 printf(" %s\n", name
);
1681 int btrfs_list_find_updated_files(int fd
, u64 root_id
, u64 oldest_gen
)
1684 struct btrfs_ioctl_search_args args
;
1685 struct btrfs_ioctl_search_key
*sk
= &args
.key
;
1686 struct btrfs_ioctl_search_header sh
;
1687 struct btrfs_file_extent_item
*item
;
1688 unsigned long off
= 0;
1693 u64 cache_dirid
= 0;
1695 char *cache_dir_name
= NULL
;
1696 char *cache_full_name
= NULL
;
1697 struct btrfs_file_extent_item backup
;
1699 memset(&backup
, 0, sizeof(backup
));
1700 memset(&args
, 0, sizeof(args
));
1702 sk
->tree_id
= root_id
;
1705 * set all the other params to the max, we'll take any objectid
1708 sk
->max_objectid
= (u64
)-1;
1709 sk
->max_offset
= (u64
)-1;
1710 sk
->max_transid
= (u64
)-1;
1711 sk
->max_type
= BTRFS_EXTENT_DATA_KEY
;
1712 sk
->min_transid
= oldest_gen
;
1713 /* just a big number, doesn't matter much */
1714 sk
->nr_items
= 4096;
1716 max_found
= find_root_gen(fd
);
1718 ret
= ioctl(fd
, BTRFS_IOC_TREE_SEARCH
, &args
);
1721 fprintf(stderr
, "ERROR: can't perform the search - %s\n",
1725 /* the ioctl returns the number of item it found in nr_items */
1726 if (sk
->nr_items
== 0)
1732 * for each item, pull the key out of the header and then
1733 * read the root_ref item it contains
1735 for (i
= 0; i
< sk
->nr_items
; i
++) {
1736 memcpy(&sh
, args
.buf
+ off
, sizeof(sh
));
1740 * just in case the item was too big, pass something other
1746 item
= (struct btrfs_file_extent_item
*)(args
.buf
+
1748 found_gen
= btrfs_stack_file_extent_generation(item
);
1749 if (sh
.type
== BTRFS_EXTENT_DATA_KEY
&&
1750 found_gen
>= oldest_gen
) {
1751 print_one_extent(fd
, &sh
, item
, found_gen
,
1752 &cache_dirid
, &cache_dir_name
,
1753 &cache_ino
, &cache_full_name
);
1758 * record the mins in sk so we can make sure the
1759 * next search doesn't repeat this root
1761 sk
->min_objectid
= sh
.objectid
;
1762 sk
->min_offset
= sh
.offset
;
1763 sk
->min_type
= sh
.type
;
1765 sk
->nr_items
= 4096;
1766 if (sk
->min_offset
< (u64
)-1)
1768 else if (sk
->min_objectid
< (u64
)-1) {
1775 free(cache_dir_name
);
1776 free(cache_full_name
);
1777 printf("transid marker was %llu\n", (unsigned long long)max_found
);
1781 char *btrfs_list_path_for_root(int fd
, u64 root
)
1783 struct root_lookup root_lookup
;
1785 char *ret_path
= NULL
;
1789 ret
= btrfs_list_get_path_rootid(fd
, &top_id
);
1791 return ERR_PTR(ret
);
1793 ret
= __list_subvol_search(fd
, &root_lookup
);
1795 return ERR_PTR(ret
);
1797 ret
= __list_subvol_fill_paths(fd
, &root_lookup
);
1799 return ERR_PTR(ret
);
1801 n
= rb_last(&root_lookup
.root
);
1803 struct root_info
*entry
;
1805 entry
= rb_entry(n
, struct root_info
, rb_node
);
1806 ret
= resolve_root(&root_lookup
, entry
, top_id
);
1807 if (ret
== -ENOENT
&& entry
->root_id
== root
) {
1811 if (entry
->root_id
== root
) {
1812 ret_path
= entry
->full_path
;
1813 entry
->full_path
= NULL
;
1818 __free_all_subvolumn(&root_lookup
);
1823 int btrfs_list_parse_sort_string(char *opt_arg
,
1824 struct btrfs_list_comparer_set
**comps
)
1832 while ((p
= strtok(opt_arg
, ",")) != NULL
) {
1834 ptr_argv
= all_sort_items
;
1837 if (strcmp(*ptr_argv
, p
) == 0) {
1842 if (strcmp(*ptr_argv
, p
) == 0) {
1859 } else if (*p
== '-') {
1865 what_to_sort
= btrfs_list_get_sort_item(p
);
1866 btrfs_list_setup_comparer(comps
, what_to_sort
, order
);
1875 * This function is used to parse the argument of filter condition.
1877 * type is the filter object.
1879 int btrfs_list_parse_filter_string(char *opt_arg
,
1880 struct btrfs_list_filter_set
**filters
,
1881 enum btrfs_list_filter_enum type
)
1886 switch (*(opt_arg
++)) {
1888 arg
= arg_strtou64(opt_arg
);
1891 btrfs_list_setup_filter(filters
, type
, arg
);
1894 arg
= arg_strtou64(opt_arg
);
1897 btrfs_list_setup_filter(filters
, type
, arg
);
1901 arg
= arg_strtou64(opt_arg
);
1903 btrfs_list_setup_filter(filters
, type
, arg
);
1910 int btrfs_list_get_path_rootid(int fd
, u64
*treeid
)
1913 struct btrfs_ioctl_ino_lookup_args args
;
1915 memset(&args
, 0, sizeof(args
));
1916 args
.objectid
= BTRFS_FIRST_FREE_OBJECTID
;
1918 ret
= ioctl(fd
, BTRFS_IOC_INO_LOOKUP
, &args
);
1921 "ERROR: can't perform the search - %s\n",
1925 *treeid
= args
.treeid
;