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, int print_parent)
206 char *full_path = NULL;
208 struct root_info *found;
211 * we go backwards from the root_info object and add pathnames
212 * 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 */
237 if ( parent_id == 0 ) {
241 /* if the ref_tree refers to ourselves, we're at the top */
242 if (next == found->root_id) {
248 * if the ref_tree wasn't in our tree of roots, we're
251 found = tree_search(&rl->root, next);
258 printf("ID %llu parent %llu top level %llu path %s\n",
259 (unsigned long long)ri->root_id, (unsigned long long)parent_id, (unsigned long long)top_id,
262 printf("ID %llu top level %llu path %s\n",
263 (unsigned long long)ri->root_id, (unsigned long long)top_id,
271 * for a single root_info, ask the kernel to give us a path name
272 * inside it's ref_root for the dir_id where it lives.
274 * This fills in root_info->path with the path to the directory and and
275 * appends this root's name.
277 static int lookup_ino_path(int fd, struct root_info *ri)
279 struct btrfs_ioctl_ino_lookup_args args;
285 memset(&args, 0, sizeof(args));
286 args.treeid = ri->ref_tree;
287 args.objectid = ri->dir_id;
289 ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &args);
292 fprintf(stderr, "ERROR: Failed to lookup path for root %llu - %s\n",
293 (unsigned long long)ri->ref_tree,
300 * we're in a subdirectory of ref_tree, the kernel ioctl
301 * puts a / in there for us
303 ri->path = malloc(strlen(ri->name) + strlen(args.name) + 1);
305 perror("malloc failed");
308 strcpy(ri->path, args.name);
309 strcat(ri->path, ri->name);
311 /* we're at the root of ref_tree */
312 ri->path = strdup(ri->name);
314 perror("strdup failed");
321 /* finding the generation for a given path is a two step process.
322 * First we use the inode loookup routine to find out the root id
324 * Then we use the tree search ioctl to scan all the root items for a
325 * given root id and spit out the latest generation we can find
327 static u64 find_root_gen(int fd)
329 struct btrfs_ioctl_ino_lookup_args ino_args;
331 struct btrfs_ioctl_search_args args;
332 struct btrfs_ioctl_search_key *sk = &args.key;
333 struct btrfs_ioctl_search_header *sh;
334 unsigned long off = 0;
339 memset(&ino_args, 0, sizeof(ino_args));
340 ino_args.objectid = BTRFS_FIRST_FREE_OBJECTID;
342 /* this ioctl fills in ino_args->treeid */
343 ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &ino_args);
346 fprintf(stderr, "ERROR: Failed to lookup path for dirid %llu - %s\n",
347 (unsigned long long)BTRFS_FIRST_FREE_OBJECTID,
352 memset(&args, 0, sizeof(args));
357 * there may be more than one ROOT_ITEM key if there are
358 * snapshots pending deletion, we have to loop through
361 sk->min_objectid = ino_args.treeid;
362 sk->max_objectid = ino_args.treeid;
363 sk->max_type = BTRFS_ROOT_ITEM_KEY;
364 sk->min_type = BTRFS_ROOT_ITEM_KEY;
365 sk->max_offset = (u64)-1;
366 sk->max_transid = (u64)-1;
370 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
373 fprintf(stderr, "ERROR: can't perform the search - %s\n",
377 /* the ioctl returns the number of item it found in nr_items */
378 if (sk->nr_items == 0)
382 for (i = 0; i < sk->nr_items; i++) {
383 struct btrfs_root_item *item;
384 sh = (struct btrfs_ioctl_search_header *)(args.buf +
388 item = (struct btrfs_root_item *)(args.buf + off);
391 sk->min_objectid = sh->objectid;
392 sk->min_type = sh->type;
393 sk->min_offset = sh->offset;
395 if (sh->objectid > ino_args.treeid)
398 if (sh->objectid == ino_args.treeid &&
399 sh->type == BTRFS_ROOT_ITEM_KEY) {
400 max_found = max(max_found,
401 btrfs_root_generation(item));
404 if (sk->min_offset < (u64)-1)
409 if (sk->min_type != BTRFS_ROOT_ITEM_KEY)
411 if (sk->min_objectid != BTRFS_ROOT_ITEM_KEY)
417 /* pass in a directory id and this will return
418 * the full path of the parent directory inside its
421 * It may return NULL if it is in the root, or an ERR_PTR if things
424 static char *__ino_resolve(int fd, u64 dirid)
426 struct btrfs_ioctl_ino_lookup_args args;
431 memset(&args, 0, sizeof(args));
432 args.objectid = dirid;
434 ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &args);
437 fprintf(stderr, "ERROR: Failed to lookup path for dirid %llu - %s\n",
438 (unsigned long long)dirid, strerror(e) );
444 * we're in a subdirectory of ref_tree, the kernel ioctl
445 * puts a / in there for us
447 full = strdup(args.name);
449 perror("malloc failed");
450 return ERR_PTR(-ENOMEM);
453 /* we're at the root of ref_tree */
460 * simple string builder, returning a new string with both
463 char *build_name(char *dirid, char *name)
469 full = malloc(strlen(dirid) + strlen(name) + 1);
478 * given an inode number, this returns the full path name inside the subvolume
479 * to that file/directory. cache_dirid and cache_name are used to
480 * cache the results so we can avoid tree searches if a later call goes
481 * to the same directory or file name
483 static char *ino_resolve(int fd, u64 ino, u64 *cache_dirid, char **cache_name)
491 struct btrfs_ioctl_search_args args;
492 struct btrfs_ioctl_search_key *sk = &args.key;
493 struct btrfs_ioctl_search_header *sh;
494 unsigned long off = 0;
498 memset(&args, 0, sizeof(args));
503 * step one, we search for the inode back ref. We just use the first
506 sk->min_objectid = ino;
507 sk->max_objectid = ino;
508 sk->max_type = BTRFS_INODE_REF_KEY;
509 sk->max_offset = (u64)-1;
510 sk->min_type = BTRFS_INODE_REF_KEY;
511 sk->max_transid = (u64)-1;
514 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
517 fprintf(stderr, "ERROR: can't perform the search - %s\n",
521 /* the ioctl returns the number of item it found in nr_items */
522 if (sk->nr_items == 0)
526 sh = (struct btrfs_ioctl_search_header *)(args.buf + off);
528 if (sh->type == BTRFS_INODE_REF_KEY) {
529 struct btrfs_inode_ref *ref;
532 ref = (struct btrfs_inode_ref *)(sh + 1);
533 namelen = btrfs_stack_inode_ref_name_len(ref);
535 name = (char *)(ref + 1);
536 name = strndup(name, namelen);
538 /* use our cached value */
539 if (dirid == *cache_dirid && *cache_name) {
540 dirname = *cache_name;
547 * the inode backref gives us the file name and the parent directory id.
548 * From here we use __ino_resolve to get the path to the parent
550 dirname = __ino_resolve(fd, dirid);
552 full = build_name(dirname, name);
553 if (*cache_name && dirname != *cache_name)
556 *cache_name = dirname;
557 *cache_dirid = dirid;
563 int list_subvols(int fd, int print_parent, int get_default)
565 struct root_lookup root_lookup;
568 struct btrfs_ioctl_search_args args;
569 struct btrfs_ioctl_search_key *sk = &args.key;
570 struct btrfs_ioctl_search_header *sh;
571 struct btrfs_root_ref *ref;
572 struct btrfs_dir_item *di;
573 unsigned long off = 0;
581 root_lookup_init(&root_lookup);
583 memset(&args, 0, sizeof(args));
585 /* search in the tree of tree roots */
589 * set the min and max to backref keys. The search will
590 * only send back this type of key now.
592 sk->max_type = BTRFS_ROOT_BACKREF_KEY;
593 sk->min_type = BTRFS_ROOT_BACKREF_KEY;
596 * set all the other params to the max, we'll take any objectid
599 sk->max_objectid = (u64)-1;
600 sk->max_offset = (u64)-1;
601 sk->max_transid = (u64)-1;
603 /* just a big number, doesn't matter much */
607 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
610 fprintf(stderr, "ERROR: can't perform the search - %s\n",
614 /* the ioctl returns the number of item it found in nr_items */
615 if (sk->nr_items == 0)
621 * for each item, pull the key out of the header and then
622 * read the root_ref item it contains
624 for (i = 0; i < sk->nr_items; i++) {
625 sh = (struct btrfs_ioctl_search_header *)(args.buf +
628 if (sh->type == BTRFS_ROOT_BACKREF_KEY) {
629 ref = (struct btrfs_root_ref *)(args.buf + off);
630 name_len = btrfs_stack_root_ref_name_len(ref);
631 name = (char *)(ref + 1);
632 dir_id = btrfs_stack_root_ref_dirid(ref);
634 add_root(&root_lookup, sh->objectid, sh->offset,
635 dir_id, name, name_len);
641 * record the mins in sk so we can make sure the
642 * next search doesn't repeat this root
644 sk->min_objectid = sh->objectid;
645 sk->min_type = sh->type;
646 sk->min_offset = sh->offset;
649 /* this iteration is done, step forward one root for the next
652 if (sk->min_objectid < (u64)-1) {
654 sk->min_type = BTRFS_ROOT_BACKREF_KEY;
660 * now we have an rbtree full of root_info objects, but we need to fill
661 * in their path names within the subvol that is referencing each one.
663 n = rb_first(&root_lookup.root);
665 struct root_info *entry;
667 entry = rb_entry(n, struct root_info, rb_node);
668 ret = lookup_ino_path(fd, entry);
674 memset(&args, 0, sizeof(args));
676 /* search in the tree of tree roots */
677 sk->tree_id = BTRFS_ROOT_TREE_OBJECTID;
679 /* search dir item */
680 sk->max_type = BTRFS_DIR_ITEM_KEY;
681 sk->min_type = BTRFS_DIR_ITEM_KEY;
683 sk->max_objectid = BTRFS_ROOT_TREE_DIR_OBJECTID;
684 sk->min_objectid = BTRFS_ROOT_TREE_DIR_OBJECTID;
685 sk->max_offset = (u64)-1;
686 sk->max_transid = (u64)-1;
688 /* just a big number, doesn't matter much */
691 /* try to get the objectid of default subvolume */
693 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
695 fprintf(stderr, "ERROR: can't perform the search\n");
700 /* go through each item to find dir item named "default" */
701 for (i = 0; i < sk->nr_items; i++) {
702 sh = (struct btrfs_ioctl_search_header *)(args.buf +
705 if (sh->type == BTRFS_DIR_ITEM_KEY) {
706 di = (struct btrfs_dir_item *)(args.buf + off);
707 name_len = le16_to_cpu(di->name_len);
708 name = (char *)di + sizeof(struct btrfs_dir_item);
709 if (!strncmp("default", name, name_len)) {
710 subvol_id = btrfs_disk_key_objectid(
720 /* now that we have all the subvol-relative paths filled in,
721 * we have to string the subvols together so that we can get
722 * a path all the way back to the FS root
724 n = rb_last(&root_lookup.root);
726 struct root_info *entry;
727 entry = rb_entry(n, struct root_info, rb_node);
729 resolve_root(&root_lookup, entry, print_parent);
730 /* we only want the default subvolume */
731 else if (subvol_id == entry->root_id)
732 resolve_root(&root_lookup, entry, print_parent);
733 else if (subvol_id == 0)
741 static int print_one_extent(int fd, struct btrfs_ioctl_search_header *sh,
742 struct btrfs_file_extent_item *item,
743 u64 found_gen, u64 *cache_dirid,
744 char **cache_dir_name, u64 *cache_ino,
745 char **cache_full_name)
755 if (sh->objectid == *cache_ino) {
756 name = *cache_full_name;
757 } else if (*cache_full_name) {
758 free(*cache_full_name);
759 *cache_full_name = NULL;
762 name = ino_resolve(fd, sh->objectid, cache_dirid,
764 *cache_full_name = name;
765 *cache_ino = sh->objectid;
770 type = btrfs_stack_file_extent_type(item);
771 compressed = btrfs_stack_file_extent_compression(item);
773 if (type == BTRFS_FILE_EXTENT_REG ||
774 type == BTRFS_FILE_EXTENT_PREALLOC) {
775 disk_start = btrfs_stack_file_extent_disk_bytenr(item);
776 disk_offset = btrfs_stack_file_extent_offset(item);
777 len = btrfs_stack_file_extent_num_bytes(item);
778 } else if (type == BTRFS_FILE_EXTENT_INLINE) {
781 len = btrfs_stack_file_extent_ram_bytes(item);
783 printf("unhandled extent type %d for inode %llu "
784 "file offset %llu gen %llu\n",
786 (unsigned long long)sh->objectid,
787 (unsigned long long)sh->offset,
788 (unsigned long long)found_gen);
792 printf("inode %llu file offset %llu len %llu disk start %llu "
793 "offset %llu gen %llu flags ",
794 (unsigned long long)sh->objectid,
795 (unsigned long long)sh->offset,
796 (unsigned long long)len,
797 (unsigned long long)disk_start,
798 (unsigned long long)disk_offset,
799 (unsigned long long)found_gen);
805 if (type == BTRFS_FILE_EXTENT_PREALLOC) {
806 printf("%sPREALLOC", flags ? "|" : "");
809 if (type == BTRFS_FILE_EXTENT_INLINE) {
810 printf("%sINLINE", flags ? "|" : "");
816 printf(" %s\n", name);
820 int find_updated_files(int fd, u64 root_id, u64 oldest_gen)
823 struct btrfs_ioctl_search_args args;
824 struct btrfs_ioctl_search_key *sk = &args.key;
825 struct btrfs_ioctl_search_header *sh;
826 struct btrfs_file_extent_item *item;
827 unsigned long off = 0;
834 char *cache_dir_name = NULL;
835 char *cache_full_name = NULL;
836 struct btrfs_file_extent_item backup;
838 memset(&backup, 0, sizeof(backup));
839 memset(&args, 0, sizeof(args));
841 sk->tree_id = root_id;
844 * set all the other params to the max, we'll take any objectid
847 sk->max_objectid = (u64)-1;
848 sk->max_offset = (u64)-1;
849 sk->max_transid = (u64)-1;
850 sk->max_type = BTRFS_EXTENT_DATA_KEY;
851 sk->min_transid = oldest_gen;
852 /* just a big number, doesn't matter much */
855 max_found = find_root_gen(fd);
857 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
860 fprintf(stderr, "ERROR: can't perform the search- %s\n",
864 /* the ioctl returns the number of item it found in nr_items */
865 if (sk->nr_items == 0)
871 * for each item, pull the key out of the header and then
872 * read the root_ref item it contains
874 for (i = 0; i < sk->nr_items; i++) {
875 sh = (struct btrfs_ioctl_search_header *)(args.buf +
880 * just in case the item was too big, pass something other
886 item = (struct btrfs_file_extent_item *)(args.buf +
888 found_gen = btrfs_stack_file_extent_generation(item);
889 if (sh->type == BTRFS_EXTENT_DATA_KEY &&
890 found_gen >= oldest_gen) {
891 print_one_extent(fd, sh, item, found_gen,
892 &cache_dirid, &cache_dir_name,
893 &cache_ino, &cache_full_name);
898 * record the mins in sk so we can make sure the
899 * next search doesn't repeat this root
901 sk->min_objectid = sh->objectid;
902 sk->min_offset = sh->offset;
903 sk->min_type = sh->type;
906 if (sk->min_offset < (u64)-1)
908 else if (sk->min_objectid < (u64)-1) {
915 free(cache_dir_name);
916 free(cache_full_name);
917 printf("transid marker was %llu\n", (unsigned long long)max_found);