cmds-fi-du.c

   1 /*
   2  * This program is free software; you can redistribute it and/or
   3  * modify it under the terms of the GNU General Public
   4  * License v2 as published by the Free Software Foundation.
   5  *
   6  * This program is distributed in the hope that it will be useful,
   7  * but WITHOUT ANY WARRANTY; without even the implied warranty of
   8  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   9  * General Public License for more details.
  10  *
  11  * You should have received a copy of the GNU General Public
  12  * License along with this program; if not, write to the
  13  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  14  * Boston, MA 021110-1307, USA.
  15  */
  16
  17 #include <sys/types.h>
  18 #include <sys/stat.h>
  19 #include <unistd.h>
  20 #include <stdio.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23 #include <stdarg.h>
  24 #include <getopt.h>
  25 #include <fcntl.h>
  26 #include <dirent.h>
  27
  28 #include <sys/ioctl.h>
  29 #include <linux/fs.h>
  30 #include <linux/version.h>
  31 #include <linux/fiemap.h>
  32
  33 #if !defined(FIEMAP_EXTENT_SHARED) && (HAVE_OWN_FIEMAP_EXTENT_SHARED_DEFINE == 1)
  34 #define FIEMAP_EXTENT_SHARED           0x00002000
  35 #endif
  36
  37 #include "utils.h"
  38 #include "commands.h"
  39 #include "kerncompat.h"
  40 #include "rbtree.h"
  41
  42 #include "interval_tree_generic.h"
  43 #include "help.h"
  44 #include "fsfeatures.h"
  45
  46 static int summarize = 0;
  47 static unsigned unit_mode = UNITS_RAW;
  48 static char path[PATH_MAX] = { 0, };
  49 static char *pathp = path;
  50 static char *path_max = &path[PATH_MAX - 1];
  51
  52 struct shared_extent {
  53         struct rb_node  rb;
  54         u64     start;  /* Start of interval */
  55         u64     last;   /* Last location _in_ interval */
  56         u64     __subtree_last;
  57 };
  58
  59 /*
  60  * extent_tree_* functions are defined in the massive interval tree
  61  * macro below. This serves to illustrate the api in human-readable
  62  * terms.
  63  */
  64 static void
  65 extent_tree_insert(struct shared_extent *node, struct rb_root *root);
  66
  67 static void
  68 extent_tree_remove(struct shared_extent *node, struct rb_root *root);
  69
  70 static struct shared_extent *
  71 extent_tree_iter_first(struct rb_root *root,
  72                        u64 start, u64 last);
  73
  74 static struct shared_extent *
  75 extent_tree_iter_next(struct shared_extent *node,
  76                         u64 start, u64 last);
  77
  78 #define START(node) ((node)->start)
  79 #define LAST(node)  ((node)->last)
  80
  81 INTERVAL_TREE_DEFINE(struct shared_extent, rb,
  82                      u64, __subtree_last,
  83                      START, LAST, static, extent_tree)
  84
  85 static int add_shared_extent(u64 start, u64 len, struct rb_root *root)
  86 {
  87         struct shared_extent *sh;
  88
  89         ASSERT(len != 0);
  90
  91         sh = calloc(1, sizeof(*sh));
  92         if (!sh)
  93                 return -ENOMEM;
  94
  95         sh->start = start;
  96         sh->last = (start + len - 1);
  97
  98         extent_tree_insert(sh, root);
  99
 100         return 0;
 101 }
 102
 103 static void cleanup_shared_extents(struct rb_root *root)
 104 {
 105         struct shared_extent *s;
 106         struct shared_extent *tmp;
 107
 108         if (!root)
 109                 return;
 110
 111         s = extent_tree_iter_first(root, 0, -1ULL);
 112         while (s) {
 113                 tmp = extent_tree_iter_next(s, 0, -1ULL);
 114                 extent_tree_remove(s, root);
 115
 116                 free(s);
 117                 s = tmp;
 118         }
 119 }
 120
 121 #define dbgprintf(...)
 122
 123 /*
 124  * Find all extents which overlap 'n', calculate the space
 125  * covered by them and remove those nodes from the tree.
 126  */
 127 static u64 count_unique_bytes(struct rb_root *root, struct shared_extent *n)
 128 {
 129         struct shared_extent *tmp;
 130         u64 wstart = n->start;
 131         u64 wlast = n->last;
 132
 133         dbgprintf("Count overlaps:");
 134
 135         do {
 136                 /*
 137                  * Expand our search window based on the lastest
 138                  * overlapping extent. Doing this will allow us to
 139                  * find all possible overlaps
 140                  */
 141                 if (wstart > n->start)
 142                         wstart = n->start;
 143                 if (wlast < n->last)
 144                         wlast = n->last;
 145
 146                 dbgprintf(" (%llu, %llu)", n->start, n->last);
 147
 148                 tmp = n;
 149                 n = extent_tree_iter_next(n, wstart, wlast);
 150
 151                 extent_tree_remove(tmp, root);
 152                 free(tmp);
 153         } while (n);
 154
 155         dbgprintf("; wstart: %llu wlast: %llu total: %llu\n", wstart,
 156                 wlast, wlast - wstart + 1);
 157
 158         return wlast - wstart + 1;
 159 }
 160
 161 /*
 162  * What we want to do here is get a count of shared bytes within the
 163  * set of extents we have collected. Specifically, we don't want to
 164  * count any byte more than once, so just adding them up doesn't
 165  * work.
 166  *
 167  * For each set of overlapping extents we find the lowest start and
 168  * highest end. From there we have the actual number of bytes which is
 169  * shared across all of the extents in our set. A sum of each sets
 170  * extent length is returned.
 171  */
 172 static void count_shared_bytes(struct rb_root *root, u64 *ret_cnt)
 173 {
 174         u64 count = 0;
 175         struct shared_extent *s = extent_tree_iter_first(root,
 176                                                          0, -1ULL);
 177
 178         if (!s)
 179                 goto out;
 180
 181         while (s) {
 182                 /*
 183                  * Find all extents which overlap 's', calculate the space
 184                  * covered by them and remove those nodes from the tree.
 185                  */
 186                 count += count_unique_bytes(root, s);
 187
 188                 /*
 189                  * Since count_unique_bytes will be emptying the tree,
 190                  * we can grab the first node here
 191                  */
 192                 s = extent_tree_iter_first(root, 0, -1ULL);
 193         }
 194
 195         BUG_ON(!RB_EMPTY_ROOT(root));
 196 out:
 197         *ret_cnt = count;
 198 }
 199
 200 /* Track which inodes we've seen for the purposes of hardlink detection. */
 201 struct seen_inode {
 202         struct rb_node  i_node;
 203         u64             i_ino;
 204         u64             i_subvol;
 205 };
 206 static struct rb_root seen_inodes = RB_ROOT;
 207
 208 static int cmp_si(struct seen_inode *si, u64 ino, u64 subvol)
 209 {
 210         if (ino < si->i_ino)
 211                 return -1;
 212         else if (ino > si->i_ino)
 213                 return 1;
 214         if (subvol < si->i_subvol)
 215                 return -1;
 216         else if (subvol > si->i_subvol)
 217                 return 1;
 218         return 0;
 219 }
 220
 221 static int mark_inode_seen(u64 ino, u64 subvol)
 222 {
 223         int cmp;
 224         struct rb_node **p = &seen_inodes.rb_node;
 225         struct rb_node *parent = NULL;
 226         struct seen_inode *si;
 227
 228         while (*p) {
 229                 parent = *p;
 230
 231                 si = rb_entry(parent, struct seen_inode, i_node);
 232                 cmp = cmp_si(si, ino, subvol);
 233                 if (cmp < 0)
 234                         p = &(*p)->rb_left;
 235                 else if (cmp > 0)
 236                         p = &(*p)->rb_right;
 237                 else
 238                         return -EEXIST;
 239         }
 240
 241         si = calloc(1, sizeof(*si));
 242         if (!si)
 243                 return -ENOMEM;
 244
 245         si->i_ino = ino;
 246         si->i_subvol = subvol;
 247
 248         rb_link_node(&si->i_node, parent, p);
 249         rb_insert_color(&si->i_node, &seen_inodes);
 250
 251         return 0;
 252 }
 253
 254 static int inode_seen(u64 ino, u64 subvol)
 255 {
 256         int cmp;
 257         struct rb_node *n = seen_inodes.rb_node;
 258         struct seen_inode *si;
 259
 260         while (n) {
 261                 si = rb_entry(n, struct seen_inode, i_node);
 262
 263                 cmp = cmp_si(si, ino, subvol);
 264                 if (cmp < 0)
 265                         n = n->rb_left;
 266                 else if (cmp > 0)
 267                         n = n->rb_right;
 268                 else
 269                         return -EEXIST;
 270         }
 271         return 0;
 272 }
 273
 274 static void clear_seen_inodes(void)
 275 {
 276         struct rb_node *n = rb_first(&seen_inodes);
 277         struct seen_inode *si;
 278
 279         while (n) {
 280                 si = rb_entry(n, struct seen_inode, i_node);
 281
 282                 rb_erase(&si->i_node, &seen_inodes);
 283                 free(si);
 284
 285                 n = rb_first(&seen_inodes);
 286         }
 287 }
 288
 289 /*
 290  * Inline extents are skipped because they do not take data space,
 291  * delalloc and unknown are skipped because we do not know how much
 292  * space they will use yet.
 293  */
 294 #define SKIP_FLAGS      (FIEMAP_EXTENT_UNKNOWN|FIEMAP_EXTENT_DELALLOC|FIEMAP_EXTENT_DATA_INLINE)
 295 static int du_calc_file_space(int fd, struct rb_root *shared_extents,
 296                               u64 *ret_total, u64 *ret_shared)
 297 {
 298         char buf[16384];
 299         struct fiemap *fiemap = (struct fiemap *)buf;
 300         struct fiemap_extent *fm_ext = &fiemap->fm_extents[0];
 301         int count = (sizeof(buf) - sizeof(*fiemap)) /
 302                         sizeof(struct fiemap_extent);
 303         unsigned int i, ret;
 304         int last = 0;
 305         int rc;
 306         u64 ext_len;
 307         u64 file_total = 0;
 308         u64 file_shared = 0;
 309         u32 flags;
 310
 311         memset(fiemap, 0, sizeof(struct fiemap));
 312
 313         do {
 314                 fiemap->fm_length = ~0ULL;
 315                 fiemap->fm_extent_count = count;
 316                 rc = ioctl(fd, FS_IOC_FIEMAP, (unsigned long) fiemap);
 317                 if (rc < 0) {
 318                         ret = -errno;
 319                         goto out;
 320                 }
 321
 322                 /* If 0 extents are returned, then more ioctls are not needed */
 323                 if (fiemap->fm_mapped_extents == 0)
 324                         break;
 325
 326                 for (i = 0; i < fiemap->fm_mapped_extents; i++) {
 327                         ext_len = fm_ext[i].fe_length;
 328                         flags = fm_ext[i].fe_flags;
 329
 330                         if (flags & FIEMAP_EXTENT_LAST)
 331                                 last = 1;
 332
 333                         if (flags & SKIP_FLAGS)
 334                                 continue;
 335
 336                         if (ext_len == 0) {
 337                                 warning("extent %llu has length 0, skipping",
 338                                         (unsigned long long)fm_ext[i].fe_physical);
 339                                 continue;
 340                         }
 341
 342                         file_total += ext_len;
 343                         if (flags & FIEMAP_EXTENT_SHARED) {
 344                                 file_shared += ext_len;
 345
 346                                 if (shared_extents) {
 347                                         ret = add_shared_extent(fm_ext[i].fe_physical,
 348                                                                 ext_len,
 349                                                                 shared_extents);
 350                                         if (ret)
 351                                                 goto out;
 352                                 }
 353                         }
 354                 }
 355
 356                 fiemap->fm_start = (fm_ext[i - 1].fe_logical +
 357                                     fm_ext[i - 1].fe_length);
 358         } while (last == 0);
 359
 360         *ret_total = file_total;
 361         *ret_shared = file_shared;
 362
 363         ret = 0;
 364 out:
 365         return ret;
 366 }
 367
 368 struct du_dir_ctxt {
 369         u64             bytes_total;
 370         u64             bytes_shared;
 371         DIR             *dirstream;
 372         struct rb_root  shared_extents;
 373 };
 374 #define INIT_DU_DIR_CTXT        (struct du_dir_ctxt) { 0ULL, 0ULL, NULL, RB_ROOT }
 375
 376 static int du_add_file(const char *filename, int dirfd,
 377                        struct rb_root *shared_extents, u64 *ret_total,
 378                        u64 *ret_shared, int top_level);
 379
 380 static int du_walk_dir(struct du_dir_ctxt *ctxt, struct rb_root *shared_extents)
 381 {
 382         int ret, type;
 383         struct dirent *entry;
 384         DIR *dirstream = ctxt->dirstream;
 385
 386         ret = 0;
 387         do {
 388                 u64 tot, shr;
 389
 390                 errno = 0;
 391                 entry = readdir(dirstream);
 392                 if (entry) {
 393                         if (strcmp(entry->d_name, ".") == 0
 394                             || strcmp(entry->d_name, "..") == 0)
 395                                 continue;
 396
 397                         type = entry->d_type;
 398                         if (type == DT_REG || type == DT_DIR) {
 399                                 tot = shr = 0;
 400
 401                                 ret = du_add_file(entry->d_name,
 402                                                   dirfd(dirstream),
 403                                                   shared_extents, &tot, &shr,
 404                                                   0);
 405                                 if (ret == -ENOTTY) {
 406                                         ret = 0;
 407                                         continue;
 408                                 } else if (ret) {
 409                                         fprintf(stderr,
 410                                                 "failed to walk dir/file: %s :%s\n",
 411                                                 entry->d_name, strerror(-ret));
 412                                         break;
 413                                 }
 414
 415                                 ctxt->bytes_total += tot;
 416                                 ctxt->bytes_shared += shr;
 417                         }
 418                 }
 419         } while (entry != NULL);
 420
 421         return ret;
 422 }
 423
 424 static int du_add_file(const char *filename, int dirfd,
 425                        struct rb_root *shared_extents, u64 *ret_total,
 426                        u64 *ret_shared, int top_level)
 427 {
 428         int ret, len = strlen(filename);
 429         char *pathtmp;
 430         struct stat st;
 431         struct du_dir_ctxt dir = INIT_DU_DIR_CTXT;
 432         int is_dir = 0;
 433         u64 file_total = 0;
 434         u64 file_shared = 0;
 435         u64 dir_set_shared = 0;
 436         u64 subvol;
 437         int fd;
 438         DIR *dirstream = NULL;
 439
 440         ret = fstatat(dirfd, filename, &st, 0);
 441         if (ret)
 442                 return -errno;
 443
 444         if (!S_ISREG(st.st_mode) && !S_ISDIR(st.st_mode))
 445                 return 0;
 446
 447         if (len > (path_max - pathp)) {
 448                 error("path too long: %s %s", path, filename);
 449                 return -ENAMETOOLONG;
 450         }
 451
 452         pathtmp = pathp;
 453         if (pathp == path)
 454                 ret = sprintf(pathp, "%s", filename);
 455         else
 456                 ret = sprintf(pathp, "/%s", filename);
 457         pathp += ret;
 458
 459         fd = open_file_or_dir3(path, &dirstream, O_RDONLY);
 460         if (fd < 0) {
 461                 ret = -errno;
 462                 goto out;
 463         }
 464
 465         ret = lookup_path_rootid(fd, &subvol);
 466         if (ret)
 467                 goto out_close;
 468
 469         if (inode_seen(st.st_ino, subvol))
 470                 goto out_close;
 471
 472         ret = mark_inode_seen(st.st_ino, subvol);
 473         if (ret)
 474                 goto out_close;
 475
 476         if (S_ISREG(st.st_mode)) {
 477                 ret = du_calc_file_space(fd, shared_extents, &file_total,
 478                                          &file_shared);
 479                 if (ret)
 480                         goto out_close;
 481         } else if (S_ISDIR(st.st_mode)) {
 482                 struct rb_root *root = shared_extents;
 483
 484                 /*
 485                  * We collect shared extents in an rb_root, the top
 486                  * level caller will not pass a root down, so use the
 487                  * one on our dir context.
 488                  */
 489                 if (top_level)
 490                         root = &dir.shared_extents;
 491
 492                 is_dir = 1;
 493
 494                 dir.dirstream = dirstream;
 495                 ret = du_walk_dir(&dir, root);
 496                 *pathp = '\0';
 497                 if (ret) {
 498                         if (top_level)
 499                                 cleanup_shared_extents(root);
 500                         goto out_close;
 501                 }
 502
 503                 file_total = dir.bytes_total;
 504                 file_shared = dir.bytes_shared;
 505                 if (top_level)
 506                         count_shared_bytes(root, &dir_set_shared);
 507         }
 508
 509         if (!summarize || top_level) {
 510                 u64 excl = file_total - file_shared;
 511
 512                 if (top_level) {
 513                         u64 set_shared = file_shared;
 514
 515                         if (is_dir)
 516                                 set_shared = dir_set_shared;
 517
 518                         printf("%10s  %10s  %10s  %s\n",
 519                                pretty_size_mode(file_total, unit_mode),
 520                                pretty_size_mode(excl, unit_mode),
 521                                pretty_size_mode(set_shared, unit_mode),
 522                                path);
 523                 } else {
 524                         printf("%10s  %10s  %10s  %s\n",
 525                                pretty_size_mode(file_total, unit_mode),
 526                                pretty_size_mode(excl, unit_mode),
 527                                "-", path);
 528                 }
 529         }
 530
 531         if (ret_total)
 532                 *ret_total = file_total;
 533         if (ret_shared)
 534                 *ret_shared = file_shared;
 535
 536 out_close:
 537         close_file_or_dir(fd, dirstream);
 538 out:
 539         /* reset path to just before this element */
 540         pathp = pathtmp;
 541
 542         return ret;
 543 }
 544
 545 const char * const cmd_filesystem_du_usage[] = {
 546         "btrfs filesystem du [options] <path> [<path>..]",
 547         "Summarize disk usage of each file.",
 548         "-s|--summarize     display only a total for each argument",
 549         HELPINFO_UNITS_LONG,
 550         NULL
 551 };
 552
 553 int cmd_filesystem_du(int argc, char **argv)
 554 {
 555         int ret = 0, err = 0;
 556         int i;
 557         u32 kernel_version;
 558
 559         unit_mode = get_unit_mode_from_arg(&argc, argv, 1);
 560
 561         while (1) {
 562                 static const struct option long_options[] = {
 563                         { "summarize", no_argument, NULL, 's'},
 564                         { NULL, 0, NULL, 0 }
 565                 };
 566                 int c = getopt_long(argc, argv, "s", long_options, NULL);
 567
 568                 if (c < 0)
 569                         break;
 570                 switch (c) {
 571                 case 's':
 572                         summarize = 1;
 573                         break;
 574                 default:
 575                         usage(cmd_filesystem_du_usage);
 576                 }
 577         }
 578
 579         if (check_argc_min(argc - optind, 1))
 580                 usage(cmd_filesystem_du_usage);
 581
 582         kernel_version = get_running_kernel_version();
 583
 584         if (kernel_version < KERNEL_VERSION(2,6,33)) {
 585                 warning(
 586 "old kernel version detected, shared space will be reported as exclusive\n"
 587 "due to missing support for FIEMAP_EXTENT_SHARED flag");
 588         }
 589
 590         printf("%10s  %10s  %10s  %s\n", "Total", "Exclusive", "Set shared",
 591                         "Filename");
 592
 593         for (i = optind; i < argc; i++) {
 594                 ret = du_add_file(argv[i], AT_FDCWD, NULL, NULL, NULL, 1);
 595                 if (ret) {
 596                         error("cannot check space of '%s': %s", argv[i],
 597                                         strerror(-ret));
 598                         err = 1;
 599                 }
 600
 601                 /* reset hard-link detection for each argument */
 602                 clear_seen_inodes();
 603         }
 604
 605         return err;
 606 }