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         BUG_ON(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. Specifcally, 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                         BUG();
 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 const char * const cmd_filesystem_du_usage[] = {
 283         "btrfs filesystem du [options] <path> [<path>..]",
 284         "Summarize disk usage of each file.",
 285         "-h|--human-readable",
 286         "                   human friendly numbers, base 1024 (default)",
 287         "-s                 display only a total for each argument",
 288         NULL
 289 };
 290
 291 /*
 292  * Inline extents are skipped because they do not take data space,
 293  * delalloc and unknown are skipped because we do not know how much
 294  * space they will use yet.
 295  */
 296 #define SKIP_FLAGS      (FIEMAP_EXTENT_UNKNOWN|FIEMAP_EXTENT_DELALLOC|FIEMAP_EXTENT_DATA_INLINE)
 297 static int du_calc_file_space(int fd, struct rb_root *shared_extents,
 298                               uint64_t *ret_total, uint64_t *ret_shared)
 299 {
 300         char buf[16384];
 301         struct fiemap *fiemap = (struct fiemap *)buf;
 302         struct fiemap_extent *fm_ext = &fiemap->fm_extents[0];
 303         int count = (sizeof(buf) - sizeof(*fiemap)) /
 304                         sizeof(struct fiemap_extent);
 305         unsigned int i, ret;
 306         int last = 0;
 307         int rc;
 308         u64 ext_len;
 309         u64 file_total = 0;
 310         u64 file_shared = 0;
 311         u32 flags;
 312
 313         memset(fiemap, 0, sizeof(struct fiemap));
 314
 315         do {
 316                 fiemap->fm_length = ~0ULL;
 317                 fiemap->fm_extent_count = count;
 318                 rc = ioctl(fd, FS_IOC_FIEMAP, (unsigned long) fiemap);
 319                 if (rc < 0) {
 320                         ret = errno;
 321                         goto out;
 322                 }
 323
 324                 /* If 0 extents are returned, then more ioctls are not needed */
 325                 if (fiemap->fm_mapped_extents == 0)
 326                         break;
 327
 328                 for (i = 0; i < fiemap->fm_mapped_extents; i++) {
 329                         ext_len = fm_ext[i].fe_length;
 330                         flags = fm_ext[i].fe_flags;
 331
 332                         if (flags & FIEMAP_EXTENT_LAST)
 333                                 last = 1;
 334
 335                         if (flags & SKIP_FLAGS)
 336                                 continue;
 337
 338                         file_total += ext_len;
 339                         if (flags & FIEMAP_EXTENT_SHARED) {
 340                                 file_shared += ext_len;
 341
 342                                 if (shared_extents) {
 343                                         ret = add_shared_extent(fm_ext[i].fe_physical,
 344                                                                 ext_len,
 345                                                                 shared_extents);
 346                                         if (ret)
 347                                                 goto out;
 348                                 }
 349                         }
 350                 }
 351
 352                 fiemap->fm_start = (fm_ext[i - 1].fe_logical +
 353                                     fm_ext[i - 1].fe_length);
 354         } while (last == 0);
 355
 356         *ret_total = file_total;
 357         *ret_shared = file_shared;
 358
 359         ret = 0;
 360 out:
 361         return ret;
 362 }
 363
 364 struct du_dir_ctxt {
 365         uint64_t        bytes_total;
 366         uint64_t        bytes_shared;
 367         DIR             *dirstream;
 368         struct rb_root  shared_extents;
 369 };
 370 #define INIT_DU_DIR_CTXT        (struct du_dir_ctxt) { 0ULL, 0ULL, NULL, RB_ROOT }
 371
 372 static int du_add_file(const char *filename, int dirfd,
 373                        struct rb_root *shared_extents, uint64_t *ret_total,
 374                        uint64_t *ret_shared, int top_level);
 375
 376 static int du_walk_dir(struct du_dir_ctxt *ctxt, struct rb_root *shared_extents)
 377 {
 378         int ret, type;
 379         struct dirent *entry;
 380         DIR *dirstream = ctxt->dirstream;
 381
 382         ret = 0;
 383         do {
 384                 uint64_t tot, shr;
 385
 386                 errno = 0;
 387                 entry = readdir(dirstream);
 388                 if (entry) {
 389                         if (strcmp(entry->d_name, ".") == 0
 390                             || strcmp(entry->d_name, "..") == 0)
 391                                 continue;
 392
 393                         type = entry->d_type;
 394                         if (type == DT_REG || type == DT_DIR) {
 395                                 tot = shr = 0;
 396
 397                                 ret = du_add_file(entry->d_name,
 398                                                   dirfd(dirstream),
 399                                                   shared_extents, &tot, &shr,
 400                                                   0);
 401                                 if (ret)
 402                                         break;
 403
 404                                 ctxt->bytes_total += tot;
 405                                 ctxt->bytes_shared += shr;
 406                         }
 407                 }
 408         } while (entry != NULL);
 409
 410         return ret;
 411 }
 412
 413 static int du_add_file(const char *filename, int dirfd,
 414                        struct rb_root *shared_extents, uint64_t *ret_total,
 415                        uint64_t *ret_shared, int top_level)
 416 {
 417         int ret, len = strlen(filename);
 418         char *pathtmp;
 419         struct stat st;
 420         struct du_dir_ctxt dir = INIT_DU_DIR_CTXT;
 421         int is_dir = 0;
 422         uint64_t file_total = 0;
 423         uint64_t file_shared = 0;
 424         u64 dir_set_shared = 0;
 425         u64 subvol;
 426         int fd;
 427         DIR *dirstream = NULL;
 428
 429         ret = fstatat(dirfd, filename, &st, 0);
 430         if (ret) {
 431                 ret = errno;
 432                 return ret;
 433         }
 434
 435         if (!S_ISREG(st.st_mode) && !S_ISDIR(st.st_mode))
 436                 return 0;
 437
 438         if (len > (path_max - pathp)) {
 439                 fprintf(stderr, "ERROR: Path max exceeded: %s %s\n", path,
 440                         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_dir(path, &dirstream);
 452         if (fd < 0) {
 453                 ret = fd;
 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("%s\t%s\t%s\t%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("%s\t%s\t\t\t%s\n",
 517                                pretty_size_mode(file_total, unit_mode),
 518                                pretty_size_mode(excl, unit_mode), path);
 519                 }
 520         }
 521
 522         if (ret_total)
 523                 *ret_total = file_total;
 524         if (ret_shared)
 525                 *ret_shared = file_shared;
 526
 527 out_close:
 528         close_file_or_dir(fd, dirstream);
 529 out:
 530         /* reset path to just before this element */
 531         pathp = pathtmp;
 532
 533         return ret;
 534 }
 535
 536 int cmd_filesystem_du(int argc, char **argv)
 537 {
 538         int ret = 0, error = 0;
 539         int i;
 540
 541         optind = 1;
 542         while (1) {
 543                 int long_index;
 544                 static const struct option long_options[] = {
 545                         { "summarize", no_argument, NULL, 's'},
 546                         { "human-readable", no_argument, NULL, 'h'},
 547                         { NULL, 0, NULL, 0 }
 548                 };
 549                 int c = getopt_long(argc, argv, "sh", long_options,
 550                                 &long_index);
 551
 552                 if (c < 0)
 553                         break;
 554                 switch (c) {
 555                 case 'h':
 556                         unit_mode = UNITS_HUMAN;
 557                         break;
 558                 case 's':
 559                         summarize = 1;
 560                         break;
 561                 default:
 562                         usage(cmd_filesystem_du_usage);
 563                 }
 564         }
 565
 566         if (check_argc_min(argc - optind, 1))
 567                 usage(cmd_filesystem_du_usage);
 568
 569         printf("total\texclusive\tset shared\tfilename\n");
 570
 571         for (i = optind; i < argc; i++) {
 572                 ret = du_add_file(argv[i], AT_FDCWD, NULL, NULL, NULL, 1);
 573                 if (ret) {
 574                         fprintf(stderr, "ERROR: can't check space of '%s': %s\n",
 575                                 argv[i], strerror(ret));
 576                         error = 1;
 577                 }
 578
 579                 /* reset hard-link detection for each argument */
 580                 clear_seen_inodes();
 581         }
 582
 583         return error;
 584 }