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"
39 /* we store all the roots we find in an rbtree so that we can
40 * search for them later.
47 * one of these for each root we find.
50 struct rb_node rb_node;
55 /* the id of the root that references this one */
58 /* the dir id we're in from ref_tree */
61 /* path from the subvol we live in to this root, including the
62 * root's name. This is null until we do the extra lookup ioctl.
66 /* the name of this root in the directory it lives in */
70 static void root_lookup_init(struct root_lookup *tree)
72 tree->root.rb_node = NULL;
75 static int comp_entry(struct root_info *entry, u64 root_id, u64 ref_tree)
77 if (entry->root_id > root_id)
79 if (entry->root_id < root_id)
81 if (entry->ref_tree > ref_tree)
83 if (entry->ref_tree < ref_tree)
89 * insert a new root into the tree. returns the existing root entry
90 * if one is already there. Both root_id and ref_tree are used
93 static struct rb_node *tree_insert(struct rb_root *root, u64 root_id,
94 u64 ref_tree, struct rb_node *node)
96 struct rb_node ** p = &root->rb_node;
97 struct rb_node * parent = NULL;
98 struct root_info *entry;
103 entry = rb_entry(parent, struct root_info, rb_node);
105 comp = comp_entry(entry, root_id, ref_tree);
115 entry = rb_entry(parent, struct root_info, rb_node);
116 rb_link_node(node, parent, p);
117 rb_insert_color(node, root);
122 * find a given root id in the tree. We return the smallest one,
123 * rb_next can be used to move forward looking for more if required
125 static struct root_info *tree_search(struct rb_root *root, u64 root_id)
127 struct rb_node * n = root->rb_node;
128 struct root_info *entry;
131 entry = rb_entry(n, struct root_info, rb_node);
133 if (entry->root_id < root_id)
135 else if (entry->root_id > root_id)
138 struct root_info *prev;
139 struct rb_node *prev_n;
144 prev = rb_entry(prev_n, struct root_info,
146 if (prev->root_id != root_id)
158 * this allocates a new root in the lookup tree.
160 * root_id should be the object id of the root
162 * ref_tree is the objectid of the referring root.
164 * dir_id is the directory in ref_tree where this root_id can be found.
166 * name is the name of root_id in that directory
168 * name_len is the length of name
170 static int add_root(struct root_lookup *root_lookup,
171 u64 root_id, u64 ref_tree, u64 dir_id, char *name,
174 struct root_info *ri;
176 ri = malloc(sizeof(*ri) + name_len + 1);
178 printf("memory allocation failed\n");
181 memset(ri, 0, sizeof(*ri) + name_len + 1);
184 ri->root_id = root_id;
185 ri->ref_tree = ref_tree;
186 strncpy(ri->name, name, name_len);
188 ret = tree_insert(&root_lookup->root, root_id, ref_tree, &ri->rb_node);
190 printf("failed to insert tree %llu\n", (unsigned long long)root_id);
197 * for a given root_info, search through the root_lookup tree to construct
198 * the full path name to it.
200 * This can't be called until all the root_info->path fields are filled
201 * in by lookup_ino_path
203 static int resolve_root(struct root_lookup *rl, struct root_info *ri)
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 /* if the ref_tree refers to ourselves, we're at the top */
237 if (next == found->root_id) {
243 * if the ref_tree wasn't in our tree of roots, we're
246 found = tree_search(&rl->root, next);
252 printf("ID %llu top level %llu path %s\n",
253 (unsigned long long)ri->root_id, (unsigned long long)top_id,
260 * for a single root_info, ask the kernel to give us a path name
261 * inside it's ref_root for the dir_id where it lives.
263 * This fills in root_info->path with the path to the directory and and
264 * appends this root's name.
266 static int lookup_ino_path(int fd, struct root_info *ri)
268 struct btrfs_ioctl_ino_lookup_args args;
274 memset(&args, 0, sizeof(args));
275 args.treeid = ri->ref_tree;
276 args.objectid = ri->dir_id;
278 ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &args);
281 fprintf(stderr, "ERROR: Failed to lookup path for root %llu - %s\n",
282 (unsigned long long)ri->ref_tree,
289 * we're in a subdirectory of ref_tree, the kernel ioctl
290 * puts a / in there for us
292 ri->path = malloc(strlen(ri->name) + strlen(args.name) + 1);
294 perror("malloc failed");
297 strcpy(ri->path, args.name);
298 strcat(ri->path, ri->name);
300 /* we're at the root of ref_tree */
301 ri->path = strdup(ri->name);
303 perror("strdup failed");
310 /* finding the generation for a given path is a two step process.
311 * First we use the inode loookup routine to find out the root id
313 * Then we use the tree search ioctl to scan all the root items for a
314 * given root id and spit out the latest generation we can find
316 static u64 find_root_gen(int fd)
318 struct btrfs_ioctl_ino_lookup_args ino_args;
320 struct btrfs_ioctl_search_args args;
321 struct btrfs_ioctl_search_key *sk = &args.key;
322 struct btrfs_ioctl_search_header *sh;
323 unsigned long off = 0;
328 memset(&ino_args, 0, sizeof(ino_args));
329 ino_args.objectid = BTRFS_FIRST_FREE_OBJECTID;
331 /* this ioctl fills in ino_args->treeid */
332 ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &ino_args);
335 fprintf(stderr, "ERROR: Failed to lookup path for dirid %llu - %s\n",
336 (unsigned long long)BTRFS_FIRST_FREE_OBJECTID,
341 memset(&args, 0, sizeof(args));
346 * there may be more than one ROOT_ITEM key if there are
347 * snapshots pending deletion, we have to loop through
350 sk->min_objectid = ino_args.treeid;
351 sk->max_objectid = ino_args.treeid;
352 sk->max_type = BTRFS_ROOT_ITEM_KEY;
353 sk->min_type = BTRFS_ROOT_ITEM_KEY;
354 sk->max_offset = (u64)-1;
355 sk->max_transid = (u64)-1;
359 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
362 fprintf(stderr, "ERROR: can't perform the search - %s\n",
366 /* the ioctl returns the number of item it found in nr_items */
367 if (sk->nr_items == 0)
371 for (i = 0; i < sk->nr_items; i++) {
372 struct btrfs_root_item *item;
373 sh = (struct btrfs_ioctl_search_header *)(args.buf +
377 item = (struct btrfs_root_item *)(args.buf + off);
380 sk->min_objectid = sh->objectid;
381 sk->min_type = sh->type;
382 sk->min_offset = sh->offset;
384 if (sh->objectid > ino_args.treeid)
387 if (sh->objectid == ino_args.treeid &&
388 sh->type == BTRFS_ROOT_ITEM_KEY) {
389 max_found = max(max_found,
390 btrfs_root_generation(item));
393 if (sk->min_offset < (u64)-1)
398 if (sk->min_type != BTRFS_ROOT_ITEM_KEY)
400 if (sk->min_objectid != BTRFS_ROOT_ITEM_KEY)
406 /* pass in a directory id and this will return
407 * the full path of the parent directory inside its
410 * It may return NULL if it is in the root, or an ERR_PTR if things
413 static char *__ino_resolve(int fd, u64 dirid)
415 struct btrfs_ioctl_ino_lookup_args args;
420 memset(&args, 0, sizeof(args));
421 args.objectid = dirid;
423 ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &args);
426 fprintf(stderr, "ERROR: Failed to lookup path for dirid %llu - %s\n",
427 (unsigned long long)dirid, strerror(e) );
433 * we're in a subdirectory of ref_tree, the kernel ioctl
434 * puts a / in there for us
436 full = strdup(args.name);
438 perror("malloc failed");
439 return ERR_PTR(-ENOMEM);
442 /* we're at the root of ref_tree */
449 * simple string builder, returning a new string with both
452 char *build_name(char *dirid, char *name)
458 full = malloc(strlen(dirid) + strlen(name) + 1);
467 * given an inode number, this returns the full path name inside the subvolume
468 * to that file/directory. cache_dirid and cache_name are used to
469 * cache the results so we can avoid tree searches if a later call goes
470 * to the same directory or file name
472 static char *ino_resolve(int fd, u64 ino, u64 *cache_dirid, char **cache_name)
480 struct btrfs_ioctl_search_args args;
481 struct btrfs_ioctl_search_key *sk = &args.key;
482 struct btrfs_ioctl_search_header *sh;
483 unsigned long off = 0;
487 memset(&args, 0, sizeof(args));
492 * step one, we search for the inode back ref. We just use the first
495 sk->min_objectid = ino;
496 sk->max_objectid = ino;
497 sk->max_type = BTRFS_INODE_REF_KEY;
498 sk->max_offset = (u64)-1;
499 sk->min_type = BTRFS_INODE_REF_KEY;
500 sk->max_transid = (u64)-1;
503 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
506 fprintf(stderr, "ERROR: can't perform the search - %s\n",
510 /* the ioctl returns the number of item it found in nr_items */
511 if (sk->nr_items == 0)
515 sh = (struct btrfs_ioctl_search_header *)(args.buf + off);
517 if (sh->type == BTRFS_INODE_REF_KEY) {
518 struct btrfs_inode_ref *ref;
521 ref = (struct btrfs_inode_ref *)(sh + 1);
522 namelen = btrfs_stack_inode_ref_name_len(ref);
524 name = (char *)(ref + 1);
525 name = strndup(name, namelen);
527 /* use our cached value */
528 if (dirid == *cache_dirid && *cache_name) {
529 dirname = *cache_name;
536 * the inode backref gives us the file name and the parent directory id.
537 * From here we use __ino_resolve to get the path to the parent
539 dirname = __ino_resolve(fd, dirid);
541 full = build_name(dirname, name);
542 if (*cache_name && dirname != *cache_name)
545 *cache_name = dirname;
546 *cache_dirid = dirid;
552 int list_subvols(int fd)
554 struct root_lookup root_lookup;
557 struct btrfs_ioctl_search_args args;
558 struct btrfs_ioctl_search_key *sk = &args.key;
559 struct btrfs_ioctl_search_header *sh;
560 struct btrfs_root_ref *ref;
561 unsigned long off = 0;
568 root_lookup_init(&root_lookup);
570 memset(&args, 0, sizeof(args));
572 /* search in the tree of tree roots */
576 * set the min and max to backref keys. The search will
577 * only send back this type of key now.
579 sk->max_type = BTRFS_ROOT_BACKREF_KEY;
580 sk->min_type = BTRFS_ROOT_BACKREF_KEY;
583 * set all the other params to the max, we'll take any objectid
586 sk->max_objectid = (u64)-1;
587 sk->max_offset = (u64)-1;
588 sk->max_transid = (u64)-1;
590 /* just a big number, doesn't matter much */
594 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
597 fprintf(stderr, "ERROR: can't perform the search - %s\n",
601 /* the ioctl returns the number of item it found in nr_items */
602 if (sk->nr_items == 0)
608 * for each item, pull the key out of the header and then
609 * read the root_ref item it contains
611 for (i = 0; i < sk->nr_items; i++) {
612 sh = (struct btrfs_ioctl_search_header *)(args.buf +
615 if (sh->type == BTRFS_ROOT_BACKREF_KEY) {
616 ref = (struct btrfs_root_ref *)(args.buf + off);
617 name_len = btrfs_stack_root_ref_name_len(ref);
618 name = (char *)(ref + 1);
619 dir_id = btrfs_stack_root_ref_dirid(ref);
621 add_root(&root_lookup, sh->objectid, sh->offset,
622 dir_id, name, name_len);
628 * record the mins in sk so we can make sure the
629 * next search doesn't repeat this root
631 sk->min_objectid = sh->objectid;
632 sk->min_type = sh->type;
633 sk->min_offset = sh->offset;
636 /* this iteration is done, step forward one root for the next
639 if (sk->min_objectid < (u64)-1) {
641 sk->min_type = BTRFS_ROOT_BACKREF_KEY;
647 * now we have an rbtree full of root_info objects, but we need to fill
648 * in their path names within the subvol that is referencing each one.
650 n = rb_first(&root_lookup.root);
652 struct root_info *entry;
654 entry = rb_entry(n, struct root_info, rb_node);
655 ret = lookup_ino_path(fd, entry);
661 /* now that we have all the subvol-relative paths filled in,
662 * we have to string the subvols together so that we can get
663 * a path all the way back to the FS root
665 n = rb_last(&root_lookup.root);
667 struct root_info *entry;
668 entry = rb_entry(n, struct root_info, rb_node);
669 resolve_root(&root_lookup, entry);
676 static int print_one_extent(int fd, struct btrfs_ioctl_search_header *sh,
677 struct btrfs_file_extent_item *item,
678 u64 found_gen, u64 *cache_dirid,
679 char **cache_dir_name, u64 *cache_ino,
680 char **cache_full_name)
690 if (sh->objectid == *cache_ino) {
691 name = *cache_full_name;
692 } else if (*cache_full_name) {
693 free(*cache_full_name);
694 *cache_full_name = NULL;
697 name = ino_resolve(fd, sh->objectid, cache_dirid,
699 *cache_full_name = name;
700 *cache_ino = sh->objectid;
705 type = btrfs_stack_file_extent_type(item);
706 compressed = btrfs_stack_file_extent_compression(item);
708 if (type == BTRFS_FILE_EXTENT_REG ||
709 type == BTRFS_FILE_EXTENT_PREALLOC) {
710 disk_start = btrfs_stack_file_extent_disk_bytenr(item);
711 disk_offset = btrfs_stack_file_extent_offset(item);
712 len = btrfs_stack_file_extent_num_bytes(item);
713 } else if (type == BTRFS_FILE_EXTENT_INLINE) {
716 len = btrfs_stack_file_extent_ram_bytes(item);
718 printf("unhandled extent type %d for inode %llu "
719 "file offset %llu gen %llu\n",
721 (unsigned long long)sh->objectid,
722 (unsigned long long)sh->offset,
723 (unsigned long long)found_gen);
727 printf("inode %llu file offset %llu len %llu disk start %llu "
728 "offset %llu gen %llu flags ",
729 (unsigned long long)sh->objectid,
730 (unsigned long long)sh->offset,
731 (unsigned long long)len,
732 (unsigned long long)disk_start,
733 (unsigned long long)disk_offset,
734 (unsigned long long)found_gen);
740 if (type == BTRFS_FILE_EXTENT_PREALLOC) {
741 printf("%sPREALLOC", flags ? "|" : "");
744 if (type == BTRFS_FILE_EXTENT_INLINE) {
745 printf("%sINLINE", flags ? "|" : "");
751 printf(" %s\n", name);
755 int find_updated_files(int fd, u64 root_id, u64 oldest_gen)
758 struct btrfs_ioctl_search_args args;
759 struct btrfs_ioctl_search_key *sk = &args.key;
760 struct btrfs_ioctl_search_header *sh;
761 struct btrfs_file_extent_item *item;
762 unsigned long off = 0;
769 char *cache_dir_name = NULL;
770 char *cache_full_name = NULL;
771 struct btrfs_file_extent_item backup;
773 memset(&backup, 0, sizeof(backup));
774 memset(&args, 0, sizeof(args));
776 sk->tree_id = root_id;
779 * set all the other params to the max, we'll take any objectid
782 sk->max_objectid = (u64)-1;
783 sk->max_offset = (u64)-1;
784 sk->max_transid = (u64)-1;
785 sk->max_type = BTRFS_EXTENT_DATA_KEY;
786 sk->min_transid = oldest_gen;
787 /* just a big number, doesn't matter much */
790 max_found = find_root_gen(fd);
792 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
795 fprintf(stderr, "ERROR: can't perform the search- %s\n",
799 /* the ioctl returns the number of item it found in nr_items */
800 if (sk->nr_items == 0)
806 * for each item, pull the key out of the header and then
807 * read the root_ref item it contains
809 for (i = 0; i < sk->nr_items; i++) {
810 sh = (struct btrfs_ioctl_search_header *)(args.buf +
815 * just in case the item was too big, pass something other
821 item = (struct btrfs_file_extent_item *)(args.buf +
823 found_gen = btrfs_stack_file_extent_generation(item);
824 if (sh->type == BTRFS_EXTENT_DATA_KEY &&
825 found_gen >= oldest_gen) {
826 print_one_extent(fd, sh, item, found_gen,
827 &cache_dirid, &cache_dir_name,
828 &cache_ino, &cache_full_name);
833 * record the mins in sk so we can make sure the
834 * next search doesn't repeat this root
836 sk->min_objectid = sh->objectid;
837 sk->min_offset = sh->offset;
838 sk->min_type = sh->type;
841 if (sk->min_offset < (u64)-1)
843 else if (sk->min_objectid < (u64)-1) {
850 free(cache_dir_name);
851 free(cache_full_name);
852 printf("transid marker was %llu\n", (unsigned long long)max_found);