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)