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