Skip to contentSkip to conversation

du_enhancement: add the shared extents and the footprint statistics support v1

PATCH New Jeff Liu 4 participants 10 messages Jan 26, 2010 – Feb 8, 2010

Subsystems (2)
Library code OCFS2
lore
Share & tools
lore

Jeff Liu

author
#0 lore raw

PATCH 1/4 du_enhancement: add the shared extents and the footprint statistics support v1

brief introduction:

the following patch sets add a new feature to displapy the shared extents size per file as well as the overall footprint statistics for du command.

It using rbtree to track the splitted extents info instead of the clusters or physical blocks to save the memory in case of the file size is too large(TB, etc).

the current extent splitting algorithem is based on Tao's idea, thanks a lot!

use '--shared-size' or '-E' as the command line trigger, with this option, du print out the shared extents in parens for each file if its resides filesystem support fiemap and the file is reflinked.

use '--fxattr' or '--fsync' or both of them to work combine with '--shared-size' for the extra fiemap control, it will print warning message on the console in case of the filesystem do not support the corresponding fiemap flags.

Signed-off-by Jeff Liu <[email protected]>
---
 gnulib |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)
gnulib +1 -1
index 8fc05d0..4b93a25 160000
@@ -1 +1 @@
-Subproject commit 8fc05d032b3f9a9d068613ab5ee297b4e7d5a08a
+Subproject commit 4b93a2579fb567b9fbbeb24439770d814dac95cd
Signature · 1 line
1.5.4.3
author
#1 lore raw

PATCH 2/4 du_enhancement: add rbtree algorithm support

rbtree algorithm copy from ocfs2-tools

Signed-off-by Jeff Liu <[email protected]>
---
 lib/Makefile.am |    3 +-
 lib/rbtree.c    |  395 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 lib/rbtree.h    |  143 ++++++++++++++++++++
 3 files changed, 540 insertions(+), 1 deletions(-)
 create mode 100644 lib/rbtree.c
 create mode 100644 lib/rbtree.h
lib/Makefile.am +2 -1
index c89ef75..2b814d8 100644
@@ -21,7 +21,8 @@ AM_CFLAGS += $(GNULIB_WARN_CFLAGS) $(WERROR_CFLAGS)
 
 libcoreutils_a_SOURCES += \
   buffer-lcm.c buffer-lcm.h \
-  xmemxfrm.c xmemxfrm.h
+  xmemxfrm.c xmemxfrm.h \
+  rbtree.c rbtree.h
 
 libcoreutils_a_LIBADD += $(LIBOBJS)
 libcoreutils_a_DEPENDENCIES += $(LIBOBJS)
lib/rbtree.c new file +395 -0

395 lines not on this page · raw message

lib/rbtree.h new file +143 -0

143 lines not on this page · raw message

Signature · 1 line
1.5.4.3
author
#2 lore raw

PATCH 3/4 du_enhancement: add fiemap header

copy to source dir for the moment, is it a proper place?

Signed-off-by Jeff Liu <[email protected]>
---
 src/fiemap.h |   68 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 68 insertions(+), 0 deletions(-)
 create mode 100644 src/fiemap.h
src/fiemap.h new file +68 -0
new file mode 100644
index 0000000..df3a32c
@@ -0,0 +1,68 @@
+/*
+ * FS_IOC_FIEMAP ioctl infrastructure.
+ *
+ * Some portions copyright (C) 2007 Cluster File Systems, Inc
+ *
+ * Authors: Mark Fasheh <[email protected]>
+ *          Kalpak Shah <[email protected]>
+ *          Andreas Dilger <[email protected]>
+ */
+
+#ifndef _LINUX_FIEMAP_H
+#define _LINUX_FIEMAP_H
+
+#include <linux/types.h>
+
+struct fiemap_extent {
+  uint64_t fe_logical;  /* logical offset in bytes for the start of
+                         * the extent from the beginning of the file */
+  uint64_t fe_physical; /* physical offset in bytes for the start
+                         * of the extent from the beginning of the disk */
+  uint64_t fe_length;   /* length in bytes for this extent */
+  uint64_t fe_reserved64[2];
+  uint32_t fe_flags;    /* FIEMAP_EXTENT_* flags for this extent */
+  uint32_t fe_reserved[3];
+};
+
+struct fiemap {
+  uint64_t fm_start;                  /* logical offset (inclusive) at
+				       * which to start mapping (in) */
+  uint64_t fm_length;                 /* logical length of mapping which
+				       * userspace wants (in) */
+  uint32_t fm_flags;                  /* FIEMAP_FLAG_* flags for request (in/out) */
+  uint32_t fm_mapped_extents;         /* number of extents that were mapped (out) */
+  uint32_t fm_extent_count;           /* size of fm_extents array (in) */
+  uint32_t fm_reserved;
+  struct fiemap_extent fm_extents[0]; /* array of mapped extents (out) */
+};
+
+#define FIEMAP_MAX_OFFSET	(~0ULL)
+
+#define FIEMAP_FLAG_SYNC	0x00000001 /* sync file data before map */
+#define FIEMAP_FLAG_XATTR	0x00000002 /* map extended attribute tree */
+
+#define FIEMAP_FLAGS_COMPAT	(FIEMAP_FLAG_SYNC | FIEMAP_FLAG_XATTR)
+
+#define FIEMAP_EXTENT_LAST		0x00000001 /* Last extent in file. */
+#define FIEMAP_EXTENT_UNKNOWN		0x00000002 /* Data location unknown. */
+#define FIEMAP_EXTENT_DELALLOC		0x00000004 /* Location still pending.
+						    * Sets EXTENT_UNKNOWN. */
+#define FIEMAP_EXTENT_ENCODED		0x00000008 /* Data can not be read
+						    * while fs is unmounted */
+#define FIEMAP_EXTENT_DATA_ENCRYPTED	0x00000080 /* Data is encrypted by fs.
+						    * Sets EXTENT_NO_BYPASS. */
+#define FIEMAP_EXTENT_NOT_ALIGNED	0x00000100 /* Extent offsets may not be
+						    * block aligned. */
+#define FIEMAP_EXTENT_DATA_INLINE	0x00000200 /* Data mixed with metadata.
+						    * Sets EXTENT_NOT_ALIGNED.*/
+#define FIEMAP_EXTENT_DATA_TAIL		0x00000400 /* Multiple files in block.
+						    * Sets EXTENT_NOT_ALIGNED.*/
+#define FIEMAP_EXTENT_UNWRITTEN		0x00000800 /* Space allocated, but
+						    * no data (i.e. zero). */
+#define FIEMAP_EXTENT_MERGED		0x00001000 /* File does not natively
+						    * support extents. Result
+						    * merged for efficiency. */
+#define FIEMAP_EXTENT_SHARED		0x00002000 /* Space shared with other
+						    * files. */
+
+#endif /* _LINUX_FIEMAP_H */
Signature · 1 line
1.5.4.3
author
#3 lore raw

PATCH 4/4 du_enhancement: show the shared extents per file and the footprint

this patch add fiemap feature support in du, du show the shared extents size in parens per file as well as the footprint for each request with either '--shared-size' or '-E' option.

the footprint which is total minus the sum total of all extents in the rbtree that have ei_shared_count > 0.

Signed-off-by Jeff Liu <[email protected]>
---
 lib/rbtree.h |    4 +-
 src/du.c     |  378 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 378 insertions(+), 4 deletions(-)
lib/rbtree.h +2 -2
index ad646b1..bb23391 100644
@@ -112,8 +112,8 @@ struct rb_root
   };
 
 #define RB_ROOT	(struct rb_root) { NULL, }
-#define	rb_entry (ptr, type, member)                              \
-  ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
+#define	rb_entry(ptr, type, member) \
+	((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
 
 extern void rb_insert_color (struct rb_node *, struct rb_root *);
 extern void rb_erase (struct rb_node *, struct rb_root *);
src/du.c +376 -2

466 lines not on this page · raw message

Signature · 1 line
1.5.4.3
#4 lore raw

PATCH 4/4 du_enhancement: show the shared extents per file and the footprint

Hi Jeff,
Thanks for the work. and sorry for the delay of review.

Quoted 17 lines · Jeff Liu

this patch add fiemap feature support in du, du show the shared extents size in parens per file as well as the footprint for each request with either '--shared-size' or '-E' option.

the footprint which is total minus the sum total of all extents in the rbtree that have ei_shared_count > 0.

Signed-off-by Jeff Liu <[email protected]>
---
 lib/rbtree.h |    4 +-
 src/du.c     |  378 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 378 insertions(+), 4 deletions(-)
lib/rbtree.h +0 -0
index ad646b1..bb23391 100644

lib/rbtree.h struct rb_root · line 116

Quoted 7 lines
lib/rbtree.h +2 -2
@@ -112,8 +112,8 @@ struct rb_root
   };
 
 #define RB_ROOT	(struct rb_root) { NULL, }
-#define	rb_entry (ptr, type, member)                              \
-  ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
+#define	rb_entry(ptr, type, member) \
+	((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

I haven't found what you change for this 2 lines. Just change the place of '\"?

Quoted 3 lines
lib/rbtree.h +0 -0
 extern void rb_insert_color (struct rb_node *, struct rb_root *);
 extern void rb_erase (struct rb_node *, struct rb_root *);

<snip>

Quoted 20 lines
lib/rbtree.h +20 -0
+/* Split the new extent into mutiple items if there is overlap
+   with the search returned, insert each item  or increase the
+   existed items shared count for the shared part.  */
+
+static void
+split_extent (uint64_t extent_physical_offset,
+              uint64_t extent_length)
+{
+  struct rb_node *parent = NULL;
+  struct rb_node *prev_parent = NULL;
+  struct extent_info *this;
+  uint64_t pb_start = extent_physical_offset;
+  uint64_t ext_len = extent_length;
+  uint64_t new_pb_start;
+  uint64_t new_ext_len;
+  uint64_t old_ext_len;
+  size_t ext_shared_count = 0;
+
+  parent = lookup_leftmost_extent_info (pb_start);
+

lib/rbtree.h

Quoted 10 lines
lib/rbtree.h +10 -0
+  while (ext_len)
+    {
+      if (!parent)
+        {
+          insert_new_extent_info (prev_parent, pb_start, ext_len, ext_shared_count);
+	  break;
+	}
+
+      this = rb_entry (parent, struct extent_info, ei_node);
+

Could you please add more comments on the later codes? It is a little complicated for analysis.

lib/rbtree.h

Quoted 4 lines
lib/rbtree.h +4 -0
+      if (pb_start < this->ei_physical)
+	{
+	  new_ext_len = min (this->ei_physical - pb_start, ext_len);
+          insert_new_extent_info (parent, pb_start, new_ext_len, ext_shared_count);

here is a bug, you need to set ext_shared_count to 0 since the later code will change it.

Quoted 13 lines
lib/rbtree.h +13 -0
+
+          pb_start += new_ext_len;
+	  ext_len -= new_ext_len;
+          continue;
+        }
+
+      if (pb_start == this->ei_physical)
+        {
+	  ext_shared_count = this->ei_shared_count;
+          old_ext_len = this->ei_length;
+          new_ext_len = min (ext_len, this->ei_length);
+
+          this->ei_length = new_ext_len;

lib/rbtree.h

Quoted 10 lines
lib/rbtree.h +10 -0
+          this->ei_shared_count++;
+
+          pb_start += new_ext_len;
+          ext_len -= new_ext_len;
+
+          if (old_ext_len > new_ext_len)
+            {
+	      new_pb_start = this->ei_physical + this->ei_length;
+	      new_ext_len = old_ext_len - new_ext_len;
+	      insert_new_extent_info (parent, new_pb_start, new_ext_len, ext_shared_count);

here you have add a new extent info but forget to increase pb_start and decrease ext_len. Also we need to reset ext_shared_count to 0 before insert.

Quoted 7 lines
lib/rbtree.h +7 -0
+	    }
+
+          prev_parent = parent;
+          parent = rb_next (parent);
+          continue;
+        }
+

lib/rbtree.h

Quoted 10 lines
lib/rbtree.h +10 -0
+      if (pb_start < this->ei_physical + this->ei_length)
+        {
+	  old_ext_len = this->ei_physical + this->ei_length - pb_start;
+	  new_ext_len = min (ext_len, old_ext_len);
+
+          ext_shared_count = this->ei_shared_count;
+	  if (new_ext_len < old_ext_len)
+            insert_new_extent_info (parent, pb_start, new_ext_len, ext_shared_count);
+	  else
+	    insert_new_extent_info (parent, pb_start, old_ext_len, ext_shared_count);

We need to ext_shared_count++ for the insert_new_extent_info? btw, only one line is enough:
insert_new_extent_info(parent, pb_start, new_ext_len, ext_shared_count); new_ext_len is <= old_ext_len because of the above min, so we are safe for the above 2 cases.

lib/rbtree.h

Quoted 13 lines
lib/rbtree.h +13 -0
+
+          this->ei_length = pb_start - this->ei_physical;
+
+	  pb_start += new_ext_len;
+	  ext_len -= new_ext_len;
+          parent = rb_next (parent);
+          continue;
+        }
+
+      prev_parent = parent;
+      parent = rb_next (parent);
+    }
+}

Regards,
Tao

author
#5 lore raw

PATCH 4/4 du_enhancement: show the shared extents per file and the footprint

Hi Tao,

Thanks for your help review.

Tao Ma ??:

Quoted 27 lines

Hi Jeff,
Thanks for the work. and sorry for the delay of review.

Quoted 23 lines · Jeff Liu

this patch add fiemap feature support in du, du show the shared extents size in parens per file
as well as the footprint for each request with either '--shared-size' or '-E' option.

the footprint which is total minus the sum total of all extents in the rbtree
that have ei_shared_count > 0.

Signed-off-by Jeff Liu <[email protected]>

---
lib/rbtree.h | 4 +-
src/du.c | 378
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++-

2 files changed, 378 insertions(+), 4 deletions(-)
lib/rbtree.h +0 -0
index ad646b1..bb23391 100644
@@ -112,8 +112,8 @@ struct rb_root
 };
Quoted 7 lines

lib/rbtree.h struct rb_root · line 116

Quoted 5 lines
lib/rbtree.h +2 -2
 #define RB_ROOT (struct rb_root) { NULL, }
-#define rb_entry (ptr, type, member) \
- ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
+#define rb_entry(ptr, type, member) \
+ ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

I haven't found what you change for this 2 lines. Just change the place of '\"?

There were 2 minor syntax changes here to satisfy the compiler. First is to omit the 'blank space' between 'rb_entry' and '('. actually, add a 'blank space' between the function name and '(' is the GNU coding style, we should abide by.

Another is place change of the '\' just as you mentioned above, or the compile process will broken as well.

Quoted 29 lines
Quoted 3 lines
lib/rbtree.h +0 -0
 extern void rb_insert_color (struct rb_node *, struct rb_root *);
 extern void rb_erase (struct rb_node *, struct rb_root *);

<snip>

Quoted 25 lines
lib/rbtree.h +25 -0
+/* Split the new extent into mutiple items if there is overlap
+ with the search returned, insert each item or increase the
+ existed items shared count for the shared part. */
+
+static void
+split_extent (uint64_t extent_physical_offset,
+ uint64_t extent_length)
+{
+ struct rb_node *parent = NULL;
+ struct rb_node *prev_parent = NULL;
+ struct extent_info *this;
+ uint64_t pb_start = extent_physical_offset;
+ uint64_t ext_len = extent_length;
+ uint64_t new_pb_start;
+ uint64_t new_ext_len;
+ uint64_t old_ext_len;
+ size_t ext_shared_count = 0;
+
+ parent = lookup_leftmost_extent_info (pb_start);
+
+ while (ext_len)
+ {
+ if (!parent)
+ {
+ insert_new_extent_info (prev_parent, pb_start, ext_len,
Quoted 8 lines

lib/rbtree.h

Quoted 6 lines

ext_shared_count);
+ break;
+ }

lib/rbtree.h +3 -0
+
+ this = rb_entry (parent, struct extent_info, ei_node);
+

Could you please add more comments on the later codes? It is a little complicated for analysis.

That's really needed.

Quoted 7 lines
Quoted 5 lines

+ if (pb_start < this->ei_physical)
+ {
+ new_ext_len = min (this->ei_physical - pb_start, ext_len);
+ insert_new_extent_info (parent, pb_start, new_ext_len, ext_shared_count);

here is a bug, you need to set ext_shared_count to 0 since the later code will change it.

Thanks for the point out.

Quoted 19 lines
Quoted 19 lines
lib/rbtree.h +19 -0
+
+ pb_start += new_ext_len;
+ ext_len -= new_ext_len;
+ continue;
+ }
+
+ if (pb_start == this->ei_physical)
+ {
+ ext_shared_count = this->ei_shared_count;
+ old_ext_len = this->ei_length;
+ new_ext_len = min (ext_len, this->ei_length);
+
+ this->ei_length = new_ext_len;
+ this->ei_shared_count++;
+
+ pb_start += new_ext_len;
+ ext_len -= new_ext_len;
+
+ if (old_ext_len > new_ext_len)
Quoted 8 lines
Quoted 5 lines

+ {
+ new_pb_start = this->ei_physical + this->ei_length;
+ new_ext_len = old_ext_len - new_ext_len;
+ insert_new_extent_info (parent, new_pb_start, new_ext_len, ext_shared_count);

here you have add a new extent info but forget to increase pb_start and decrease ext_len. Also we need to reset ext_shared_count to 0 before insert.

Good catch.

Quoted 12 lines
Quoted 12 lines

+ }

lib/rbtree.h +11 -0
+
+ prev_parent = parent;
+ parent = rb_next (parent);
+ continue;
+ }
+
+ if (pb_start < this->ei_physical + this->ei_length)
+ {
+ old_ext_len = this->ei_physical + this->ei_length - pb_start;
+ new_ext_len = min (ext_len, old_ext_len);
+
Quoted 8 lines
Quoted 7 lines

+ ext_shared_count = this->ei_shared_count;
+ if (new_ext_len < old_ext_len)
+ insert_new_extent_info (parent, pb_start, new_ext_len, ext_shared_count);
+ else
+ insert_new_extent_info (parent, pb_start, old_ext_len, ext_shared_count);

We need to ext_shared_count++ for the insert_new_extent_info?

Yes, its need, the new insert extent is overlapped with it was before.

Quoted 4 lines

btw, only one line is enough:
insert_new_extent_info(parent, pb_start, new_ext_len, ext_shared_count); new_ext_len is <= old_ext_len because of the above min, so we are safe for the above 2 cases.

Hmm, that's true, why I do such stupid thing at that time. :-P

Quoted 5 lines
Quoted 5 lines
lib/rbtree.h +5 -0
+
+ this->ei_length = pb_start - this->ei_physical;
+
+ pb_start += new_ext_len;
+ ext_len -= new_ext_len;
Quoted 9 lines

lib/rbtree.h

Quoted 8 lines

+ parent = rb_next (parent);
+ continue;
+ }

lib/rbtree.h +5 -0
+
+ prev_parent = parent;
+ parent = rb_next (parent);
+ }
+}

BTW, Maybe I will have to delay the new patch submits time due to my current works and the spring Festival annual leave.

Quoted 2 lines

Regards,
Tao

Thanks,
-Jeff

#6 lore raw

PATCH 1/4 du_enhancement: add the shared extents and the footprint statistics support v1

In reply to Jeff Liu

On 2010?01?26? 16:00, Jeff Liu Wrote:

Quoted 14 lines

brief introduction:

the following patch sets add a new feature to displapy the shared extents size per file as well as the overall footprint statistics for du command.

It using rbtree to track the splitted extents info instead of the clusters or physical blocks to save the memory in case of the file size is too large(TB, etc).

the current extent splitting algorithem is based on Tao's idea, thanks a lot!

use '--shared-size' or '-E' as the command line trigger, with this option, du print out the shared extents in parens for each file if its resides filesystem support fiemap and the file is reflinked.

Quoted 5 lines

use '--fxattr' or '--fsync' or both of them to work combine with '--shared-size' for the extra fiemap control, it will print warning message on the console in case of the filesystem do not support the corresponding fiemap flags.

Signed-off-by Jeff Liu <[email protected]>

---

Hi Jeff,

If I understand correctly, this patch series is for coreutils, neither ocfs2 nor ocfs2-tools. How about Cc bug-coreutils at gnu.org as while ?

Signature · 2 lines
Coly Li
SuSE Labs
#7 lore raw

PATCH 1/4 du_enhancement: add the shared extents and the footprint statistics support v1

Quoted 6 lines · Coly Li

Jeff,

If I understand correctly, this patch series is for coreutils, neither ocfs2 nor ocfs2-tools. How about Cc bug-coreutils at gnu.org as while ?

All in good time. I've asked Jeff to email only ocfs2-devel. We want to work out the kinks before we cc coreutils.

#8 lore raw

PATCH 1/4 du_enhancement: add the shared extents and the footprint statistics support v1

On 2010?01?27? 03:52, Sunil Mushran Wrote:

Quoted 10 lines
Quoted 7 lines · Coly Li

Jeff,

If I understand correctly, this patch series is for coreutils, neither ocfs2 nor ocfs2-tools.
How about Cc bug-coreutils at gnu.org as while ?

All in good time. I've asked Jeff to email only ocfs2-devel. We want to work out the kinks before we cc coreutils.

Oh, I see. Thanks to make it clear :-)

Signature · 2 lines
Coly Li
SuSE Labs