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 /* generation when the root is created or last updated */
63 /* path from the subvol we live in to this root, including the
64 * root's name. This is null until we do the extra lookup ioctl.
68 /* the name of this root in the directory it lives in */
72 static void root_lookup_init(struct root_lookup *tree)
74 tree->root.rb_node = NULL;
77 static int comp_entry(struct root_info *entry, u64 root_id, u64 ref_tree)
79 if (entry->root_id > root_id)
81 if (entry->root_id < root_id)
83 if (entry->ref_tree > ref_tree)
85 if (entry->ref_tree < ref_tree)
91 * insert a new root into the tree. returns the existing root entry
92 * if one is already there. Both root_id and ref_tree are used
95 static struct rb_node *tree_insert(struct rb_root *root, u64 root_id,
96 u64 ref_tree, struct rb_node *node)
98 struct rb_node ** p = &root->rb_node;
99 struct rb_node * parent = NULL;
100 struct root_info *entry;
105 entry = rb_entry(parent, struct root_info, rb_node);
107 comp = comp_entry(entry, root_id, ref_tree);
117 entry = rb_entry(parent, struct root_info, rb_node);
118 rb_link_node(node, parent, p);
119 rb_insert_color(node, root);
124 * find a given root id in the tree. We return the smallest one,
125 * rb_next can be used to move forward looking for more if required
127 static struct root_info *tree_search(struct rb_root *root, u64 root_id)
129 struct rb_node * n = root->rb_node;
130 struct root_info *entry;
133 entry = rb_entry(n, struct root_info, rb_node);
135 if (entry->root_id < root_id)
137 else if (entry->root_id > root_id)
140 struct root_info *prev;
141 struct rb_node *prev_n;
146 prev = rb_entry(prev_n, struct root_info,
148 if (prev->root_id != root_id)
160 * this allocates a new root in the lookup tree.
162 * root_id should be the object id of the root
164 * ref_tree is the objectid of the referring root.
166 * dir_id is the directory in ref_tree where this root_id can be found.
168 * name is the name of root_id in that directory
170 * name_len is the length of name
172 static int add_root(struct root_lookup *root_lookup,
173 u64 root_id, u64 ref_tree, u64 dir_id, char *name,
176 struct root_info *ri;
178 ri = malloc(sizeof(*ri) + name_len + 1);
180 printf("memory allocation failed\n");
183 memset(ri, 0, sizeof(*ri) + name_len + 1);
186 ri->root_id = root_id;
187 ri->ref_tree = ref_tree;
188 strncpy(ri->name, name, name_len);
190 ri->name[name_len] = 0;
192 ret = tree_insert(&root_lookup->root, root_id, ref_tree, &ri->rb_node);
194 printf("failed to insert tree %llu\n", (unsigned long long)root_id);
200 static int update_root(struct root_lookup *root_lookup, u64 root_id, u64 gen)
202 struct root_info *ri;
204 ri = tree_search(&root_lookup->root, root_id);
205 if (!ri || ri->root_id != root_id) {
206 fprintf(stderr, "could not find subvol %llu\n", root_id);
214 * for a given root_info, search through the root_lookup tree to construct
215 * the full path name to it.
217 * This can't be called until all the root_info->path fields are filled
218 * in by lookup_ino_path
220 static int resolve_root(struct root_lookup *rl, struct root_info *ri,
221 u64 *parent_id, u64 *top_id, char **path)
223 char *full_path = NULL;
225 struct root_info *found;
228 * we go backwards from the root_info object and add pathnames
229 * from parent directories as we go.
236 int add_len = strlen(found->path);
238 /* room for / and for null */
239 tmp = malloc(add_len + 2 + len);
241 memcpy(tmp + add_len + 1, full_path, len);
243 memcpy(tmp, found->path, add_len);
244 tmp [add_len + len + 1] = '\0';
249 full_path = strdup(found->path);
253 next = found->ref_tree;
254 /* record the first parent */
258 /* if the ref_tree refers to ourselves, we're at the top */
259 if (next == found->root_id) {
265 * if the ref_tree wasn't in our tree of roots, we're
268 found = tree_search(&rl->root, next);
281 * for a single root_info, ask the kernel to give us a path name
282 * inside it's ref_root for the dir_id where it lives.
284 * This fills in root_info->path with the path to the directory and and
285 * appends this root's name.
287 static int lookup_ino_path(int fd, struct root_info *ri)
289 struct btrfs_ioctl_ino_lookup_args args;
295 memset(&args, 0, sizeof(args));
296 args.treeid = ri->ref_tree;
297 args.objectid = ri->dir_id;
299 ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &args);
302 fprintf(stderr, "ERROR: Failed to lookup path for root %llu - %s\n",
303 (unsigned long long)ri->ref_tree,
310 * we're in a subdirectory of ref_tree, the kernel ioctl
311 * puts a / in there for us
313 ri->path = malloc(strlen(ri->name) + strlen(args.name) + 1);
315 perror("malloc failed");
318 strcpy(ri->path, args.name);
319 strcat(ri->path, ri->name);
321 /* we're at the root of ref_tree */
322 ri->path = strdup(ri->name);
324 perror("strdup failed");
331 /* finding the generation for a given path is a two step process.
332 * First we use the inode loookup routine to find out the root id
334 * Then we use the tree search ioctl to scan all the root items for a
335 * given root id and spit out the latest generation we can find
337 static u64 find_root_gen(int fd)
339 struct btrfs_ioctl_ino_lookup_args ino_args;
341 struct btrfs_ioctl_search_args args;
342 struct btrfs_ioctl_search_key *sk = &args.key;
343 struct btrfs_ioctl_search_header *sh;
344 unsigned long off = 0;
349 memset(&ino_args, 0, sizeof(ino_args));
350 ino_args.objectid = BTRFS_FIRST_FREE_OBJECTID;
352 /* this ioctl fills in ino_args->treeid */
353 ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &ino_args);
356 fprintf(stderr, "ERROR: Failed to lookup path for dirid %llu - %s\n",
357 (unsigned long long)BTRFS_FIRST_FREE_OBJECTID,
362 memset(&args, 0, sizeof(args));
367 * there may be more than one ROOT_ITEM key if there are
368 * snapshots pending deletion, we have to loop through
371 sk->min_objectid = ino_args.treeid;
372 sk->max_objectid = ino_args.treeid;
373 sk->max_type = BTRFS_ROOT_ITEM_KEY;
374 sk->min_type = BTRFS_ROOT_ITEM_KEY;
375 sk->max_offset = (u64)-1;
376 sk->max_transid = (u64)-1;
380 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
383 fprintf(stderr, "ERROR: can't perform the search - %s\n",
387 /* the ioctl returns the number of item it found in nr_items */
388 if (sk->nr_items == 0)
392 for (i = 0; i < sk->nr_items; i++) {
393 struct btrfs_root_item *item;
394 sh = (struct btrfs_ioctl_search_header *)(args.buf +
398 item = (struct btrfs_root_item *)(args.buf + off);
401 sk->min_objectid = sh->objectid;
402 sk->min_type = sh->type;
403 sk->min_offset = sh->offset;
405 if (sh->objectid > ino_args.treeid)
408 if (sh->objectid == ino_args.treeid &&
409 sh->type == BTRFS_ROOT_ITEM_KEY) {
410 max_found = max(max_found,
411 btrfs_root_generation(item));
414 if (sk->min_offset < (u64)-1)
419 if (sk->min_type != BTRFS_ROOT_ITEM_KEY)
421 if (sk->min_objectid != BTRFS_ROOT_ITEM_KEY)
427 /* pass in a directory id and this will return
428 * the full path of the parent directory inside its
431 * It may return NULL if it is in the root, or an ERR_PTR if things
434 static char *__ino_resolve(int fd, u64 dirid)
436 struct btrfs_ioctl_ino_lookup_args args;
441 memset(&args, 0, sizeof(args));
442 args.objectid = dirid;
444 ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &args);
447 fprintf(stderr, "ERROR: Failed to lookup path for dirid %llu - %s\n",
448 (unsigned long long)dirid, strerror(e) );
454 * we're in a subdirectory of ref_tree, the kernel ioctl
455 * puts a / in there for us
457 full = strdup(args.name);
459 perror("malloc failed");
460 return ERR_PTR(-ENOMEM);
463 /* we're at the root of ref_tree */
470 * simple string builder, returning a new string with both
473 char *build_name(char *dirid, char *name)
479 full = malloc(strlen(dirid) + strlen(name) + 1);
488 * given an inode number, this returns the full path name inside the subvolume
489 * to that file/directory. cache_dirid and cache_name are used to
490 * cache the results so we can avoid tree searches if a later call goes
491 * to the same directory or file name
493 static char *ino_resolve(int fd, u64 ino, u64 *cache_dirid, char **cache_name)
501 struct btrfs_ioctl_search_args args;
502 struct btrfs_ioctl_search_key *sk = &args.key;
503 struct btrfs_ioctl_search_header *sh;
504 unsigned long off = 0;
508 memset(&args, 0, sizeof(args));
513 * step one, we search for the inode back ref. We just use the first
516 sk->min_objectid = ino;
517 sk->max_objectid = ino;
518 sk->max_type = BTRFS_INODE_REF_KEY;
519 sk->max_offset = (u64)-1;
520 sk->min_type = BTRFS_INODE_REF_KEY;
521 sk->max_transid = (u64)-1;
524 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
527 fprintf(stderr, "ERROR: can't perform the search - %s\n",
531 /* the ioctl returns the number of item it found in nr_items */
532 if (sk->nr_items == 0)
536 sh = (struct btrfs_ioctl_search_header *)(args.buf + off);
538 if (sh->type == BTRFS_INODE_REF_KEY) {
539 struct btrfs_inode_ref *ref;
542 ref = (struct btrfs_inode_ref *)(sh + 1);
543 namelen = btrfs_stack_inode_ref_name_len(ref);
545 name = (char *)(ref + 1);
546 name = strndup(name, namelen);
548 /* use our cached value */
549 if (dirid == *cache_dirid && *cache_name) {
550 dirname = *cache_name;
557 * the inode backref gives us the file name and the parent directory id.
558 * From here we use __ino_resolve to get the path to the parent
560 dirname = __ino_resolve(fd, dirid);
562 full = build_name(dirname, name);
563 if (*cache_name && dirname != *cache_name)
566 *cache_name = dirname;
567 *cache_dirid = dirid;
573 static int get_default_subvolid(int fd, u64 *default_id)
575 struct btrfs_ioctl_search_args args;
576 struct btrfs_ioctl_search_key *sk = &args.key;
577 struct btrfs_ioctl_search_header *sh;
581 memset(&args, 0, sizeof(args));
584 * search for a dir item with a name 'default' in the tree of
585 * tree roots, it should point us to a default root
589 /* don't worry about ancient format and request only one item */
592 sk->max_objectid = BTRFS_ROOT_TREE_DIR_OBJECTID;
593 sk->min_objectid = BTRFS_ROOT_TREE_DIR_OBJECTID;
594 sk->max_type = BTRFS_DIR_ITEM_KEY;
595 sk->min_type = BTRFS_DIR_ITEM_KEY;
596 sk->max_offset = (u64)-1;
597 sk->max_transid = (u64)-1;
599 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
603 /* the ioctl returns the number of items it found in nr_items */
604 if (sk->nr_items == 0)
607 sh = (struct btrfs_ioctl_search_header *)args.buf;
609 if (sh->type == BTRFS_DIR_ITEM_KEY) {
610 struct btrfs_dir_item *di;
614 di = (struct btrfs_dir_item *)(sh + 1);
615 name_len = btrfs_stack_dir_name_len(di);
616 name = (char *)(di + 1);
618 if (!strncmp("default", name, name_len))
619 found = btrfs_disk_key_objectid(&di->location);
627 static int __list_subvol_search(int fd, struct root_lookup *root_lookup)
630 struct btrfs_ioctl_search_args args;
631 struct btrfs_ioctl_search_key *sk = &args.key;
632 struct btrfs_ioctl_search_header *sh;
633 struct btrfs_root_ref *ref;
634 struct btrfs_root_item *ri;
635 unsigned long off = 0;
644 root_lookup_init(root_lookup);
645 memset(&args, 0, sizeof(args));
647 /* search in the tree of tree roots */
651 * set the min and max to backref keys. The search will
652 * only send back this type of key now.
654 sk->max_type = BTRFS_ROOT_BACKREF_KEY;
655 sk->min_type = BTRFS_ROOT_BACKREF_KEY;
657 sk->min_objectid = BTRFS_FIRST_FREE_OBJECTID;
660 * set all the other params to the max, we'll take any objectid
663 sk->max_objectid = BTRFS_LAST_FREE_OBJECTID;
664 sk->max_offset = (u64)-1;
665 sk->max_transid = (u64)-1;
668 /* just a big number, doesn't matter much */
672 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
675 /* the ioctl returns the number of item it found in nr_items */
676 if (sk->nr_items == 0)
682 * for each item, pull the key out of the header and then
683 * read the root_ref item it contains
685 for (i = 0; i < sk->nr_items; i++) {
686 sh = (struct btrfs_ioctl_search_header *)(args.buf +
689 if (!get_gen && sh->type == BTRFS_ROOT_BACKREF_KEY) {
690 ref = (struct btrfs_root_ref *)(args.buf + off);
691 name_len = btrfs_stack_root_ref_name_len(ref);
692 name = (char *)(ref + 1);
693 dir_id = btrfs_stack_root_ref_dirid(ref);
695 add_root(root_lookup, sh->objectid, sh->offset,
696 dir_id, name, name_len);
697 } else if (get_gen && sh->type == BTRFS_ROOT_ITEM_KEY) {
698 ri = (struct btrfs_root_item *)(args.buf + off);
699 gen = btrfs_root_generation(ri);
701 update_root(root_lookup, sh->objectid, gen);
707 * record the mins in sk so we can make sure the
708 * next search doesn't repeat this root
710 sk->min_objectid = sh->objectid;
711 sk->min_type = sh->type;
712 sk->min_offset = sh->offset;
715 /* this iteration is done, step forward one root for the next
719 type = BTRFS_ROOT_ITEM_KEY;
721 type = BTRFS_ROOT_BACKREF_KEY;
723 if (sk->min_type < type) {
726 } else if (sk->min_objectid < BTRFS_LAST_FREE_OBJECTID) {
735 memset(&args, 0, sizeof(args));
738 sk->max_type = BTRFS_ROOT_ITEM_KEY;
739 sk->min_type = BTRFS_ROOT_ITEM_KEY;
741 sk->min_objectid = BTRFS_FIRST_FREE_OBJECTID;
743 sk->max_objectid = BTRFS_LAST_FREE_OBJECTID;
744 sk->max_offset = (u64)-1;
745 sk->max_transid = (u64)-1;
753 static int __list_subvol_fill_paths(int fd, struct root_lookup *root_lookup)
757 n = rb_first(&root_lookup->root);
759 struct root_info *entry;
761 entry = rb_entry(n, struct root_info, rb_node);
762 ret = lookup_ino_path(fd, entry);
771 int list_subvols(int fd, int print_parent, int get_default)
773 struct root_lookup root_lookup;
779 ret = get_default_subvolid(fd, &default_id);
781 fprintf(stderr, "ERROR: can't perform the search - %s\n",
785 if (default_id == 0) {
786 fprintf(stderr, "ERROR: 'default' dir item not found\n");
790 /* no need to resolve roots if FS_TREE is default */
791 if (default_id == BTRFS_FS_TREE_OBJECTID) {
792 printf("ID 5 (FS_TREE)\n");
797 ret = __list_subvol_search(fd, &root_lookup);
799 fprintf(stderr, "ERROR: can't perform the search - %s\n",
805 * now we have an rbtree full of root_info objects, but we need to fill
806 * in their path names within the subvol that is referencing each one.
808 ret = __list_subvol_fill_paths(fd, &root_lookup);
812 /* now that we have all the subvol-relative paths filled in,
813 * we have to string the subvols together so that we can get
814 * a path all the way back to the FS root
816 n = rb_last(&root_lookup.root);
818 struct root_info *entry;
823 entry = rb_entry(n, struct root_info, rb_node);
824 if (get_default && entry->root_id != default_id) {
829 resolve_root(&root_lookup, entry, &parent_id, &level, &path);
831 printf("ID %llu gen %llu parent %llu top level %llu path %s\n",
832 (unsigned long long)entry->root_id,
833 (unsigned long long)entry->gen,
834 (unsigned long long)parent_id,
835 (unsigned long long)level, path);
837 printf("ID %llu gen %llu top level %llu path %s\n",
838 (unsigned long long)entry->root_id,
839 (unsigned long long)entry->gen,
840 (unsigned long long)level, path);
850 static int print_one_extent(int fd, struct btrfs_ioctl_search_header *sh,
851 struct btrfs_file_extent_item *item,
852 u64 found_gen, u64 *cache_dirid,
853 char **cache_dir_name, u64 *cache_ino,
854 char **cache_full_name)
864 if (sh->objectid == *cache_ino) {
865 name = *cache_full_name;
866 } else if (*cache_full_name) {
867 free(*cache_full_name);
868 *cache_full_name = NULL;
871 name = ino_resolve(fd, sh->objectid, cache_dirid,
873 *cache_full_name = name;
874 *cache_ino = sh->objectid;
879 type = btrfs_stack_file_extent_type(item);
880 compressed = btrfs_stack_file_extent_compression(item);
882 if (type == BTRFS_FILE_EXTENT_REG ||
883 type == BTRFS_FILE_EXTENT_PREALLOC) {
884 disk_start = btrfs_stack_file_extent_disk_bytenr(item);
885 disk_offset = btrfs_stack_file_extent_offset(item);
886 len = btrfs_stack_file_extent_num_bytes(item);
887 } else if (type == BTRFS_FILE_EXTENT_INLINE) {
890 len = btrfs_stack_file_extent_ram_bytes(item);
892 printf("unhandled extent type %d for inode %llu "
893 "file offset %llu gen %llu\n",
895 (unsigned long long)sh->objectid,
896 (unsigned long long)sh->offset,
897 (unsigned long long)found_gen);
901 printf("inode %llu file offset %llu len %llu disk start %llu "
902 "offset %llu gen %llu flags ",
903 (unsigned long long)sh->objectid,
904 (unsigned long long)sh->offset,
905 (unsigned long long)len,
906 (unsigned long long)disk_start,
907 (unsigned long long)disk_offset,
908 (unsigned long long)found_gen);
914 if (type == BTRFS_FILE_EXTENT_PREALLOC) {
915 printf("%sPREALLOC", flags ? "|" : "");
918 if (type == BTRFS_FILE_EXTENT_INLINE) {
919 printf("%sINLINE", flags ? "|" : "");
925 printf(" %s\n", name);
929 int find_updated_files(int fd, u64 root_id, u64 oldest_gen)
932 struct btrfs_ioctl_search_args args;
933 struct btrfs_ioctl_search_key *sk = &args.key;
934 struct btrfs_ioctl_search_header *sh;
935 struct btrfs_file_extent_item *item;
936 unsigned long off = 0;
943 char *cache_dir_name = NULL;
944 char *cache_full_name = NULL;
945 struct btrfs_file_extent_item backup;
947 memset(&backup, 0, sizeof(backup));
948 memset(&args, 0, sizeof(args));
950 sk->tree_id = root_id;
953 * set all the other params to the max, we'll take any objectid
956 sk->max_objectid = (u64)-1;
957 sk->max_offset = (u64)-1;
958 sk->max_transid = (u64)-1;
959 sk->max_type = BTRFS_EXTENT_DATA_KEY;
960 sk->min_transid = oldest_gen;
961 /* just a big number, doesn't matter much */
964 max_found = find_root_gen(fd);
966 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
969 fprintf(stderr, "ERROR: can't perform the search- %s\n",
973 /* the ioctl returns the number of item it found in nr_items */
974 if (sk->nr_items == 0)
980 * for each item, pull the key out of the header and then
981 * read the root_ref item it contains
983 for (i = 0; i < sk->nr_items; i++) {
984 sh = (struct btrfs_ioctl_search_header *)(args.buf +
989 * just in case the item was too big, pass something other
995 item = (struct btrfs_file_extent_item *)(args.buf +
997 found_gen = btrfs_stack_file_extent_generation(item);
998 if (sh->type == BTRFS_EXTENT_DATA_KEY &&
999 found_gen >= oldest_gen) {
1000 print_one_extent(fd, sh, item, found_gen,
1001 &cache_dirid, &cache_dir_name,
1002 &cache_ino, &cache_full_name);
1007 * record the mins in sk so we can make sure the
1008 * next search doesn't repeat this root
1010 sk->min_objectid = sh->objectid;
1011 sk->min_offset = sh->offset;
1012 sk->min_type = sh->type;
1014 sk->nr_items = 4096;
1015 if (sk->min_offset < (u64)-1)
1017 else if (sk->min_objectid < (u64)-1) {
1024 free(cache_dir_name);
1025 free(cache_full_name);
1026 printf("transid marker was %llu\n", (unsigned long long)max_found);
1030 char *path_for_root(int fd, u64 root)
1032 struct root_lookup root_lookup;
1034 char *ret_path = NULL;
1037 ret = __list_subvol_search(fd, &root_lookup);
1039 return ERR_PTR(ret);
1041 ret = __list_subvol_fill_paths(fd, &root_lookup);
1043 return ERR_PTR(ret);
1045 n = rb_last(&root_lookup.root);
1047 struct root_info *entry;
1052 entry = rb_entry(n, struct root_info, rb_node);
1053 resolve_root(&root_lookup, entry, &parent_id, &level, &path);
1054 if (entry->root_id == root)