btrfs-debug-tree: add -d option to print only the device mapping
[btrfs-progs-unstable.git] / btrfs-list.c
blob93766a806d9b78d2df3ea851b321c7817a159a9f
1 /*
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 #define _GNU_SOURCE
20 #ifndef __CHECKER__
21 #include <sys/ioctl.h>
22 #include <sys/mount.h>
23 #include "ioctl.h"
24 #endif
25 #include <stdio.h>
26 #include <stdlib.h>
27 #include <sys/types.h>
28 #include <sys/stat.h>
29 #include <fcntl.h>
30 #include <unistd.h>
31 #include <dirent.h>
32 #include <libgen.h>
33 #include "kerncompat.h"
34 #include "ctree.h"
35 #include "transaction.h"
36 #include "utils.h"
37 #include "version.h"
39 /* we store all the roots we find in an rbtree so that we can
40 * search for them later.
42 struct root_lookup {
43 struct rb_root root;
47 * one of these for each root we find.
49 struct root_info {
50 struct rb_node rb_node;
52 /* this root's id */
53 u64 root_id;
55 /* the id of the root that references this one */
56 u64 ref_tree;
58 /* the dir id we're in from ref_tree */
59 u64 dir_id;
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.
64 char *path;
66 /* the name of this root in the directory it lives in */
67 char name[];
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)
78 return 1;
79 if (entry->root_id < root_id)
80 return -1;
81 if (entry->ref_tree > ref_tree)
82 return 1;
83 if (entry->ref_tree < ref_tree)
84 return -1;
85 return 0;
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
91 * as the key
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;
99 int comp;
101 while(*p) {
102 parent = *p;
103 entry = rb_entry(parent, struct root_info, rb_node);
105 comp = comp_entry(entry, root_id, ref_tree);
107 if (comp < 0)
108 p = &(*p)->rb_left;
109 else if (comp > 0)
110 p = &(*p)->rb_right;
111 else
112 return parent;
115 entry = rb_entry(parent, struct root_info, rb_node);
116 rb_link_node(node, parent, p);
117 rb_insert_color(node, root);
118 return NULL;
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;
130 while(n) {
131 entry = rb_entry(n, struct root_info, rb_node);
133 if (entry->root_id < root_id)
134 n = n->rb_left;
135 else if (entry->root_id > root_id)
136 n = n->rb_right;
137 else {
138 struct root_info *prev;
139 struct rb_node *prev_n;
140 while (1) {
141 prev_n = rb_prev(n);
142 if (!prev_n)
143 break;
144 prev = rb_entry(prev_n, struct root_info,
145 rb_node);
146 if (prev->root_id != root_id)
147 break;
148 entry = prev;
149 n = prev_n;
151 return entry;
154 return NULL;
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,
172 int name_len)
174 struct root_info *ri;
175 struct rb_node *ret;
176 ri = malloc(sizeof(*ri) + name_len + 1);
177 if (!ri) {
178 printf("memory allocation failed\n");
179 exit(1);
181 memset(ri, 0, sizeof(*ri) + name_len + 1);
182 ri->path = NULL;
183 ri->dir_id = dir_id;
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);
189 if (ret) {
190 printf("failed to insert tree %llu\n", (unsigned long long)root_id);
191 exit(1);
193 return 0;
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)
205 u64 top_id;
206 char *full_path = NULL;
207 int len = 0;
208 struct root_info *found;
211 * we go backwards from the root_info object and add pathnames
212 * from parent directories as we go.
214 found = ri;
215 while (1) {
216 char *tmp;
217 u64 next;
218 int add_len = strlen(found->path);
220 /* room for / and for null */
221 tmp = malloc(add_len + 2 + len);
222 if (full_path) {
223 memcpy(tmp + add_len + 1, full_path, len);
224 tmp[add_len] = '/';
225 memcpy(tmp, found->path, add_len);
226 tmp [add_len + len + 1] = '\0';
227 free(full_path);
228 full_path = tmp;
229 len += add_len + 1;
230 } else {
231 full_path = strdup(found->path);
232 len = add_len;
235 next = found->ref_tree;
236 /* if the ref_tree refers to ourselves, we're at the top */
237 if (next == found->root_id) {
238 top_id = next;
239 break;
243 * if the ref_tree wasn't in our tree of roots, we're
244 * at the top
246 found = tree_search(&rl->root, next);
247 if (!found) {
248 top_id = next;
249 break;
252 printf("ID %llu top level %llu path %s\n", ri->root_id, top_id,
253 full_path);
254 free(full_path);
255 return 0;
259 * for a single root_info, ask the kernel to give us a path name
260 * inside it's ref_root for the dir_id where it lives.
262 * This fills in root_info->path with the path to the directory and and
263 * appends this root's name.
265 static int lookup_ino_path(int fd, struct root_info *ri)
267 struct btrfs_ioctl_ino_lookup_args args;
268 int ret;
270 if (ri->path)
271 return 0;
273 memset(&args, 0, sizeof(args));
274 args.treeid = ri->ref_tree;
275 args.objectid = ri->dir_id;
277 ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &args);
278 if (ret) {
279 fprintf(stderr, "ERROR: Failed to lookup path for root %llu\n",
280 (unsigned long long)ri->ref_tree);
281 return ret;
284 if (args.name[0]) {
286 * we're in a subdirectory of ref_tree, the kernel ioctl
287 * puts a / in there for us
289 ri->path = malloc(strlen(ri->name) + strlen(args.name) + 1);
290 if (!ri->path) {
291 perror("malloc failed");
292 exit(1);
294 strcpy(ri->path, args.name);
295 strcat(ri->path, ri->name);
296 } else {
297 /* we're at the root of ref_tree */
298 ri->path = strdup(ri->name);
299 if (!ri->path) {
300 perror("strdup failed");
301 exit(1);
304 return 0;
307 /* finding the generation for a given path is a two step process.
308 * First we use the inode loookup routine to find out the root id
310 * Then we use the tree search ioctl to scan all the root items for a
311 * given root id and spit out the latest generation we can find
313 static u64 find_root_gen(int fd)
315 struct btrfs_ioctl_ino_lookup_args ino_args;
316 int ret;
317 struct btrfs_ioctl_search_args args;
318 struct btrfs_ioctl_search_key *sk = &args.key;
319 struct btrfs_ioctl_search_header *sh;
320 unsigned long off = 0;
321 u64 max_found = 0;
322 int i;
324 memset(&ino_args, 0, sizeof(ino_args));
325 ino_args.objectid = BTRFS_FIRST_FREE_OBJECTID;
327 /* this ioctl fills in ino_args->treeid */
328 ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &ino_args);
329 if (ret) {
330 fprintf(stderr, "ERROR: Failed to lookup path for dirid %llu\n",
331 (unsigned long long)BTRFS_FIRST_FREE_OBJECTID);
332 return 0;
335 memset(&args, 0, sizeof(args));
337 sk->tree_id = 1;
340 * there may be more than one ROOT_ITEM key if there are
341 * snapshots pending deletion, we have to loop through
342 * them.
344 sk->min_objectid = ino_args.treeid;
345 sk->max_objectid = ino_args.treeid;
346 sk->max_type = BTRFS_ROOT_ITEM_KEY;
347 sk->min_type = BTRFS_ROOT_ITEM_KEY;
348 sk->max_offset = (u64)-1;
349 sk->max_transid = (u64)-1;
350 sk->nr_items = 4096;
352 while (1) {
353 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
354 if (ret < 0) {
355 fprintf(stderr, "ERROR: can't perform the search\n");
356 return 0;
358 /* the ioctl returns the number of item it found in nr_items */
359 if (sk->nr_items == 0)
360 break;
362 off = 0;
363 for (i = 0; i < sk->nr_items; i++) {
364 struct btrfs_root_item *item;
365 sh = (struct btrfs_ioctl_search_header *)(args.buf +
366 off);
368 off += sizeof(*sh);
369 item = (struct btrfs_root_item *)(args.buf + off);
370 off += sh->len;
372 sk->min_objectid = sh->objectid;
373 sk->min_type = sh->type;
374 sk->min_offset = sh->offset;
376 if (sh->objectid > ino_args.treeid)
377 break;
379 if (sh->objectid == ino_args.treeid &&
380 sh->type == BTRFS_ROOT_ITEM_KEY) {
381 max_found = max(max_found,
382 btrfs_root_generation(item));
385 if (sk->min_offset < (u64)-1)
386 sk->min_offset++;
387 else
388 break;
390 if (sk->min_type != BTRFS_ROOT_ITEM_KEY)
391 break;
392 if (sk->min_objectid != BTRFS_ROOT_ITEM_KEY)
393 break;
395 return max_found;
398 /* pass in a directory id and this will return
399 * the full path of the parent directory inside its
400 * subvolume root.
402 * It may return NULL if it is in the root, or an ERR_PTR if things
403 * go badly.
405 static char *__ino_resolve(int fd, u64 dirid)
407 struct btrfs_ioctl_ino_lookup_args args;
408 int ret;
409 char *full;
411 memset(&args, 0, sizeof(args));
412 args.objectid = dirid;
414 ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &args);
415 if (ret) {
416 fprintf(stderr, "ERROR: Failed to lookup path for dirid %llu\n",
417 (unsigned long long)dirid);
418 return ERR_PTR(ret);
421 if (args.name[0]) {
423 * we're in a subdirectory of ref_tree, the kernel ioctl
424 * puts a / in there for us
426 full = strdup(args.name);
427 if (!full) {
428 perror("malloc failed");
429 return ERR_PTR(-ENOMEM);
431 } else {
432 /* we're at the root of ref_tree */
433 full = NULL;
435 return full;
439 * simple string builder, returning a new string with both
440 * dirid and name
442 char *build_name(char *dirid, char *name)
444 char *full;
445 if (!dirid)
446 return strdup(name);
448 full = malloc(strlen(dirid) + strlen(name) + 1);
449 if (!full)
450 return NULL;
451 strcpy(full, dirid);
452 strcat(full, name);
453 return full;
457 * given an inode number, this returns the full path name inside the subvolume
458 * to that file/directory. cache_dirid and cache_name are used to
459 * cache the results so we can avoid tree searches if a later call goes
460 * to the same directory or file name
462 static char *ino_resolve(int fd, u64 ino, u64 *cache_dirid, char **cache_name)
465 u64 dirid;
466 char *dirname;
467 char *name;
468 char *full;
469 int ret;
470 struct btrfs_ioctl_search_args args;
471 struct btrfs_ioctl_search_key *sk = &args.key;
472 struct btrfs_ioctl_search_header *sh;
473 unsigned long off = 0;
474 int namelen;
476 memset(&args, 0, sizeof(args));
478 sk->tree_id = 0;
481 * step one, we search for the inode back ref. We just use the first
482 * one
484 sk->min_objectid = ino;
485 sk->max_objectid = ino;
486 sk->max_type = BTRFS_INODE_REF_KEY;
487 sk->max_offset = (u64)-1;
488 sk->min_type = BTRFS_INODE_REF_KEY;
489 sk->max_transid = (u64)-1;
490 sk->nr_items = 1;
492 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
493 if (ret < 0) {
494 fprintf(stderr, "ERROR: can't perform the search\n");
495 return NULL;
497 /* the ioctl returns the number of item it found in nr_items */
498 if (sk->nr_items == 0)
499 return NULL;
501 off = 0;
502 sh = (struct btrfs_ioctl_search_header *)(args.buf + off);
504 if (sh->type == BTRFS_INODE_REF_KEY) {
505 struct btrfs_inode_ref *ref;
506 dirid = sh->offset;
508 ref = (struct btrfs_inode_ref *)(sh + 1);
509 namelen = btrfs_stack_inode_ref_name_len(ref);
511 name = (char *)(ref + 1);
512 name = strndup(name, namelen);
514 /* use our cached value */
515 if (dirid == *cache_dirid && *cache_name) {
516 dirname = *cache_name;
517 goto build;
519 } else {
520 return NULL;
523 * the inode backref gives us the file name and the parent directory id.
524 * From here we use __ino_resolve to get the path to the parent
526 dirname = __ino_resolve(fd, dirid);
527 build:
528 full = build_name(dirname, name);
529 if (*cache_name && dirname != *cache_name)
530 free(*cache_name);
532 *cache_name = dirname;
533 *cache_dirid = dirid;
534 free(name);
536 return full;
539 int list_subvols(int fd)
541 struct root_lookup root_lookup;
542 struct rb_node *n;
543 int ret;
544 struct btrfs_ioctl_search_args args;
545 struct btrfs_ioctl_search_key *sk = &args.key;
546 struct btrfs_ioctl_search_header *sh;
547 struct btrfs_root_ref *ref;
548 unsigned long off = 0;
549 int name_len;
550 char *name;
551 u64 dir_id;
552 int i;
554 root_lookup_init(&root_lookup);
556 memset(&args, 0, sizeof(args));
558 /* search in the tree of tree roots */
559 sk->tree_id = 1;
562 * set the min and max to backref keys. The search will
563 * only send back this type of key now.
565 sk->max_type = BTRFS_ROOT_BACKREF_KEY;
566 sk->min_type = BTRFS_ROOT_BACKREF_KEY;
569 * set all the other params to the max, we'll take any objectid
570 * and any trans
572 sk->max_objectid = (u64)-1;
573 sk->max_offset = (u64)-1;
574 sk->max_transid = (u64)-1;
576 /* just a big number, doesn't matter much */
577 sk->nr_items = 4096;
579 while(1) {
580 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
581 if (ret < 0) {
582 fprintf(stderr, "ERROR: can't perform the search\n");
583 return ret;
585 /* the ioctl returns the number of item it found in nr_items */
586 if (sk->nr_items == 0)
587 break;
589 off = 0;
592 * for each item, pull the key out of the header and then
593 * read the root_ref item it contains
595 for (i = 0; i < sk->nr_items; i++) {
596 sh = (struct btrfs_ioctl_search_header *)(args.buf +
597 off);
598 off += sizeof(*sh);
599 if (sh->type == BTRFS_ROOT_BACKREF_KEY) {
600 ref = (struct btrfs_root_ref *)(args.buf + off);
601 name_len = btrfs_stack_root_ref_name_len(ref);
602 name = (char *)(ref + 1);
603 dir_id = btrfs_stack_root_ref_dirid(ref);
605 add_root(&root_lookup, sh->objectid, sh->offset,
606 dir_id, name, name_len);
609 off += sh->len;
612 * record the mins in sk so we can make sure the
613 * next search doesn't repeat this root
615 sk->min_objectid = sh->objectid;
616 sk->min_type = sh->type;
617 sk->min_offset = sh->offset;
619 sk->nr_items = 4096;
620 /* this iteration is done, step forward one root for the next
621 * ioctl
623 if (sk->min_objectid < (u64)-1) {
624 sk->min_objectid++;
625 sk->min_type = BTRFS_ROOT_BACKREF_KEY;
626 sk->min_offset = 0;
627 } else
628 break;
631 * now we have an rbtree full of root_info objects, but we need to fill
632 * in their path names within the subvol that is referencing each one.
634 n = rb_first(&root_lookup.root);
635 while (n) {
636 struct root_info *entry;
637 int ret;
638 entry = rb_entry(n, struct root_info, rb_node);
639 ret = lookup_ino_path(fd, entry);
640 if(ret < 0)
641 return ret;
642 n = rb_next(n);
645 /* now that we have all the subvol-relative paths filled in,
646 * we have to string the subvols together so that we can get
647 * a path all the way back to the FS root
649 n = rb_last(&root_lookup.root);
650 while (n) {
651 struct root_info *entry;
652 entry = rb_entry(n, struct root_info, rb_node);
653 resolve_root(&root_lookup, entry);
654 n = rb_prev(n);
657 return ret;
660 static int print_one_extent(int fd, struct btrfs_ioctl_search_header *sh,
661 struct btrfs_file_extent_item *item,
662 u64 found_gen, u64 *cache_dirid,
663 char **cache_dir_name, u64 *cache_ino,
664 char **cache_full_name)
666 u64 len = 0;
667 u64 disk_start = 0;
668 u64 disk_offset = 0;
669 u8 type;
670 int compressed = 0;
671 int flags = 0;
672 char *name = NULL;
674 if (sh->objectid == *cache_ino) {
675 name = *cache_full_name;
676 } else if (*cache_full_name) {
677 free(*cache_full_name);
678 *cache_full_name = NULL;
680 if (!name) {
681 name = ino_resolve(fd, sh->objectid, cache_dirid,
682 cache_dir_name);
683 *cache_full_name = name;
684 *cache_ino = sh->objectid;
686 if (!name)
687 return -EIO;
689 type = btrfs_stack_file_extent_type(item);
690 compressed = btrfs_stack_file_extent_compression(item);
692 if (type == BTRFS_FILE_EXTENT_REG ||
693 type == BTRFS_FILE_EXTENT_PREALLOC) {
694 disk_start = btrfs_stack_file_extent_disk_bytenr(item);
695 disk_offset = btrfs_stack_file_extent_offset(item);
696 len = btrfs_stack_file_extent_num_bytes(item);
697 } else if (type == BTRFS_FILE_EXTENT_INLINE) {
698 disk_start = 0;
699 disk_offset = 0;
700 len = btrfs_stack_file_extent_ram_bytes(item);
701 } else {
702 printf("unhandled extent type %d for inode %llu "
703 "file offset %llu gen %llu\n",
704 type,
705 (unsigned long long)sh->objectid,
706 (unsigned long long)sh->offset,
707 (unsigned long long)found_gen);
709 return -EIO;
711 printf("inode %llu file offset %llu len %llu disk start %llu "
712 "offset %llu gen %llu flags ",
713 (unsigned long long)sh->objectid,
714 (unsigned long long)sh->offset,
715 (unsigned long long)len,
716 (unsigned long long)disk_start,
717 (unsigned long long)disk_offset,
718 (unsigned long long)found_gen);
720 if (compressed) {
721 printf("COMPRESS");
722 flags++;
724 if (type == BTRFS_FILE_EXTENT_PREALLOC) {
725 printf("%sPREALLOC", flags ? "|" : "");
726 flags++;
728 if (type == BTRFS_FILE_EXTENT_INLINE) {
729 printf("%sINLINE", flags ? "|" : "");
730 flags++;
732 if (!flags)
733 printf("NONE");
735 printf(" %s\n", name);
736 return 0;
739 int find_updated_files(int fd, u64 root_id, u64 oldest_gen)
741 int ret;
742 struct btrfs_ioctl_search_args args;
743 struct btrfs_ioctl_search_key *sk = &args.key;
744 struct btrfs_ioctl_search_header *sh;
745 struct btrfs_file_extent_item *item;
746 unsigned long off = 0;
747 u64 found_gen;
748 u64 max_found = 0;
749 int i;
750 u64 cache_dirid = 0;
751 u64 cache_ino = 0;
752 char *cache_dir_name = NULL;
753 char *cache_full_name = NULL;
754 struct btrfs_file_extent_item backup;
756 memset(&backup, 0, sizeof(backup));
757 memset(&args, 0, sizeof(args));
759 sk->tree_id = root_id;
762 * set all the other params to the max, we'll take any objectid
763 * and any trans
765 sk->max_objectid = (u64)-1;
766 sk->max_offset = (u64)-1;
767 sk->max_transid = (u64)-1;
768 sk->max_type = BTRFS_EXTENT_DATA_KEY;
769 sk->min_transid = oldest_gen;
770 /* just a big number, doesn't matter much */
771 sk->nr_items = 4096;
773 max_found = find_root_gen(fd);
774 while(1) {
775 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
776 if (ret < 0) {
777 fprintf(stderr, "ERROR: can't perform the search\n");
778 return ret;
780 /* the ioctl returns the number of item it found in nr_items */
781 if (sk->nr_items == 0)
782 break;
784 off = 0;
787 * for each item, pull the key out of the header and then
788 * read the root_ref item it contains
790 for (i = 0; i < sk->nr_items; i++) {
791 sh = (struct btrfs_ioctl_search_header *)(args.buf +
792 off);
793 off += sizeof(*sh);
796 * just in case the item was too big, pass something other
797 * than garbage
799 if (sh->len == 0)
800 item = &backup;
801 else
802 item = (struct btrfs_file_extent_item *)(args.buf +
803 off);
804 found_gen = btrfs_stack_file_extent_generation(item);
805 if (sh->type == BTRFS_EXTENT_DATA_KEY &&
806 found_gen >= oldest_gen) {
807 print_one_extent(fd, sh, item, found_gen,
808 &cache_dirid, &cache_dir_name,
809 &cache_ino, &cache_full_name);
811 off += sh->len;
814 * record the mins in sk so we can make sure the
815 * next search doesn't repeat this root
817 sk->min_objectid = sh->objectid;
818 sk->min_offset = sh->offset;
819 sk->min_type = sh->type;
821 sk->nr_items = 4096;
822 if (sk->min_offset < (u64)-1)
823 sk->min_offset++;
824 else if (sk->min_objectid < (u64)-1) {
825 sk->min_objectid++;
826 sk->min_offset = 0;
827 sk->min_type = 0;
828 } else
829 break;
831 free(cache_dir_name);
832 free(cache_full_name);
833 printf("transid marker was %llu\n", (unsigned long long)max_found);
834 return ret;