btrfs-list.c

   1 /*
   2  * Copyright (C) 2010 Oracle.  All rights reserved.
   3  *
   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.
   7  *
   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.
  12  *
  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.
  17  */
  18
  19 #ifndef __CHECKER__
  20 #include <sys/ioctl.h>
  21 #include <sys/mount.h>
  22 #include "ioctl.h"
  23 #endif
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26 #include <sys/types.h>
  27 #include <sys/stat.h>
  28 #include <fcntl.h>
  29 #include <unistd.h>
  30 #include <dirent.h>
  31 #include <libgen.h>
  32 #include "kerncompat.h"
  33 #include "ctree.h"
  34 #include "transaction.h"
  35 #include "utils.h"
  36 #include "version.h"
  37
  38 /* we store all the roots we find in an rbtree so that we can
  39  * search for them later.
  40  */
  41 struct root_lookup {
  42         struct rb_root root;
  43 };
  44
  45 /*
  46  * one of these for each root we find.
  47  */
  48 struct root_info {
  49         struct rb_node rb_node;
  50
  51         /* this root's id */
  52         u64 root_id;
  53
  54         /* the id of the root that references this one */
  55         u64 ref_tree;
  56
  57         /* the dir id we're in from ref_tree */
  58         u64 dir_id;
  59
  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.
  62          */
  63         char *path;
  64
  65         /* the name of this root in the directory it lives in */
  66         char name[];
  67 };
  68
  69 void root_lookup_init(struct root_lookup *tree)
  70 {
  71         tree->root.rb_node = NULL;
  72 }
  73
  74 static int comp_entry(struct root_info *entry, u64 root_id, u64 ref_tree)
  75 {
  76         if (entry->root_id > root_id)
  77                 return 1;
  78         if (entry->root_id < root_id)
  79                 return -1;
  80         if (entry->ref_tree > ref_tree)
  81                 return 1;
  82         if (entry->ref_tree < ref_tree)
  83                 return -1;
  84         return 0;
  85 }
  86
  87 /*
  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
  90  * as the key
  91  */
  92 static struct rb_node *tree_insert(struct rb_root *root, u64 root_id,
  93                                    u64 ref_tree, struct rb_node *node)
  94 {
  95         struct rb_node ** p = &root->rb_node;
  96         struct rb_node * parent = NULL;
  97         struct root_info *entry;
  98         int comp;
  99
 100         while(*p) {
 101                 parent = *p;
 102                 entry = rb_entry(parent, struct root_info, rb_node);
 103
 104                 comp = comp_entry(entry, root_id, ref_tree);
 105
 106                 if (comp < 0)
 107                         p = &(*p)->rb_left;
 108                 else if (comp > 0)
 109                         p = &(*p)->rb_right;
 110                 else
 111                         return parent;
 112         }
 113
 114         entry = rb_entry(parent, struct root_info, rb_node);
 115         rb_link_node(node, parent, p);
 116         rb_insert_color(node, root);
 117         return NULL;
 118 }
 119
 120 /*
 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
 123  */
 124 static struct root_info *tree_search(struct rb_root *root, u64 root_id)
 125 {
 126         struct rb_node * n = root->rb_node;
 127         struct root_info *entry;
 128
 129         while(n) {
 130                 entry = rb_entry(n, struct root_info, rb_node);
 131
 132                 if (entry->root_id < root_id)
 133                         n = n->rb_left;
 134                 else if (entry->root_id > root_id)
 135                         n = n->rb_right;
 136                 else {
 137                         struct root_info *prev;
 138                         struct rb_node *prev_n;
 139                         while (1) {
 140                                 prev_n = rb_prev(n);
 141                                 if (!prev_n)
 142                                         break;
 143                                 prev = rb_entry(prev_n, struct root_info,
 144                                                       rb_node);
 145                                 if (prev->root_id != root_id)
 146                                         break;
 147                                 entry = prev;
 148                                 n = prev_n;
 149                         }
 150                         return entry;
 151                 }
 152         }
 153         return NULL;
 154 }
 155
 156 /*
 157  * helper to open either a file or directory so that
 158  * we can run ioctls on it.
 159  */
 160 static int open_file_or_dir(const char *fname)
 161 {
 162         int ret;
 163         struct stat st;
 164         DIR *dirstream;
 165         int fd;
 166
 167         ret = stat(fname, &st);
 168         if (ret < 0) {
 169                 perror("stat:");
 170                 exit(1);
 171         }
 172         if (S_ISDIR(st.st_mode)) {
 173                 dirstream = opendir(fname);
 174                 if (!dirstream) {
 175                         perror("opendir");
 176                         exit(1);
 177                 }
 178                 fd = dirfd(dirstream);
 179         } else {
 180                 fd = open(fname, O_RDWR);
 181         }
 182         if (fd < 0) {
 183                 perror("open");
 184                 exit(1);
 185         }
 186         return fd;
 187 }
 188
 189 /*
 190  * this allocates a new root in the lookup tree.
 191  *
 192  * root_id should be the object id of the root
 193  *
 194  * ref_tree is the objectid of the referring root.
 195  *
 196  * dir_id is the directory in ref_tree where this root_id can be found.
 197  *
 198  * name is the name of root_id in that directory
 199  *
 200  * name_len is the length of name
 201  */
 202 static int add_root(struct root_lookup *root_lookup,
 203                     u64 root_id, u64 ref_tree, u64 dir_id, char *name,
 204                     int name_len)
 205 {
 206         struct root_info *ri;
 207         struct rb_node *ret;
 208         ri = malloc(sizeof(*ri) + name_len);
 209         if (!ri) {
 210                 printf("memory allocation failed\n");
 211                 exit(1);
 212         }
 213         ri->path = NULL;
 214         ri->dir_id = dir_id;
 215         ri->root_id = root_id;
 216         ri->ref_tree = ref_tree;
 217         strncpy(ri->name, name, name_len);
 218
 219         ret = tree_insert(&root_lookup->root, root_id, ref_tree, &ri->rb_node);
 220         if (ret) {
 221                 printf("failed to insert tree %llu\n", (unsigned long long)root_id);
 222                 exit(1);
 223         }
 224         return 0;
 225 }
 226
 227 /*
 228  * for a given root_info, search through the root_lookup tree to construct
 229  * the full path name to it.
 230  *
 231  * This can't be called until all the root_info->path fields are filled
 232  * in by lookup_ino_path
 233  */
 234 static int resolve_root(struct root_lookup *rl, struct root_info *ri)
 235 {
 236         u64 top_id;
 237         char *full_path = NULL;
 238         int len = 0;
 239         struct root_info *found;
 240
 241         /*
 242          * we go backwards from the root_info object and add pathnames
 243          * from parent directories as we go.
 244          */
 245         found = ri;
 246         while (1) {
 247                 char *tmp;
 248                 u64 next;
 249                 int add_len = strlen(found->path);
 250
 251                 /* room for / and for null */
 252                 tmp = malloc(add_len + 2 + len);
 253                 if (full_path) {
 254                         memcpy(tmp + add_len + 1, full_path, len);
 255                         tmp[add_len] = '/';
 256                         memcpy(tmp, found->path, add_len);
 257                         tmp [add_len + len + 1] = '\0';
 258                         free(full_path);
 259                         full_path = tmp;
 260                         len += add_len + 1;
 261                 } else {
 262                         full_path = strdup(found->path);
 263                         len = add_len;
 264                 }
 265
 266                 next = found->ref_tree;
 267                 /* if the ref_tree refers to ourselves, we're at the top */
 268                 if (next == found->root_id) {
 269                         top_id = next;
 270                         break;
 271                 }
 272
 273                 /*
 274                  * if the ref_tree wasn't in our tree of roots, we're
 275                  * at the top
 276                  */
 277                 found = tree_search(&rl->root, next);
 278                 if (!found) {
 279                         top_id = next;
 280                         break;
 281                 }
 282         }
 283         printf("ID %llu top level %llu path %s\n", ri->root_id, top_id,
 284                full_path);
 285         free(full_path);
 286         return 0;
 287 }
 288
 289 /*
 290  * for a single root_info, ask the kernel to give us a path name
 291  * inside it's ref_root for the dir_id where it lives.
 292  *
 293  * This fills in root_info->path with the path to the directory and and
 294  * appends this root's name.
 295  */
 296 static int lookup_ino_path(int fd, struct root_info *ri)
 297 {
 298         struct btrfs_ioctl_ino_lookup_args args;
 299         int ret;
 300
 301         if (ri->path)
 302                 return 0;
 303
 304         args.treeid = ri->ref_tree;
 305         args.objectid = ri->dir_id;
 306         args.name[0] = '\0';
 307
 308         ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &args);
 309         if (ret) {
 310                 fprintf(stderr, "Failed to lookup path for root %llu\n",
 311                         (unsigned long long)ri->ref_tree);
 312                 exit(1);
 313         }
 314
 315         if (args.name[0]) {
 316                 /*
 317                  * we're in a subdirectory of ref_tree, the kernel ioctl
 318                  * puts a / in there for us
 319                  */
 320                 ri->path = malloc(strlen(ri->name) + strlen(args.name) + 1);
 321                 if (!ri->path) {
 322                         perror("malloc failed");
 323                         exit(1);
 324                 }
 325                 strcpy(ri->path, args.name);
 326                 strcat(ri->path, ri->name);
 327         } else {
 328                 /* we're at the root of ref_tree */
 329                 ri->path = strdup(ri->name);
 330                 if (!ri->path) {
 331                         perror("strdup failed");
 332                         exit(1);
 333                 }
 334         }
 335         return 0;
 336 }
 337
 338 static int list_subvols(int fd)
 339 {
 340         struct root_lookup root_lookup;
 341         struct rb_node *n;
 342         int ret;
 343         struct btrfs_ioctl_search_args args;
 344         struct btrfs_ioctl_search_key *sk = &args.key;
 345         struct btrfs_ioctl_search_header *sh;
 346         struct btrfs_root_ref *ref;
 347         unsigned long off = 0;
 348         int name_len;
 349         char *name;
 350         u64 dir_id;
 351         int i;
 352
 353         root_lookup_init(&root_lookup);
 354
 355         memset(&args, 0, sizeof(args));
 356
 357         /* search in the tree of tree roots */
 358         sk->tree_id = 1;
 359
 360         /*
 361          * set the min and max to backref keys.  The search will
 362          * only send back this type of key now.
 363          */
 364         sk->max_type = BTRFS_ROOT_BACKREF_KEY;
 365         sk->min_type = BTRFS_ROOT_BACKREF_KEY;
 366
 367         /*
 368          * set all the other params to the max, we'll take any objectid
 369          * and any trans
 370          */
 371         sk->max_objectid = (u64)-1;
 372         sk->max_offset = (u64)-1;
 373         sk->max_transid = (u64)-1;
 374
 375         /* just a big number, doesn't matter much */
 376         sk->nr_items = 4096;
 377
 378         while(1) {
 379                 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 380                 if (ret < 0) {
 381                         perror("ioctl:");
 382                         break;
 383                 }
 384                 /* the ioctl returns the number of item it found in nr_items */
 385                 if (sk->nr_items == 0)
 386                         break;
 387
 388                 off = 0;
 389
 390                 /*
 391                  * for each item, pull the key out of the header and then
 392                  * read the root_ref item it contains
 393                  */
 394                 for (i = 0; i < sk->nr_items; i++) {
 395                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 396                                                                   off);
 397                         off += sizeof(*sh);
 398
 399                         ref = (struct btrfs_root_ref *)(args.buf + off);
 400                         name_len = btrfs_stack_root_ref_name_len(ref);
 401                         name = (char *)(ref + 1);
 402                         dir_id = btrfs_stack_root_ref_dirid(ref);
 403
 404                         add_root(&root_lookup, sh->objectid, sh->offset,
 405                                  dir_id, name, name_len);
 406
 407                         off += sh->len;
 408
 409                         /*
 410                          * record the mins in sk so we can make sure the
 411                          * next search doesn't repeat this root
 412                          */
 413                         sk->min_objectid = sh->objectid;
 414                         sk->min_type = sh->type;
 415                         sk->min_offset = sh->offset;
 416                 }
 417                 sk->nr_items = 4096;
 418                 /* this iteration is done, step forward one root for the next
 419                  * ioctl
 420                  */
 421                 if (sk->min_objectid < (u64)-1)
 422                         sk->min_objectid++;
 423                 else
 424                         break;
 425         }
 426         /*
 427          * now we have an rbtree full of root_info objects, but we need to fill
 428          * in their path names within the subvol that is referencing each one.
 429          */
 430         n = rb_first(&root_lookup.root);
 431         while (n) {
 432                 struct root_info *entry;
 433                 entry = rb_entry(n, struct root_info, rb_node);
 434                 lookup_ino_path(fd, entry);
 435                 n = rb_next(n);
 436         }
 437
 438         /* now that we have all the subvol-relative paths filled in,
 439          * we have to string the subvols together so that we can get
 440          * a path all the way back to the FS root
 441          */
 442         n = rb_last(&root_lookup.root);
 443         while (n) {
 444                 struct root_info *entry;
 445                 entry = rb_entry(n, struct root_info, rb_node);
 446                 resolve_root(&root_lookup, entry);
 447                 n = rb_prev(n);
 448         }
 449
 450         printf("%s\n", BTRFS_BUILD_VERSION);
 451         return ret;
 452 }
 453
 454 int main(int ac, char **av)
 455 {
 456         int fd;
 457
 458         if (ac != 2) {
 459                 fprintf(stderr, "usage: btrfs-list mount_point\n");
 460                 exit(1);
 461         }
 462         fd = open_file_or_dir(av[1]);
 463
 464         return list_subvols(fd);
 465 }
 466