"Fossies" - the Fresh Open Source Software Archive

Member "btrfs-progs-v5.4/cmds/filesystem-du.c" (3 Dec 2019, 13767 Bytes) of package /linux/misc/btrfs-progs-v5.4.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "filesystem-du.c" see the Fossies "Dox" file reference documentation.

    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 "common/utils.h"
   38 #include "cmds/commands.h"
   39 #include "kerncompat.h"
   40 #include "kernel-lib/rbtree.h"
   41 
   42 #include "kernel-lib/interval_tree_generic.h"
   43 #include "common/help.h"
   44 #include "common/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                     errno = -ret;
  410                     fprintf(stderr,
  411                     "failed to walk dir/file: %s : %m\n",
  412                         entry->d_name);
  413                     break;
  414                 }
  415 
  416                 ctxt->bytes_total += tot;
  417                 ctxt->bytes_shared += shr;
  418             }
  419         }
  420     } while (entry != NULL);
  421 
  422     return ret;
  423 }
  424 
  425 static int du_add_file(const char *filename, int dirfd,
  426                struct rb_root *shared_extents, u64 *ret_total,
  427                u64 *ret_shared, int top_level)
  428 {
  429     int ret, len = strlen(filename);
  430     char *pathtmp;
  431     struct stat st;
  432     struct du_dir_ctxt dir = INIT_DU_DIR_CTXT;
  433     int is_dir = 0;
  434     u64 file_total = 0;
  435     u64 file_shared = 0;
  436     u64 dir_set_shared = 0;
  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 || *(pathp - 1) == '/')
  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     /*
  466      * If st.st_ino == BTRFS_EMPTY_SUBVOL_DIR_OBJECTID ==2, there is no any
  467      * related tree
  468      */
  469     if (st.st_ino != BTRFS_EMPTY_SUBVOL_DIR_OBJECTID) {
  470         u64 subvol;
  471 
  472         ret = lookup_path_rootid(fd, &subvol);
  473         if (ret)
  474             goto out_close;
  475 
  476         if (inode_seen(st.st_ino, subvol))
  477             goto out_close;
  478 
  479         ret = mark_inode_seen(st.st_ino, subvol);
  480         if (ret)
  481             goto out_close;
  482     }
  483 
  484     if (S_ISREG(st.st_mode)) {
  485         ret = du_calc_file_space(fd, shared_extents, &file_total,
  486                      &file_shared);
  487         if (ret)
  488             goto out_close;
  489     } else if (S_ISDIR(st.st_mode)) {
  490         struct rb_root *root = shared_extents;
  491 
  492         /*
  493          * We collect shared extents in an rb_root, the top
  494          * level caller will not pass a root down, so use the
  495          * one on our dir context.
  496          */
  497         if (top_level)
  498             root = &dir.shared_extents;
  499 
  500         is_dir = 1;
  501 
  502         dir.dirstream = dirstream;
  503         ret = du_walk_dir(&dir, root);
  504         *pathp = '\0';
  505         if (ret) {
  506             if (top_level)
  507                 cleanup_shared_extents(root);
  508             goto out_close;
  509         }
  510 
  511         file_total = dir.bytes_total;
  512         file_shared = dir.bytes_shared;
  513         if (top_level)
  514             count_shared_bytes(root, &dir_set_shared);
  515     }
  516 
  517     if (!summarize || top_level) {
  518         u64 excl = file_total - file_shared;
  519 
  520         if (top_level) {
  521             u64 set_shared = file_shared;
  522 
  523             if (is_dir)
  524                 set_shared = dir_set_shared;
  525 
  526             printf("%10s  %10s  %10s  %s\n",
  527                    pretty_size_mode(file_total, unit_mode),
  528                    pretty_size_mode(excl, unit_mode),
  529                    pretty_size_mode(set_shared, unit_mode),
  530                    path);
  531         } else {
  532             printf("%10s  %10s  %10s  %s\n",
  533                    pretty_size_mode(file_total, unit_mode),
  534                    pretty_size_mode(excl, unit_mode),
  535                    "-", path);
  536         }
  537     }
  538 
  539     if (ret_total)
  540         *ret_total = file_total;
  541     if (ret_shared)
  542         *ret_shared = file_shared;
  543 
  544 out_close:
  545     close_file_or_dir(fd, dirstream);
  546 out:
  547     /* reset path to just before this element */
  548     pathp = pathtmp;
  549 
  550     return ret;
  551 }
  552 
  553 static const char * const cmd_filesystem_du_usage[] = {
  554     "btrfs filesystem du [options] <path> [<path>..]",
  555     "Summarize disk usage of each file.",
  556     "",
  557     "-s|--summarize     display only a total for each argument",
  558     HELPINFO_UNITS_LONG,
  559     NULL
  560 };
  561 
  562 static int cmd_filesystem_du(const struct cmd_struct *cmd,
  563                  int argc, char **argv)
  564 {
  565     int ret = 0, err = 0;
  566     int i;
  567     u32 kernel_version;
  568 
  569     unit_mode = get_unit_mode_from_arg(&argc, argv, 1);
  570 
  571     optind = 0;
  572     while (1) {
  573         static const struct option long_options[] = {
  574             { "summarize", no_argument, NULL, 's'},
  575             { NULL, 0, NULL, 0 }
  576         };
  577         int c = getopt_long(argc, argv, "s", long_options, NULL);
  578 
  579         if (c < 0)
  580             break;
  581         switch (c) {
  582         case 's':
  583             summarize = 1;
  584             break;
  585         default:
  586             usage_unknown_option(cmd, argv);
  587         }
  588     }
  589 
  590     if (check_argc_min(argc - optind, 1))
  591         return 1;
  592 
  593     kernel_version = get_running_kernel_version();
  594 
  595     if (kernel_version < KERNEL_VERSION(2,6,33)) {
  596         warning(
  597 "old kernel version detected, shared space will be reported as exclusive\n"
  598 "due to missing support for FIEMAP_EXTENT_SHARED flag");
  599     }
  600 
  601     printf("%10s  %10s  %10s  %s\n", "Total", "Exclusive", "Set shared",
  602             "Filename");
  603 
  604     for (i = optind; i < argc; i++) {
  605         ret = du_add_file(argv[i], AT_FDCWD, NULL, NULL, NULL, 1);
  606         if (ret) {
  607             errno = -ret;
  608             error("cannot check space of '%s': %m", argv[i]);
  609             err = 1;
  610         }
  611 
  612         /* reset hard-link detection for each argument */
  613         clear_seen_inodes();
  614     }
  615 
  616     return err;
  617 }
  618 DEFINE_SIMPLE_COMMAND(filesystem_du, "du");