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