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