X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=cmds-fi-du.c;h=8a44665cee3b515dc92d881746ca665d7dea95ee;hb=64f3dc013676544d3f6142a80cfef99644e4e49a;hp=b413b611867ca2e9fbce0aa72970e0026de32dc6;hpb=a2e7ff1eae45ad77d80d31d8b793021364573a74;p=platform%2Fupstream%2Fbtrfs-progs.git

diff --git a/cmds-fi-du.c b/cmds-fi-du.c
index b413b61..8a44665 100644
--- a/cmds-fi-du.c
+++ b/cmds-fi-du.c
@@ -27,19 +27,176 @@
 
 #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;
@@ -78,12 +235,12 @@ static int mark_inode_seen(u64 ino, u64 subvol)
 		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;
@@ -109,20 +266,25 @@ static int inode_seen(u64 ino, u64 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,
@@ -130,8 +292,8 @@ const char * const cmd_filesystem_du_usage[] = {
  * 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;
@@ -142,28 +304,19 @@ static int du_calc_file_space(int dirfd, const char *filename,
 	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 */
@@ -180,9 +333,24 @@ static int du_calc_file_space(int dirfd, const char *filename,
 			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 +
@@ -193,32 +361,31 @@ static int du_calc_file_space(int dirfd, const char *filename,
 	*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);
@@ -232,10 +399,18 @@ static int du_walk_dir(struct du_dir_ctxt *ctxt)
 				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;
@@ -243,36 +418,34 @@ static int du_walk_dir(struct du_dir_ctxt *ctxt)
 		}
 	} 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;
@@ -282,44 +455,84 @@ static int du_add_file(const char *filename, int dirfd, uint64_t *ret_total,
 		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)
@@ -336,28 +549,32 @@ out:
 	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;
@@ -369,16 +586,28 @@ int cmd_filesystem_du(int argc, char **argv)
 	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;
 }