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  * this allocates a new root in the lookup tree.
 158  *
 159  * root_id should be the object id of the root
 160  *
 161  * ref_tree is the objectid of the referring root.
 162  *
 163  * dir_id is the directory in ref_tree where this root_id can be found.
 164  *
 165  * name is the name of root_id in that directory
 166  *
 167  * name_len is the length of name
 168  */
 169 static int add_root(struct root_lookup *root_lookup,
 170                     u64 root_id, u64 ref_tree, u64 dir_id, char *name,
 171                     int name_len)
 172 {
 173         struct root_info *ri;
 174         struct rb_node *ret;
 175         ri = malloc(sizeof(*ri) + name_len + 1);
 176         if (!ri) {
 177                 printf("memory allocation failed\n");
 178                 exit(1);
 179         }
 180         memset(ri, 0, sizeof(*ri) + name_len + 1);
 181         ri->path = NULL;
 182         ri->dir_id = dir_id;
 183         ri->root_id = root_id;
 184         ri->ref_tree = ref_tree;
 185         strncpy(ri->name, name, name_len);
 186
 187         ret = tree_insert(&root_lookup->root, root_id, ref_tree, &ri->rb_node);
 188         if (ret) {
 189                 printf("failed to insert tree %llu\n", (unsigned long long)root_id);
 190                 exit(1);
 191         }
 192         return 0;
 193 }
 194
 195 /*
 196  * for a given root_info, search through the root_lookup tree to construct
 197  * the full path name to it.
 198  *
 199  * This can't be called until all the root_info->path fields are filled
 200  * in by lookup_ino_path
 201  */
 202 static int resolve_root(struct root_lookup *rl, struct root_info *ri)
 203 {
 204         u64 top_id;
 205         char *full_path = NULL;
 206         int len = 0;
 207         struct root_info *found;
 208
 209         /*
 210          * we go backwards from the root_info object and add pathnames
 211          * from parent directories as we go.
 212          */
 213         found = ri;
 214         while (1) {
 215                 char *tmp;
 216                 u64 next;
 217                 int add_len = strlen(found->path);
 218
 219                 /* room for / and for null */
 220                 tmp = malloc(add_len + 2 + len);
 221                 if (full_path) {
 222                         memcpy(tmp + add_len + 1, full_path, len);
 223                         tmp[add_len] = '/';
 224                         memcpy(tmp, found->path, add_len);
 225                         tmp [add_len + len + 1] = '\0';
 226                         free(full_path);
 227                         full_path = tmp;
 228                         len += add_len + 1;
 229                 } else {
 230                         full_path = strdup(found->path);
 231                         len = add_len;
 232                 }
 233
 234                 next = found->ref_tree;
 235                 /* if the ref_tree refers to ourselves, we're at the top */
 236                 if (next == found->root_id) {
 237                         top_id = next;
 238                         break;
 239                 }
 240
 241                 /*
 242                  * if the ref_tree wasn't in our tree of roots, we're
 243                  * at the top
 244                  */
 245                 found = tree_search(&rl->root, next);
 246                 if (!found) {
 247                         top_id = next;
 248                         break;
 249                 }
 250         }
 251         printf("ID %llu top level %llu path %s\n", ri->root_id, top_id,
 252                full_path);
 253         free(full_path);
 254         return 0;
 255 }
 256
 257 /*
 258  * for a single root_info, ask the kernel to give us a path name
 259  * inside it's ref_root for the dir_id where it lives.
 260  *
 261  * This fills in root_info->path with the path to the directory and and
 262  * appends this root's name.
 263  */
 264 static int lookup_ino_path(int fd, struct root_info *ri)
 265 {
 266         struct btrfs_ioctl_ino_lookup_args args;
 267         int ret;
 268
 269         if (ri->path)
 270                 return 0;
 271
 272         memset(&args, 0, sizeof(args));
 273         args.treeid = ri->ref_tree;
 274         args.objectid = ri->dir_id;
 275
 276         ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &args);
 277         if (ret) {
 278                 fprintf(stderr, "Failed to lookup path for root %llu\n",
 279                         (unsigned long long)ri->ref_tree);
 280                 exit(1);
 281         }
 282
 283         if (args.name[0]) {
 284                 /*
 285                  * we're in a subdirectory of ref_tree, the kernel ioctl
 286                  * puts a / in there for us
 287                  */
 288                 ri->path = malloc(strlen(ri->name) + strlen(args.name) + 1);
 289                 if (!ri->path) {
 290                         perror("malloc failed");
 291                         exit(1);
 292                 }
 293                 strcpy(ri->path, args.name);
 294                 strcat(ri->path, ri->name);
 295         } else {
 296                 /* we're at the root of ref_tree */
 297                 ri->path = strdup(ri->name);
 298                 if (!ri->path) {
 299                         perror("strdup failed");
 300                         exit(1);
 301                 }
 302         }
 303         return 0;
 304 }
 305
 306 int list_subvols(int fd)
 307 {
 308         struct root_lookup root_lookup;
 309         struct rb_node *n;
 310         int ret;
 311         struct btrfs_ioctl_search_args args;
 312         struct btrfs_ioctl_search_key *sk = &args.key;
 313         struct btrfs_ioctl_search_header *sh;
 314         struct btrfs_root_ref *ref;
 315         unsigned long off = 0;
 316         int name_len;
 317         char *name;
 318         u64 dir_id;
 319         int i;
 320
 321         root_lookup_init(&root_lookup);
 322
 323         memset(&args, 0, sizeof(args));
 324
 325         /* search in the tree of tree roots */
 326         sk->tree_id = 1;
 327
 328         /*
 329          * set the min and max to backref keys.  The search will
 330          * only send back this type of key now.
 331          */
 332         sk->max_type = BTRFS_ROOT_BACKREF_KEY;
 333         sk->min_type = BTRFS_ROOT_BACKREF_KEY;
 334
 335         /*
 336          * set all the other params to the max, we'll take any objectid
 337          * and any trans
 338          */
 339         sk->max_objectid = (u64)-1;
 340         sk->max_offset = (u64)-1;
 341         sk->max_transid = (u64)-1;
 342
 343         /* just a big number, doesn't matter much */
 344         sk->nr_items = 4096;
 345
 346         while(1) {
 347                 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 348                 if (ret < 0) {
 349                         perror("ioctl:");
 350                         break;
 351                 }
 352                 /* the ioctl returns the number of item it found in nr_items */
 353                 if (sk->nr_items == 0)
 354                         break;
 355
 356                 off = 0;
 357
 358                 /*
 359                  * for each item, pull the key out of the header and then
 360                  * read the root_ref item it contains
 361                  */
 362                 for (i = 0; i < sk->nr_items; i++) {
 363                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 364                                                                   off);
 365                         off += sizeof(*sh);
 366
 367                         ref = (struct btrfs_root_ref *)(args.buf + off);
 368                         name_len = btrfs_stack_root_ref_name_len(ref);
 369                         name = (char *)(ref + 1);
 370                         dir_id = btrfs_stack_root_ref_dirid(ref);
 371
 372                         add_root(&root_lookup, sh->objectid, sh->offset,
 373                                  dir_id, name, name_len);
 374
 375                         off += sh->len;
 376
 377                         /*
 378                          * record the mins in sk so we can make sure the
 379                          * next search doesn't repeat this root
 380                          */
 381                         sk->min_objectid = sh->objectid;
 382                         sk->min_type = sh->type;
 383                         sk->min_offset = sh->offset;
 384                 }
 385                 sk->nr_items = 4096;
 386                 /* this iteration is done, step forward one root for the next
 387                  * ioctl
 388                  */
 389                 if (sk->min_objectid < (u64)-1)
 390                         sk->min_objectid++;
 391                 else
 392                         break;
 393         }
 394         /*
 395          * now we have an rbtree full of root_info objects, but we need to fill
 396          * in their path names within the subvol that is referencing each one.
 397          */
 398         n = rb_first(&root_lookup.root);
 399         while (n) {
 400                 struct root_info *entry;
 401                 entry = rb_entry(n, struct root_info, rb_node);
 402                 lookup_ino_path(fd, entry);
 403                 n = rb_next(n);
 404         }
 405
 406         /* now that we have all the subvol-relative paths filled in,
 407          * we have to string the subvols together so that we can get
 408          * a path all the way back to the FS root
 409          */
 410         n = rb_last(&root_lookup.root);
 411         while (n) {
 412                 struct root_info *entry;
 413                 entry = rb_entry(n, struct root_info, rb_node);
 414                 resolve_root(&root_lookup, entry);
 415                 n = rb_prev(n);
 416         }
 417
 418         return ret;
 419 }