btrfs-progs: add 'du' command

Hi,

This patch adds a 'du' subcommand to btrfs. 'btrfs fi du' will calculate disk usage of the target files using fiemap. For individual files, it will report a count of total bytes, and exclusive (not shared) bytes. We also calculate a 'set shared' value which is described below.

Each argument to 'btrfs fi du' will have a 'set shared' value calculated for it. We define each 'set' as those files found by a recursive search of an argument to btrfs fi du. The 'set shared' value then is a sum of all shared space referenced by the set.

'set shared' takes into account overlapping shared extents, hence it isn't as simple as adding up shared extents. To efficiently find overlapping regions, we store them in an interval tree. When the scan of a file set is complete, we can walk the tree and calculate our actual shared bytes while also taking into account any duplicate or overlapping extents.

The interval tree implementation is taken from Linux v4.0-rc7. I went ahead and made some small comment updates to rbtree.h and rbtree_augmented.h while I was importing this code as both are used by the interval tree and I needed to check for any code changes in those headers (there weren't any).

Following this paragraph is a very simple example. I started with a clean btrfs fs in which i copied vmlinuz from /boot. I then made a snapshot of the fs root in 'snap1'. After the snapshot, I made a 2nd copy of vmlinuz into the main fs to give us some not-shared data. The output below shows a sum of all the space, and a 'set shared' with len exactly equal to that of the single shared file.

# btrfs fi du .
total	exclusive	set shared	filename
4362240	0			./vmlinuz-4.0.0-rc7
4362240	0			./snap1/vmlinuz-4.0.0-rc7
4362240	0			./snap1
4362240	4362240			./vmlinuz-4.0.0-rc7.copy
13086720	4362240	4362240	.

A git tree of the patches can be found here:

https://github.com/markfasheh/btrfs-progs-patches/tree/du

or if you prefer to pull:

git pull https://github.com/markfasheh/btrfs-progs-patches du

Attached to this e-mail is a single patch version of the change.

Comments/feedback appreciated.

index 83927e4..6095b6e 100644
@@ -40,7 +40,7 @@ cmds_objects = cmds-subvolume.o cmds-filesystem.o cmds-device.o cmds-scrub.o \
 	       cmds-inspect.o cmds-balance.o cmds-send.o cmds-receive.o \
 	       cmds-quota.o cmds-qgroup.o cmds-replace.o cmds-check.o \
 	       cmds-restore.o cmds-rescue.o chunk-recover.o super-recover.o \
-	       cmds-property.o cmds-fi-disk_usage.o
+	       cmds-property.o cmds-fi-disk_usage.o cmds-du.o
 libbtrfs_objects = send-stream.o send-utils.o rbtree.o btrfs-list.o crc32c.o \
 		   uuid-tree.o utils-lib.o rbtree-utils.o
 libbtrfs_headers = send-stream.h send-utils.h send.h rbtree.h btrfs-list.h \

new file mode 100644
index 0000000..5ffb178
@@ -0,0 +1,7 @@
+#ifndef __CMDS_DU_H__
+#define __CMDS_DU_H__
+
+extern const char * const cmd_filesystem_du_usage[];
+int cmd_filesystem_du(int argc, char **argv);
+
+#endif	/* __CMDS_DU_H__ */

index f3fc160..eb82664 100644
@@ -37,7 +37,7 @@
 #include "cmds-fi-disk_usage.h"
 #include "list_sort.h"
 #include "disk-io.h"
-
+#include "cmds-du.h"
 
 /*
  * for btrfs fi show, we maintain a hash of fsids we've already printed.

@@ -1297,6 +1297,7 @@ static int cmd_label(int argc, char **argv)
 const struct cmd_group filesystem_cmd_group = {
 	filesystem_cmd_group_usage, NULL, {
 		{ "df", cmd_filesystem_df, cmd_filesystem_df_usage, NULL, 0 },
+		{ "du", cmd_filesystem_du, cmd_filesystem_du_usage, NULL, 0 },
 		{ "show", cmd_show, cmd_show_usage, NULL, 0 },
 		{ "sync", cmd_sync, cmd_sync_usage, NULL, 0 },
 		{ "defragment", cmd_defrag, cmd_defrag_usage, NULL, 0 },

index 0d4f2bf..47b662a 100644
@@ -57,7 +57,7 @@ struct rb_root {
 
 #define RB_EMPTY_ROOT(root)  ((root)->rb_node == NULL)
 
-/* 'empty' nodes are nodes that are known not to be inserted in an rbree */
+/* 'empty' nodes are nodes that are known not to be inserted in an rtbree */
 #define RB_EMPTY_NODE(node)  \
 	((node)->__rb_parent_color == (unsigned long)(node))
 #define RB_CLEAR_NODE(node)  \

index cbc9639..5d26978 100644
@@ -46,6 +46,16 @@ struct rb_augment_callbacks {
 
 extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
 	void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
+/*
+ * Fixup the rbtree and update the augmented information when rebalancing.
+ *
+ * On insertion, the user must update the augmented information on the path
+ * leading to the inserted node, then call rb_link_node() as usual and
+ * rb_augment_inserted() instead of the usual rb_insert_color() call.
+ * If rb_augment_inserted() rebalances the rbtree, it will callback into
+ * a user provided function to update the augmented information on the
+ * affected subtrees.
+ */
 static inline void
 rb_insert_augmented(struct rb_node *node, struct rb_root *root,
 		    const struct rb_augment_callbacks *augment)

The functionality is useful, I personally like it and have seen people on irc to ask about this.

The question is whether we want to add this to a btrfs command or to the 'du' utility itself. AFAICS it's not built around FIEMAP, so I guess this would be an intrusive change.

I guess the next thing people will want to see is the compressed size.

The file interval_tree.h seems missing and build fails.

Cool, I would really like to know how close this gets to answering some of those questions regarding disk usage.

Yeah internally this is happening much differently than du. Jeff and I had talked once or twice about counting extent refs as a future enhancement, which would definitey be out of the scope of anything du does right now.

I can look into this. Maybe as a switch? How do I even get the compressed size?

If you pull the branch again you should have a fix for this.

Thanks David,

	--Mark

--
Mark Fasheh

IIRC one of the questions was 'how much do these two files share', eg. after one of the files has been reflinked and modified.

Not needed for the first implementation. The compressed size can be read from userspace by iterating the extents. I have the code for that stashed somewhere, we can add that once this patchset lands.

I've tested it, works for me, however if you want me to pull the branch please clean up the patches so the fixups are not in separate commits. Also cmds-du goes to cmds-filesystem, as it's a subcommand. Patch subjects should start with 'btrfs-progs'. The rest is the same as if it were a patchset for kernel. I do fix small things at commit time unless there are too many of them.