#include <sys/ioctl.h>
#include <linux/fs.h>
+#include <linux/version.h>
#include <linux/fiemap.h>
+#if !defined(FIEMAP_EXTENT_SHARED) && (HAVE_OWN_FIEMAP_EXTENT_SHARED_DEFINE == 1)
+#define FIEMAP_EXTENT_SHARED 0x00002000
+#endif
+
#include "utils.h"
#include "commands.h"
#include "kerncompat.h"
#include "rbtree.h"
+#include "interval_tree_generic.h"
+#include "help.h"
+#include "fsfeatures.h"
+
static int summarize = 0;
static unsigned unit_mode = UNITS_RAW;
static char path[PATH_MAX] = { 0, };
static char *pathp = path;
static char *path_max = &path[PATH_MAX - 1];
+struct shared_extent {
+ struct rb_node rb;
+ u64 start; /* Start of interval */
+ u64 last; /* Last location _in_ interval */
+ u64 __subtree_last;
+};
+
+/*
+ * extent_tree_* functions are defined in the massive interval tree
+ * macro below. This serves to illustrate the api in human-readable
+ * terms.
+ */
+static void
+extent_tree_insert(struct shared_extent *node, struct rb_root *root);
+
+static void
+extent_tree_remove(struct shared_extent *node, struct rb_root *root);
+
+static struct shared_extent *
+extent_tree_iter_first(struct rb_root *root,
+ u64 start, u64 last);
+
+static struct shared_extent *
+extent_tree_iter_next(struct shared_extent *node,
+ u64 start, u64 last);
+
+#define START(node) ((node)->start)
+#define LAST(node) ((node)->last)
+
+INTERVAL_TREE_DEFINE(struct shared_extent, rb,
+ u64, __subtree_last,
+ START, LAST, static, extent_tree)
+
+static int add_shared_extent(u64 start, u64 len, struct rb_root *root)
+{
+ struct shared_extent *sh;
+
+ ASSERT(len != 0);
+
+ sh = calloc(1, sizeof(*sh));
+ if (!sh)
+ return -ENOMEM;
+
+ sh->start = start;
+ sh->last = (start + len - 1);
+
+ extent_tree_insert(sh, root);
+
+ return 0;
+}
+
+static void cleanup_shared_extents(struct rb_root *root)
+{
+ struct shared_extent *s;
+ struct shared_extent *tmp;
+
+ if (!root)
+ return;
+
+ s = extent_tree_iter_first(root, 0, -1ULL);
+ while (s) {
+ tmp = extent_tree_iter_next(s, 0, -1ULL);
+ extent_tree_remove(s, root);
+
+ free(s);
+ s = tmp;
+ }
+}
+
+#define dbgprintf(...)
+
+/*
+ * Find all extents which overlap 'n', calculate the space
+ * covered by them and remove those nodes from the tree.
+ */
+static u64 count_unique_bytes(struct rb_root *root, struct shared_extent *n)
+{
+ struct shared_extent *tmp;
+ u64 wstart = n->start;
+ u64 wlast = n->last;
+
+ dbgprintf("Count overlaps:");
+
+ do {
+ /*
+ * Expand our search window based on the lastest
+ * overlapping extent. Doing this will allow us to
+ * find all possible overlaps
+ */
+ if (wstart > n->start)
+ wstart = n->start;
+ if (wlast < n->last)
+ wlast = n->last;
+
+ dbgprintf(" (%llu, %llu)", n->start, n->last);
+
+ tmp = n;
+ n = extent_tree_iter_next(n, wstart, wlast);
+
+ extent_tree_remove(tmp, root);
+ free(tmp);
+ } while (n);
+
+ dbgprintf("; wstart: %llu wlast: %llu total: %llu\n", wstart,
+ wlast, wlast - wstart + 1);
+
+ return wlast - wstart + 1;
+}
+
+/*
+ * What we want to do here is get a count of shared bytes within the
+ * set of extents we have collected. Specifically, we don't want to
+ * count any byte more than once, so just adding them up doesn't
+ * work.
+ *
+ * For each set of overlapping extents we find the lowest start and
+ * highest end. From there we have the actual number of bytes which is
+ * shared across all of the extents in our set. A sum of each sets
+ * extent length is returned.
+ */
+static void count_shared_bytes(struct rb_root *root, u64 *ret_cnt)
+{
+ u64 count = 0;
+ struct shared_extent *s = extent_tree_iter_first(root,
+ 0, -1ULL);
+
+ if (!s)
+ goto out;
+
+ while (s) {
+ /*
+ * Find all extents which overlap 's', calculate the space
+ * covered by them and remove those nodes from the tree.
+ */
+ count += count_unique_bytes(root, s);
+
+ /*
+ * Since count_unique_bytes will be emptying the tree,
+ * we can grab the first node here
+ */
+ s = extent_tree_iter_first(root, 0, -1ULL);
+ }
+
+ BUG_ON(!RB_EMPTY_ROOT(root));
+out:
+ *ret_cnt = count;
+}
+
/* Track which inodes we've seen for the purposes of hardlink detection. */
struct seen_inode {
struct rb_node i_node;
else if (cmp > 0)
p = &(*p)->rb_right;
else
- BUG();
+ return -EEXIST;
}
si = calloc(1, sizeof(*si));
if (!si)
- return ENOMEM;
+ return -ENOMEM;
si->i_ino = ino;
si->i_subvol = subvol;
else if (cmp > 0)
n = n->rb_right;
else
- return EEXIST;
+ return -EEXIST;
}
return 0;
-
}
-const char * const cmd_filesystem_du_usage[] = {
- "btrfs filesystem du [options] <path> [<path>..]",
- "Summarize disk usage of each file.",
- "-h|--human-readable",
- " human friendly numbers, base 1024 (default)",
- "-s display only a total for each argument",
- NULL
-};
+static void clear_seen_inodes(void)
+{
+ struct rb_node *n = rb_first(&seen_inodes);
+ struct seen_inode *si;
+
+ while (n) {
+ si = rb_entry(n, struct seen_inode, i_node);
+
+ rb_erase(&si->i_node, &seen_inodes);
+ free(si);
+
+ n = rb_first(&seen_inodes);
+ }
+}
/*
* Inline extents are skipped because they do not take data space,
* space they will use yet.
*/
#define SKIP_FLAGS (FIEMAP_EXTENT_UNKNOWN|FIEMAP_EXTENT_DELALLOC|FIEMAP_EXTENT_DATA_INLINE)
-static int du_calc_file_space(int dirfd, const char *filename,
- uint64_t *ret_total, uint64_t *ret_shared)
+static int du_calc_file_space(int fd, struct rb_root *shared_extents,
+ u64 *ret_total, u64 *ret_shared)
{
char buf[16384];
struct fiemap *fiemap = (struct fiemap *)buf;
int last = 0;
int rc;
u64 ext_len;
- int fd;
u64 file_total = 0;
u64 file_shared = 0;
u32 flags;
memset(fiemap, 0, sizeof(struct fiemap));
- fd = openat(dirfd, filename, O_RDONLY);
- if (fd == -1) {
- ret = errno;
- fprintf(stderr, "ERROR: can't access '%s': %s\n",
- filename, strerror(ret));
- return ret;
- }
-
do {
fiemap->fm_length = ~0ULL;
fiemap->fm_extent_count = count;
rc = ioctl(fd, FS_IOC_FIEMAP, (unsigned long) fiemap);
if (rc < 0) {
- ret = errno;
- goto out_close;
+ ret = -errno;
+ goto out;
}
/* If 0 extents are returned, then more ioctls are not needed */
if (flags & SKIP_FLAGS)
continue;
+ if (ext_len == 0) {
+ warning("extent %llu has length 0, skipping",
+ (unsigned long long)fm_ext[i].fe_physical);
+ continue;
+ }
+
file_total += ext_len;
- if (flags & FIEMAP_EXTENT_SHARED)
+ if (flags & FIEMAP_EXTENT_SHARED) {
file_shared += ext_len;
+
+ if (shared_extents) {
+ ret = add_shared_extent(fm_ext[i].fe_physical,
+ ext_len,
+ shared_extents);
+ if (ret)
+ goto out;
+ }
+ }
}
fiemap->fm_start = (fm_ext[i - 1].fe_logical +
*ret_shared = file_shared;
ret = 0;
-out_close:
- close(fd);
+out:
return ret;
}
struct du_dir_ctxt {
- uint64_t bytes_total;
- uint64_t bytes_shared;
+ u64 bytes_total;
+ u64 bytes_shared;
+ DIR *dirstream;
+ struct rb_root shared_extents;
};
+#define INIT_DU_DIR_CTXT (struct du_dir_ctxt) { 0ULL, 0ULL, NULL, RB_ROOT }
-static int du_add_file(const char *filename, int dirfd, uint64_t *ret_total,
- uint64_t *ret_shared, int top_level);
+static int du_add_file(const char *filename, int dirfd,
+ struct rb_root *shared_extents, u64 *ret_total,
+ u64 *ret_shared, int top_level);
-static int du_walk_dir(struct du_dir_ctxt *ctxt)
+static int du_walk_dir(struct du_dir_ctxt *ctxt, struct rb_root *shared_extents)
{
- int fd, ret, type;
- DIR *dirstream = NULL;
+ int ret, type;
struct dirent *entry;
-
- fd = open_file_or_dir(path, &dirstream);
- if (fd < 0)
- return fd;
+ DIR *dirstream = ctxt->dirstream;
ret = 0;
do {
- uint64_t tot, shr;
+ u64 tot, shr;
errno = 0;
entry = readdir(dirstream);
tot = shr = 0;
ret = du_add_file(entry->d_name,
- dirfd(dirstream), &tot,
- &shr, 0);
- if (ret)
+ dirfd(dirstream),
+ shared_extents, &tot, &shr,
+ 0);
+ if (ret == -ENOTTY) {
+ ret = 0;
+ continue;
+ } else if (ret) {
+ fprintf(stderr,
+ "failed to walk dir/file: %s :%s\n",
+ entry->d_name, strerror(-ret));
break;
+ }
ctxt->bytes_total += tot;
ctxt->bytes_shared += shr;
}
} while (entry != NULL);
- close_file_or_dir(fd, dirstream);
return ret;
}
-static int du_add_file(const char *filename, int dirfd, uint64_t *ret_total,
- uint64_t *ret_shared, int top_level)
+static int du_add_file(const char *filename, int dirfd,
+ struct rb_root *shared_extents, u64 *ret_total,
+ u64 *ret_shared, int top_level)
{
int ret, len = strlen(filename);
char *pathtmp;
struct stat st;
- struct du_dir_ctxt dir;
- uint64_t file_total = 0;
- uint64_t file_shared = 0;
- u64 subvol;
+ struct du_dir_ctxt dir = INIT_DU_DIR_CTXT;
+ int is_dir = 0;
+ u64 file_total = 0;
+ u64 file_shared = 0;
+ u64 dir_set_shared = 0;
int fd;
DIR *dirstream = NULL;
ret = fstatat(dirfd, filename, &st, 0);
- if (ret) {
- ret = errno;
- return ret;
- }
+ if (ret)
+ return -errno;
if (!S_ISREG(st.st_mode) && !S_ISDIR(st.st_mode))
return 0;
if (len > (path_max - pathp)) {
- fprintf(stderr, "ERROR: Path max exceeded: %s %s\n", path,
- filename);
- return ENAMETOOLONG;
+ error("path too long: %s %s", path, filename);
+ return -ENAMETOOLONG;
}
pathtmp = pathp;
ret = sprintf(pathp, "/%s", filename);
pathp += ret;
- fd = open_file_or_dir(path, &dirstream);
+ fd = open_file_or_dir3(path, &dirstream, O_RDONLY);
if (fd < 0) {
- ret = fd;
+ ret = -errno;
goto out;
}
- ret = lookup_ino_rootid(fd, &subvol);
- if (ret)
- goto out_close;
+ /*
+ * If st.st_ino == BTRFS_EMPTY_SUBVOL_DIR_OBJECTID ==2, there is no any
+ * related tree
+ */
+ if (st.st_ino != BTRFS_EMPTY_SUBVOL_DIR_OBJECTID) {
+ u64 subvol;
- if (inode_seen(st.st_ino, subvol))
- goto out_close;
+ ret = lookup_path_rootid(fd, &subvol);
+ if (ret)
+ goto out_close;
- ret = mark_inode_seen(st.st_ino, subvol);
- if (ret)
- goto out_close;
+ if (inode_seen(st.st_ino, subvol))
+ goto out_close;
+
+ ret = mark_inode_seen(st.st_ino, subvol);
+ if (ret)
+ goto out_close;
+ }
if (S_ISREG(st.st_mode)) {
- ret = du_calc_file_space(dirfd, filename, &file_total,
+ ret = du_calc_file_space(fd, shared_extents, &file_total,
&file_shared);
if (ret)
goto out_close;
} else if (S_ISDIR(st.st_mode)) {
- memset(&dir, 0, sizeof(dir));
+ struct rb_root *root = shared_extents;
+
+ /*
+ * We collect shared extents in an rb_root, the top
+ * level caller will not pass a root down, so use the
+ * one on our dir context.
+ */
+ if (top_level)
+ root = &dir.shared_extents;
- ret = du_walk_dir(&dir);
+ is_dir = 1;
+
+ dir.dirstream = dirstream;
+ ret = du_walk_dir(&dir, root);
*pathp = '\0';
- if (ret)
+ if (ret) {
+ if (top_level)
+ cleanup_shared_extents(root);
goto out_close;
+ }
file_total = dir.bytes_total;
file_shared = dir.bytes_shared;
+ if (top_level)
+ count_shared_bytes(root, &dir_set_shared);
}
if (!summarize || top_level) {
- printf("%s\t%s\t%s\n", pretty_size_mode(file_total, unit_mode),
- pretty_size_mode((file_total - file_shared), unit_mode),
- path);
+ u64 excl = file_total - file_shared;
+
+ if (top_level) {
+ u64 set_shared = file_shared;
+
+ if (is_dir)
+ set_shared = dir_set_shared;
+
+ printf("%10s %10s %10s %s\n",
+ pretty_size_mode(file_total, unit_mode),
+ pretty_size_mode(excl, unit_mode),
+ pretty_size_mode(set_shared, unit_mode),
+ path);
+ } else {
+ printf("%10s %10s %10s %s\n",
+ pretty_size_mode(file_total, unit_mode),
+ pretty_size_mode(excl, unit_mode),
+ "-", path);
+ }
}
if (ret_total)
return ret;
}
+const char * const cmd_filesystem_du_usage[] = {
+ "btrfs filesystem du [options] <path> [<path>..]",
+ "Summarize disk usage of each file.",
+ "-s|--summarize display only a total for each argument",
+ HELPINFO_UNITS_LONG,
+ NULL
+};
+
int cmd_filesystem_du(int argc, char **argv)
{
- int ret = 0, error = 0;
+ int ret = 0, err = 0;
int i;
+ u32 kernel_version;
+
+ unit_mode = get_unit_mode_from_arg(&argc, argv, 1);
- optind = 1;
while (1) {
- int long_index;
static const struct option long_options[] = {
{ "summarize", no_argument, NULL, 's'},
- { "human-readable", no_argument, NULL, 'h'},
{ NULL, 0, NULL, 0 }
};
- int c = getopt_long(argc, argv, "sh", long_options,
- &long_index);
+ int c = getopt_long(argc, argv, "s", long_options, NULL);
if (c < 0)
break;
switch (c) {
- case 'h':
- unit_mode = UNITS_HUMAN;
- break;
case 's':
summarize = 1;
break;
if (check_argc_min(argc - optind, 1))
usage(cmd_filesystem_du_usage);
- printf("total\texclusive\tfilename\n");
+ kernel_version = get_running_kernel_version();
+
+ if (kernel_version < KERNEL_VERSION(2,6,33)) {
+ warning(
+"old kernel version detected, shared space will be reported as exclusive\n"
+"due to missing support for FIEMAP_EXTENT_SHARED flag");
+ }
+
+ printf("%10s %10s %10s %s\n", "Total", "Exclusive", "Set shared",
+ "Filename");
for (i = optind; i < argc; i++) {
- ret = du_add_file(argv[i], AT_FDCWD, NULL, NULL, 1);
+ ret = du_add_file(argv[i], AT_FDCWD, NULL, NULL, NULL, 1);
if (ret) {
- fprintf(stderr, "ERROR: can't check space of '%s': %s\n",
- argv[i], strerror(ret));
- error = 1;
+ error("cannot check space of '%s': %s", argv[i],
+ strerror(-ret));
+ err = 1;
}
+
+ /* reset hard-link detection for each argument */
+ clear_seen_inodes();
}
- return error;
+ return err;
}
projects / platform / upstream / btrfs-progs.git / blobdiff