Skip to contentSkip to conversation

du-enhancement: add rbtree v2

PATCH New Jie Liu 2 participants 8 messages Feb 26, 2010 – Sep 20, 2010 OCFS2

lore
Share & tools
lore

Jie Liu

author
#0 lore raw

PATCH 1/3 du-enhancement: add rbtree v2

rbtree copy from ocfs2-tools.
add rbtree source code to lib/Makefile.am.
This change also affect the corresponding Makefile.in in subdirs as well as the coreutils-6.9/configure script.

---
 coreutils-6.9/Makefile.in     |    3 +-
 coreutils-6.9/configure       |    2 +-
 coreutils-6.9/doc/Makefile.in |    3 +-
 coreutils-6.9/lib/Makefile.am |    3 +-
 coreutils-6.9/lib/Makefile.in |    5 +-
 coreutils-6.9/lib/rbtree.c    |  395 +++++++++++++++++++++++++++++++++++++++++
 coreutils-6.9/lib/rbtree.h    |  143 +++++++++++++++
 coreutils-6.9/po/Makefile.in  |    6 +-
 coreutils-6.9/src/Makefile.in |    2 +-
 9 files changed, 552 insertions(+), 10 deletions(-)
 create mode 100644 coreutils-6.9/lib/rbtree.c
 create mode 100644 coreutils-6.9/lib/rbtree.h
coreutils-6.9/Makefile.in +2 -1
index a2cd3ba..af95e47 100644
@@ -57,7 +57,8 @@ DIST_COMMON = README $(am__configure_deps) $(srcdir)/Makefile.am \
 	build-aux/ChangeLog build-aux/compile build-aux/config.guess \
 	build-aux/config.rpath build-aux/config.sub build-aux/depcomp \
 	build-aux/install-sh build-aux/mdate-sh build-aux/missing \
-	build-aux/texinfo.tex build-aux/ylwrap
+	build-aux/texinfo.tex build-aux/ylwrap depcomp install-sh \
+	ylwrap
 ACLOCAL_M4 = $(top_srcdir)/aclocal.m4
 am__aclocal_m4_deps = $(top_srcdir)/m4/absolute-header.m4 \
 	$(top_srcdir)/m4/acl.m4 $(top_srcdir)/m4/alloca.m4 \
coreutils-6.9/configure +1 -1
index 8c903bd..67e2503 100755
@@ -605,7 +605,7 @@ PACKAGE_NAME='GNU coreutils'
 PACKAGE_TARNAME='coreutils'
 PACKAGE_VERSION='6.9'
 PACKAGE_STRING='GNU coreutils 6.9'
-PACKAGE_BUGREPORT='http://oss.oracle.com/bugzilla'
+PACKAGE_BUGREPORT='bug-coreutils at gnu.org'
 
 ac_unique_file="src/ls.c"
 # Factoring default headers for most tests.
coreutils-6.9/doc/Makefile.in +2 -1
index ca84e92..e5683c1 100644
@@ -53,7 +53,8 @@ build_triplet = @build@
 host_triplet = @host@
 subdir = doc
 DIST_COMMON = $(srcdir)/Makefile.am $(srcdir)/Makefile.in \
-	$(srcdir)/stamp-vti $(srcdir)/version.texi ChangeLog
+	$(srcdir)/stamp-vti $(srcdir)/version.texi ChangeLog mdate-sh \
+	texinfo.tex
 ACLOCAL_M4 = $(top_srcdir)/aclocal.m4
 am__aclocal_m4_deps = $(top_srcdir)/m4/absolute-header.m4 \
 	$(top_srcdir)/m4/acl.m4 $(top_srcdir)/m4/alloca.m4 \
coreutils-6.9/lib/Makefile.am +2 -1
index cfa22be..6e22f65 100644
@@ -26,7 +26,8 @@ LDADD = $(noinst_LIBRARIES)
 
 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)
coreutils-6.9/lib/Makefile.in +3 -2
index 772d8f3..8c08170 100644
@@ -213,7 +213,7 @@ am_libcoreutils_a_OBJECTS = allocsa.$(OBJEXT) base64.$(OBJEXT) \
 	xalloc-die.$(OBJEXT) xgethostname.$(OBJEXT) xmemcoll.$(OBJEXT) \
 	xreadlink.$(OBJEXT) xreadlink-with-size.$(OBJEXT) \
 	xstrndup.$(OBJEXT) xstrtoimax.$(OBJEXT) xstrtoumax.$(OBJEXT) \
-	buffer-lcm.$(OBJEXT) xmemxfrm.$(OBJEXT)
+	buffer-lcm.$(OBJEXT) xmemxfrm.$(OBJEXT) rbtree.$(OBJEXT)
 libcoreutils_a_OBJECTS = $(am_libcoreutils_a_OBJECTS)
 LTLIBRARIES = $(noinst_LTLIBRARIES)
 PROGRAMS = $(noinst_PROGRAMS)
@@ -643,7 +643,7 @@ libcoreutils_a_SOURCES = allocsa.h allocsa.c base64.h base64.c \
 	xgethostname.h xgethostname.c xmemcoll.h xmemcoll.c \
 	xreadlink.c xreadlink-with-size.c xstrndup.h xstrndup.c \
 	xstrtoimax.c xstrtoumax.c buffer-lcm.c buffer-lcm.h xmemxfrm.c \
-	xmemxfrm.h
+	xmemxfrm.h rbtree.c rbtree.h
 libcoreutils_a_LIBADD = $(gl_LIBOBJS) @ALLOCA@ $(LIBOBJS)
 libcoreutils_a_DEPENDENCIES = $(gl_LIBOBJS) @ALLOCA@ $(LIBOBJS)
 EXTRA_libcoreutils_a_SOURCES = acl.c acl_entries.c file-has-acl.c \
@@ -915,6 +915,7 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote at ./$(DEPDIR)/quote.Po at am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote at ./$(DEPDIR)/quotearg.Po at am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote at ./$(DEPDIR)/raise.Po at am__quote@
+ at AMDEP_TRUE@@am__include@ @am__quote at ./$(DEPDIR)/rbtree.Po at am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote at ./$(DEPDIR)/readlink.Po at am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote at ./$(DEPDIR)/readtokens.Po at am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote at ./$(DEPDIR)/readtokens0.Po at am__quote@
coreutils-6.9/lib/rbtree.c new file +395 -0

395 lines not on this page · raw message

coreutils-6.9/lib/rbtree.h new file +143 -0

143 lines not on this page · raw message

coreutils-6.9/po/Makefile.in +3 -3
index cc6e178..3373a4e 100644
@@ -14,7 +14,7 @@
 
 PACKAGE = coreutils
 VERSION = 6.9
-PACKAGE_BUGREPORT = http://oss.oracle.com/bugzilla
+PACKAGE_BUGREPORT = bug-coreutils at gnu.org
 
 SHELL = /bin/sh
 
@@ -30,10 +30,10 @@ datadir = ${datarootdir}
 localedir = ${datarootdir}/locale
 gettextsrcdir = $(datadir)/gettext/po
 
-INSTALL = /usr/bin/install -c
+INSTALL = /usr/local/bin/install -c
 INSTALL_DATA = ${INSTALL} -m 644
 mkinstalldirs = $(SHELL) $(SHELL) /var/autofs/ca-fileserver2/build/smushran/git/shared-du/coreutils-6.9/build-aux/install-sh -d
-mkdir_p = /bin/mkdir -p
+mkdir_p = /usr/local/bin/mkdir -p
 
 GMSGFMT_ = /usr/bin/msgfmt
 GMSGFMT_no = /usr/bin/msgfmt
coreutils-6.9/src/Makefile.in +1 -1
index 18965a9..bbbc18c 100644
@@ -1200,7 +1200,7 @@ uninstall-binPROGRAMS:
 	done
 
 clean-binPROGRAMS:
-	-test -z "$(bin_PROGRAMS)" || rm -f $(bin_PROGRAMS) > /dev/null 2>&1 || /bin/rm -f $(bin_PROGRAMS)
+	-test -z "$(bin_PROGRAMS)" || rm -f $(bin_PROGRAMS)
 
 clean-noinstPROGRAMS:
 	-test -z "$(noinst_PROGRAMS)" || rm -f $(noinst_PROGRAMS)
Signature · 1 line
1.5.4.3
author
#1 lore raw

PATCH 2/3 du-enhancement: add fiemap header file v2

add fiemap.h to src/ which will be used by du.c

---
 coreutils-6.9/src/fiemap.h |   68 ++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 68 insertions(+), 0 deletions(-)
 create mode 100644 coreutils-6.9/src/fiemap.h
coreutils-6.9/src/fiemap.h new file +68 -0
new file mode 100644
index 0000000..54222ba
@@ -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
#2 lore raw

PATCH 3/3 du-enhancement: show the shared extents per file and the footprint v2

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.

---
 coreutils-6.9/src/du.c |  444 +++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 437 insertions(+), 7 deletions(-)
coreutils-6.9/src/du.c +437 -7
index 206d318..3adc3a8 100644
@@ -28,6 +28,11 @@
 #include <stdio.h>
 #include <getopt.h>
 #include <sys/types.h>
+
+#if HAVE_SYS_IOCTL_H
+# include <sys/ioctl.h>
+#endif
+
 #include <assert.h>
 #include "system.h"
 #include "argmatch.h"
@@ -44,6 +49,8 @@
 #include "stat-time.h"
 #include "xfts.h"
 #include "xstrtol.h"
+#include "rbtree.h"
+#include "fiemap.h"
 
 extern bool fts_debug;
 
@@ -64,6 +71,10 @@ extern bool fts_debug;
 /* Initial size of the hash table.  */
 #define INITIAL_TABLE_SIZE 103
 
+#if defined(_IOWR) && !defined(FS_IOC_FIEMAP)
+# define FS_IOC_FIEMAP _IOWR('f', 11, struct fiemap)
+#endif
+
 /* Hash structure for inode and device numbers.  The separate entry
    structure makes it easier to rehash "in place".  */
 
@@ -174,6 +185,34 @@ static char const *time_style = NULL;
 /* Format used to display date / time. Controlled by --time-style */
 static char const *time_format = NULL;
 
+/* If true, display the size of the shared extents per file and show
+ * the footprint in the end.  */
+static bool print_shared_size = false;
+
+/* FIEMAP_FLAG_* flags for request.  */
+static uint32_t fiemap_bits_flags;
+
+/* Show the size of the shared extents per file.  */
+static uint64_t file_shared_extents;
+
+/* Initialize the root of extents tree.  */
+static struct rb_root fe_root;
+
+/* A structure for per extent info.  */
+struct extent_info {
+  /* rbtree node */
+  struct rb_node ei_node;
+
+  /* physical offset in bytes */
+  uint64_t ei_physical;
+
+  /* length in bytes for this extent */
+  uint64_t ei_length;
+
+  /* extent shared count */
+  size_t ei_shared_count;
+};
+
 /* The units to use when printing sizes.  */
 static uintmax_t output_block_size;
 
@@ -205,7 +244,9 @@ enum
   MEGABYTES_LONG_OPTION,
 
   TIME_OPTION,
-  TIME_STYLE_OPTION
+  TIME_STYLE_OPTION,
+  FIEMAP_FLAG_SYNC_OPTION,
+  FIEMAP_FLAG_XATTR_OPTION
 };
 
 static struct option const long_options[] =
@@ -215,6 +256,9 @@ static struct option const long_options[] =
   {"block-size", required_argument, NULL, 'B'},
   {"bytes", no_argument, NULL, 'b'},
   {"count-links", no_argument, NULL, 'l'},
+  {"shared-size", no_argument, NULL, 'E'},
+  {"fsync", no_argument, NULL, FIEMAP_FLAG_SYNC_OPTION},
+  {"fxattr", no_argument, NULL, FIEMAP_FLAG_XATTR_OPTION},
   {"dereference", no_argument, NULL, 'L'},
   {"dereference-args", no_argument, NULL, 'D'},
   {"exclude", required_argument, NULL, EXCLUDE_OPTION},
@@ -314,6 +358,11 @@ Mandatory arguments to long options are mandatory for short options too.\n\
   -m                    like --block-size=1M\n\
 "), stdout);
       fputs (_("\
+  -E, --shared-size     show the size of the shared extents per file\n\
+      --fsync           sync file data before map\n\
+      --fxattr          map extended attribute tree\n\
+"), stdout);
+      fputs (_("\
   -L, --dereference     dereference all symbolic links\n\
   -P, --no-dereference  don't follow any symbolic links (this is the default)\n\
   -0, --null            end each output line with 0 byte rather than newline\n\
@@ -443,6 +492,22 @@ print_only_size (uintmax_t n_bytes)
 			 1, output_block_size), stdout);
 }
 
+/* Print footprint follow by STRING. */
+
+static void
+print_footprint (const struct duinfo *pdui, uintmax_t footprint, const char *string)
+{
+  print_only_size (footprint);
+  if (opt_time)
+    {
+      putchar ('\t');
+      show_date (time_format, pdui->tmax);
+    }
+
+  printf ("\t%s%c", string, opt_nul_terminate_output ? '\0' : '\n');
+  fflush (stdout);
+}
+
 /* Print size (and optionally time) indicated by *PDUI, followed by STRING.  */
 
 static void
@@ -454,10 +519,329 @@ print_size (const struct duinfo *pdui, const char *string)
       putchar ('\t');
       show_date (time_format, pdui->tmax);
     }
+  if ((print_shared_size) && (file_shared_extents > 0))
+    {
+      putchar ('\t');
+      putchar ('(');
+
+      if ((output_block_size == 1) && (file_shared_extents > pdui->size))
+        file_shared_extents = pdui->size;
+
+      print_only_size (file_shared_extents);
+      putchar (')');
+
+      file_shared_extents = 0;
+    }
   printf ("\t%s%c", string, opt_nul_terminate_output ? '\0' : '\n');
   fflush (stdout);
 }
 
+/* Free all allocated extents info from the rbtree.  */
+
+static void
+free_extent_info (void)
+{
+  struct rb_node *node;
+  struct extent_info *ei;
+
+  while ((node = rb_first (&fe_root)))
+    {
+      ei = rb_entry (node, struct extent_info, ei_node);
+      rb_erase (&ei->ei_node, &fe_root);
+      free (ei);
+    }
+}
+
+/* Walkup the extents rbtree to figure out the total size
+   of shared extents which has ei_shared_count > 0.  */
+
+static uintmax_t
+figure_share_extent_size (void)
+{
+  struct rb_node *node;
+  struct extent_info *ei;
+  static uintmax_t total_shared_extents = 0;
+
+  for (node = rb_first (&fe_root); node; node = rb_next (node))
+  {
+    ei = rb_entry (node, struct extent_info, ei_node);
+    if (ei->ei_shared_count > 0)
+        total_shared_extents += ei->ei_length * ei->ei_shared_count;
+  }
+
+  return total_shared_extents;
+}
+
+/* Insert new extent based on the new parent.  */
+
+static void
+insert_new_extent_info (struct rb_node *parent,
+                        uint64_t fe_physical,
+                        uint64_t fe_length,
+                        size_t extent_shared_count)
+{
+  struct rb_node **p = parent ? &parent : &((&fe_root)->rb_node);
+  struct rb_node *pp = NULL;
+  struct extent_info *this = NULL;
+  struct extent_info *ei;
+
+  while (*p)
+    {
+      pp = *p;
+      this = rb_entry (*p, struct extent_info, ei_node);
+
+      if (this->ei_physical > fe_physical)
+        p = &(*p)->rb_left;
+      else if (this->ei_physical < fe_physical)
+	p = &(*p)->rb_right;
+      else
+	return;
+    }
+
+  ei = xcalloc (1, sizeof *ei);
+  ei->ei_physical = fe_physical;
+  ei->ei_length = fe_length;
+  ei->ei_shared_count += extent_shared_count;
+
+  rb_link_node (&ei->ei_node, pp, p);
+  rb_insert_color (&ei->ei_node, &fe_root);
+}
+
+/* Find the left-most position to insert.  */
+
+static struct rb_node *
+lookup_leftmost_extent_info (uint64_t fe_physical)
+{
+  struct rb_node **p = &((&fe_root)->rb_node);
+  struct rb_node *parent;
+  struct extent_info *this;
+
+  while (*p)
+    {
+      parent = *p;
+      this = rb_entry (*p, struct extent_info, ei_node);
+
+      if (this->ei_physical > fe_physical)
+       p = &(*p)->rb_left;
+      else if (this->ei_physical < fe_physical)
+	p = &(*p)->rb_right;
+      else
+	break;
+    }
+
+  return parent;
+}
+
+/* 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);
+
+  /* We make use of the extent physical offset as the comparative value by combine
+     with the extent length to decide how to split it into sub extents.
+     For each new extent, in short, there are 3 scenarios need to process against
+     the search returned:
+     . physical offset smaller than the searched.
+     . physical offset equal to the searched.
+     . physical offset greater than the searched.  */
+  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);
+
+      /* The new extent physical offset is smaller than the search returned.
+         there are 3 scenarios need to check against the old one which shown
+	 as the following sketch.
+                   |---------| old
+         |------| new1
+         |---------------| new2
+         |------------------------| new3.  */
+
+      if (pb_start < this->ei_physical)
+	{
+	  new_ext_len = MIN (this->ei_physical - pb_start, ext_len);
+
+	  ext_shared_count = 0;
+          insert_new_extent_info (parent, pb_start, new_ext_len, ext_shared_count);
+
+          pb_start += new_ext_len;
+	  ext_len -= new_ext_len;
+          continue;
+        }
+
+      /* The new extent physical offset if equal to the search returned.
+         there are 3 scenarios need to check against the old one which shown
+	 as the following sketch.
+         |----------| old
+         |----------------| new1
+         |----------| new2
+         |-------| new3.  */
+      if (pb_start == this->ei_physical)
+        {
+          old_ext_len = this->ei_length;
+          new_ext_len = MIN (ext_len, this->ei_length);
+
+          /* Decrease the existed extent size to the minor, its shared count
+	     need to increase due to the overlap of them.  */
+          this->ei_length = new_ext_len;
+          this->ei_shared_count++;
+
+          pb_start += new_ext_len;
+          ext_len -= new_ext_len;
+
+          /* The search returned extent range includes the new, figure out the
+	   * not included range and insert it on the rbtree.  */
+          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;
+	      ext_shared_count = 0;
+	      insert_new_extent_info (parent, new_pb_start, new_ext_len, ext_shared_count);
+	    }
+
+          prev_parent = parent;
+          parent = rb_next (parent);
+          continue;
+        }
+
+      /* The new extent physical offset if greater than the search returned.
+         there are 3 scenarios need to check against the old one which shown
+	 as the following sketch.
+         |-----------| old
+           |----| new1
+           |-----------| new2
+           |---------------| new3.  */
+      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;
+
+          /* The new extent overlapped with the old one, as a result, we
+	     need to increase its shared count before inserting.  */
+          ext_shared_count++;
+	  insert_new_extent_info (parent, pb_start, new_ext_len, ext_shared_count);
+
+          /* Decrease the search returned extent size and keep it on the tree.  */
+          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);
+    }
+}
+
+/* This function is called once for every file system object that fts
+   encounters, get its extent mapping info for the proceeding extent
+   spliting operation.  */
+
+static void
+process_extent(int cwd_fd, char const *file,
+               char const *file_full_name)
+{
+  char buf[4096] = "";
+  struct fiemap *fiemap = (struct fiemap *)buf;
+  struct fiemap_extent *fm_ext = &fiemap->fm_extents[0];
+  uint32_t count = (sizeof (buf) - sizeof (*fiemap)) /
+               sizeof (struct fiemap_extent);
+  int last = 0;
+
+  int fd = openat (cwd_fd, file, O_RDONLY);
+  if (fd < 0)
+    {
+      fd = open (file_full_name, O_RDONLY);
+      if (fd < 0)
+        {
+          error(0, errno, _("cannot open %s"), quote (file_full_name));
+          return;
+	}
+    }
+
+  memset (fiemap, 0, sizeof (*fiemap));
+
+  do {
+    fiemap->fm_length = ~0ULL;
+    fiemap->fm_flags = fiemap_bits_flags;
+    fiemap->fm_extent_count = count;
+
+    if (ioctl (fd, FS_IOC_FIEMAP, (unsigned long) fiemap) < 0)
+      {
+        if (errno == EBADR)
+            error (0, errno, _("%s FIEMAP failed with unsupported flags %x\n"),
+                                quote (file_full_name), fiemap->fm_flags);
+
+        error(0, errno, _("%s extent mapping failed"), quote (file_full_name));
+        goto close_file;
+      }
+
+    /* If 0 extents are returned, then more ioctls
+       are not needed.  */
+    if (fiemap->fm_mapped_extents == 0)
+      goto close_file;
+
+    uint64_t ext_phy_offset;
+    uint64_t ext_len;
+    size_t i;
+    for (i = 0; i < fiemap->fm_mapped_extents; i++)
+      {
+        ext_phy_offset = fm_ext[i].fe_physical;
+	ext_len = fm_ext[i].fe_length;
+
+        /* Skip inline file which its data mixed with metadata.  */
+        if (fm_ext[i].fe_flags & FIEMAP_EXTENT_DATA_INLINE)
+	  {
+            if (fm_ext[i].fe_flags & FIEMAP_EXTENT_LAST)
+              {
+                last = 1;
+                break;
+	      }
+	    continue;
+	  }
+
+        /* Increase the shared extents size per file.  */
+        if (fm_ext[i].fe_flags & FIEMAP_EXTENT_SHARED)
+          file_shared_extents += fm_ext[i].fe_length;
+
+        split_extent (ext_phy_offset, ext_len);
+
+        if (fm_ext[i].fe_flags & FIEMAP_EXTENT_LAST)
+          last = 1;
+
+        fiemap->fm_start = (fm_ext[i-1].fe_logical + fm_ext[i-1].fe_length);
+      }
+    } while (last == 0);
+
+close_file:
+  if (close (fd) < 0)
+      error (0, errno, _("closing %s"), quote (file_full_name));
+}
+
 /* This function is called once for every file system object that fts
    encounters.  fts does a depth-first traversal.  This function knows
    that and accumulates per-directory totals based on changes in
@@ -483,7 +867,8 @@ process_file (FTS *fts, FTSENT *ent)
   static struct dulevel *dulvl;
   bool print = true;
 
-  const char *file = ent->fts_path;
+  const char *file_full_name = ent->fts_path;
+  const char *file = ent->fts_accpath;
   const struct stat *sb = ent->fts_statp;
   bool skip;
 
@@ -495,18 +880,18 @@ process_file (FTS *fts, FTSENT *ent)
   switch (ent->fts_info)
     {
     case FTS_NS:
-      error (0, ent->fts_errno, _("cannot access %s"), quote (file));
+      error (0, ent->fts_errno, _("cannot access %s"), quote (file_full_name));
       return false;
 
     case FTS_ERR:
       /* if (S_ISDIR (ent->fts_statp->st_mode) && FIXME */
-      error (0, ent->fts_errno, _("%s"), quote (file));
+      error (0, ent->fts_errno, _("%s"), quote (file_full_name));
       return false;
 
     case FTS_DNR:
       /* Don't return just yet, since although the directory is not readable,
 	 we were able to stat it, so we do have a size.  */
-      error (0, ent->fts_errno, _("cannot read directory %s"), quote (file));
+      error (0, ent->fts_errno, _("cannot read directory %s"), quote (file_full_name));
       ok = false;
       break;
 
@@ -619,9 +1004,12 @@ process_file (FTS *fts, FTSENT *ent)
   if (!print)
     return ok;
 
+  if (print_shared_size)
+    process_extent (fts->fts_cwd_fd, file, file_full_name);
+
   if ((IS_DIR_TYPE (ent->fts_info) && level <= max_depth)
       || ((opt_all && level <= max_depth) || level == 0))
-    print_size (&dui_to_print, file);
+    print_size (&dui_to_print, file_full_name);
 
   return ok;
 }
@@ -709,7 +1097,7 @@ main (int argc, char **argv)
   human_output_opts = human_options (getenv ("DU_BLOCK_SIZE"), false,
 				     &output_block_size);
 
-  while ((c = getopt_long (argc, argv, DEBUG_OPT "0abchHklmsxB:DLPSX:",
+  while ((c = getopt_long (argc, argv, DEBUG_OPT "0abchHklmsxB:DELPSX:",
 			   long_options, NULL)) != -1)
     {
       switch (c)
@@ -834,6 +1222,27 @@ main (int argc, char **argv)
 	    }
 	  break;
 
+	case 'E':
+#ifndef FS_IOC_FIEMAP
+          error (EXIT_FAILURE, 0, _("Shared-du are not supported by this version"));
+#endif
+	  print_shared_size = true;
+	  break;
+
+	case FIEMAP_FLAG_SYNC_OPTION:
+#ifndef FS_IOC_FIEMAP
+          error (EXIT_FAILURE, 0, _("Shared-du are not supported by this version"));
+#endif
+	  fiemap_bits_flags |= FIEMAP_FLAG_SYNC;
+          break;
+
+        case FIEMAP_FLAG_XATTR_OPTION:
+#ifndef FS_IOC_FIEMAP
+          error (EXIT_FAILURE, 0, _("Shared-du are not supported by this version"));
+#endif
+	  fiemap_bits_flags |= FIEMAP_FLAG_XATTR;
+	  break;
+
 	case FILES0_FROM_OPTION:
 	  files_from = optarg;
 	  break;
@@ -866,6 +1275,17 @@ main (int argc, char **argv)
   if (!ok)
     usage (EXIT_FAILURE);
 
+  if (((fiemap_bits_flags & FIEMAP_FLAG_SYNC) ||
+      (fiemap_bits_flags & FIEMAP_FLAG_XATTR)) &&
+      !print_shared_size)
+    {
+      error(0, 0, _("warning: fiemap flags must be combined with --shared-size"));
+      usage (EXIT_FAILURE);
+    }
+
+  if (print_shared_size)
+      fe_root = RB_ROOT;
+
   if (opt_all & opt_summarize_only)
     {
       error (0, 0, _("cannot both summarize and show all entries"));
@@ -1015,6 +1435,16 @@ main (int argc, char **argv)
   if (files_from)
     readtokens0_free (&tok);
 
+  if (print_shared_size)
+    {
+      uintmax_t tot_shared_extents = figure_share_extent_size ();
+      uintmax_t footprint = tot_dui.size - tot_shared_extents;
+
+      print_footprint(&tot_dui, footprint, _("footprint"));
+
+      free_extent_info ();
+    }
+
   hash_free (htab);
 
   exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);
Signature · 1 line
1.5.4.3
#3 lore raw

PATCH 3/3 du-enhancement: show the shared extents per file and the footprint v2

Quoted 30 lines · Jie 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.

---
 coreutils-6.9/src/du.c |  444 +++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 437 insertions(+), 7 deletions(-)
coreutils-6.9/src/du.c +14 -0
index 206d318..3adc3a8 100644
+/* Insert new extent based on the new parent.  */
+
+static void
+insert_new_extent_info (struct rb_node *parent,
+                        uint64_t fe_physical,
+                        uint64_t fe_length,
+                        size_t extent_shared_count)
+{
+  struct rb_node **p = parent ? &parent : &((&fe_root)->rb_node);
+  struct rb_node *pp = NULL;
+  struct extent_info *this = NULL;
+  struct extent_info *ei;
+
+  while (*p)

coreutils-6.9/src/du.c print_size (const struct duinfo *pdui, const char *string) · line 598

Quoted 10 lines
coreutils-6.9/src/du.c +10 -0
+    {
+      pp = *p;
+      this = rb_entry (*p, struct extent_info, ei_node);
+
+      if (this->ei_physical > fe_physical)
+        p = &(*p)->rb_left;
+      else if (this->ei_physical < fe_physical)
+	p = &(*p)->rb_right;
+      else
+	return;

I am just curious in your code the last "else" should never happen? If yes, maybe if we meet with this, it means a bug in the code. So better assert here?

Quoted 16 lines
coreutils-6.9/src/du.c +15 -0
+    }
+
+/* Find the left-most position to insert.  */
+
+static struct rb_node *
+lookup_leftmost_extent_info (uint64_t fe_physical)
+{
+  struct rb_node **p = &((&fe_root)->rb_node);
+  struct rb_node *parent;
+  struct extent_info *this;
+
+  while (*p)
+    {
+      parent = *p;
+      this = rb_entry (*p, struct extent_info, ei_node);

coreutils-6.9/src/du.c print_size (const struct duinfo *pdui, const char *string) · line 632

Quoted 10 lines
coreutils-6.9/src/du.c +10 -0
+
+      if (this->ei_physical > fe_physical)
+       p = &(*p)->rb_left;
+      else if (this->ei_physical < fe_physical)
+	p = &(*p)->rb_right;
+      else
+	break;
+    }
+
+  return parent;

If the rb-tree is empty, the parent is uninitialized. So please set parent to NULL in the declaration.

Quoted 38 lines
coreutils-6.9/src/du.c +36 -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);
+
 
+      /* The new extent physical offset if greater than the search returned.
+         there are 3 scenarios need to check against the old one which shown
+	 as the following sketch.
+         |-----------| old
+           |----| new1
+           |-----------| new2
+           |---------------| new3.  */
+      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;
+

coreutils-6.9/src/du.c print_size (const struct duinfo *pdui, const char *string) · line 750

Quoted 10 lines
coreutils-6.9/src/du.c +10 -0
+          /* The new extent overlapped with the old one, as a result, we
+	     need to increase its shared count before inserting.  */
+          ext_shared_count++;
+	  insert_new_extent_info (parent, pb_start, new_ext_len, ext_shared_count);
+
+          /* Decrease the search returned extent size and keep it on the tree.  */
+          this->ei_length = pb_start - this->ei_physical;
+
+	  pb_start += new_ext_len;
+	  ext_len -= new_ext_len;

We also need prev_parent = parent here?

coreutils-6.9/src/du.c print_size (const struct duinfo *pdui, const char *string) · line 756

Quoted 7 lines
coreutils-6.9/src/du.c +6 -0
+          parent = rb_next (parent);
+          continue;
+        }
+
+      prev_parent = parent;
+      parent = rb_next (parent);

btw, in the above 3 cases, you always call "continue", so we have no chance to arrive here actually.

Quoted 45 lines
coreutils-6.9/src/du.c +44 -0
+    }
+}
+
+/* This function is called once for every file system object that fts
+   encounters, get its extent mapping info for the proceeding extent
+   spliting operation.  */
+
+static void
+process_extent(int cwd_fd, char const *file,
+               char const *file_full_name)
+{
+  char buf[4096] = "";
+  struct fiemap *fiemap = (struct fiemap *)buf;
+  struct fiemap_extent *fm_ext = &fiemap->fm_extents[0];
+  uint32_t count = (sizeof (buf) - sizeof (*fiemap)) /
+               sizeof (struct fiemap_extent);
+  int last = 0;
+
+  int fd = openat (cwd_fd, file, O_RDONLY);
+  if (fd < 0)
+    {
+      fd = open (file_full_name, O_RDONLY);
+      if (fd < 0)
+        {
+          error(0, errno, _("cannot open %s"), quote (file_full_name));
+          return;
+	}
+    }
+
+  memset (fiemap, 0, sizeof (*fiemap));
+
+  do {
+    fiemap->fm_length = ~0ULL;
+    fiemap->fm_flags = fiemap_bits_flags;
+    fiemap->fm_extent_count = count;
+
+    if (ioctl (fd, FS_IOC_FIEMAP, (unsigned long) fiemap) < 0)
+      {
+        if (errno == EBADR)
+            error (0, errno, _("%s FIEMAP failed with unsupported flags %x\n"),
+                                quote (file_full_name), fiemap->fm_flags);
+
+        error(0, errno, _("%s extent mapping failed"), quote (file_full_name));
+        goto close_file;

coreutils-6.9/src/du.c print_size (const struct duinfo *pdui, const char *string) · line 810

Quoted 10 lines
coreutils-6.9/src/du.c +10 -0
+      }
+
+    /* If 0 extents are returned, then more ioctls
+       are not needed.  */
+    if (fiemap->fm_mapped_extents == 0)
+      goto close_file;
+
+    uint64_t ext_phy_offset;
+    uint64_t ext_len;
+    size_t i;

better move these declaration above.

Quoted 17 lines
coreutils-6.9/src/du.c +16 -0
+    for (i = 0; i < fiemap->fm_mapped_extents; i++)
+      {
+        ext_phy_offset = fm_ext[i].fe_physical;
+	ext_len = fm_ext[i].fe_length;
+
+        /* Skip inline file which its data mixed with metadata.  */
+        if (fm_ext[i].fe_flags & FIEMAP_EXTENT_DATA_INLINE)
+	  {
+            if (fm_ext[i].fe_flags & FIEMAP_EXTENT_LAST)
+              {
+                last = 1;
+                break;
+	      }
+	    continue;
+	  }
+

coreutils-6.9/src/du.c print_size (const struct duinfo *pdui, const char *string) · line 836

Quoted 10 lines
coreutils-6.9/src/du.c +10 -0
+        /* Increase the shared extents size per file.  */
+        if (fm_ext[i].fe_flags & FIEMAP_EXTENT_SHARED)
+          file_shared_extents += fm_ext[i].fe_length;
+
+        split_extent (ext_phy_offset, ext_len);
+
+        if (fm_ext[i].fe_flags & FIEMAP_EXTENT_LAST)
+          last = 1;
+
+        fiemap->fm_start = (fm_ext[i-1].fe_logical + fm_ext[i-1].fe_length);

I am just curious you start from i=0, so how could fm_ext[-1] work? Or I miss something here?

coreutils-6.9/src/du.c print_size (const struct duinfo *pdui, const char *string) · line 839

Quoted 4 lines
coreutils-6.9/src/du.c +3 -0
+      }
+    } while (last == 0);
+

Regards,
Tao

author
#4 lore raw

PATCH 3/3 du-enhancement: show the shared extents per file and the footprint v2

Hi Tao,

Thanks for your comments.

Quoted 40 lines · Tao Ma
Quoted 39 lines · Jie 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.

---
 coreutils-6.9/src/du.c |  444
+++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 437 insertions(+), 7 deletions(-)
coreutils-6.9/src/du.c +20 -0
index 206d318..3adc3a8 100644
+/* Insert new extent based on the new parent.  */
+
+static void
+insert_new_extent_info (struct rb_node *parent,
+                        uint64_t fe_physical,
+                        uint64_t fe_length,
+                        size_t extent_shared_count)
+{
+  struct rb_node **p = parent ? &parent : &((&fe_root)->rb_node);
+  struct rb_node *pp = NULL;
+  struct extent_info *this = NULL;
+  struct extent_info *ei;
+
+  while (*p)
+    {
+      pp = *p;
+      this = rb_entry (*p, struct extent_info, ei_node);
+
+      if (this->ei_physical > fe_physical)
+        p = &(*p)->rb_left;
Quoted 8 lines

coreutils-6.9/src/du.c print_size (const struct duinfo *pdui, const char *string) · line 598

Quoted 5 lines
coreutils-6.9/src/du.c +4 -0
+      else if (this->ei_physical < fe_physical)
+    p = &(*p)->rb_right;
+      else
+    return;

I am just curious in your code the last "else" should never happen? If yes, maybe if we meet with this, it means a bug in the code. So better assert here?

IMHO, the last 'else' should not happen if the split algorithm works correctly. The current algorithm is designed to make sure there is no extent overlap occurrs in the rbtree. So I am prefer to abort the DU process by asserting there.

Quoted 20 lines
Quoted 20 lines
coreutils-6.9/src/du.c +20 -0
+    }
+
+/* Find the left-most position to insert.  */
+
+static struct rb_node *
+lookup_leftmost_extent_info (uint64_t fe_physical)
+{
+  struct rb_node **p = &((&fe_root)->rb_node);
+  struct rb_node *parent;
+  struct extent_info *this;
+
+  while (*p)
+    {
+      parent = *p;
+      this = rb_entry (*p, struct extent_info, ei_node);
+
+      if (this->ei_physical > fe_physical)
+       p = &(*p)->rb_left;
+      else if (this->ei_physical < fe_physical)
+    p = &(*p)->rb_right;
Quoted 8 lines

coreutils-6.9/src/du.c print_size (const struct duinfo *pdui, const char *string) · line 632

Quoted 6 lines
coreutils-6.9/src/du.c +5 -0
+      else
+    break;
+    }
+
+  return parent;

If the rb-tree is empty, the parent is uninitialized. So please set parent to NULL in the declaration.

Thanks, this will be fixed in the next patches submit.

Quoted 44 lines
Quoted 44 lines
coreutils-6.9/src/du.c +22 -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);
+
  +      /* The new extent physical offset if greater than the search

returned.
+ there are 3 scenarios need to check against the old one
which shown

coreutils-6.9/src/du.c +16 -0
+     as the following sketch.
+         |-----------| old
+           |----| new1
+           |-----------| new2
+           |---------------| new3.  */
+      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;
+
+          /* The new extent overlapped with the old one, as a result, we
+         need to increase its shared count before inserting.  */
+          ext_shared_count++;
+      insert_new_extent_info (parent, pb_start, new_ext_len,

ext_shared_count);
+

Quoted 8 lines

coreutils-6.9/src/du.c print_size (const struct duinfo *pdui, const char *string) · line 750

Quoted 7 lines

+ /* Decrease the search returned extent size and keep it on
the tree. */

coreutils-6.9/src/du.c +4 -0
+          this->ei_length = pb_start - this->ei_physical;
+
+      pb_start += new_ext_len;
+      ext_len -= new_ext_len;

We also need prev_parent = parent here?

Yes, it needed.
By combining with your following next comments.
I will modify the logical as well.

Quoted 60 lines

coreutils-6.9/src/du.c print_size (const struct duinfo *pdui, const char *string) · line 756

Quoted 7 lines
coreutils-6.9/src/du.c +6 -0
+          parent = rb_next (parent);
+          continue;
+        }
+
+      prev_parent = parent;
+      parent = rb_next (parent);

btw, in the above 3 cases, you always call "continue", so we have no chance to arrive here actually.

Quoted 51 lines
coreutils-6.9/src/du.c +40 -0
+    }
+}
+
+/* This function is called once for every file system object that fts
+   encounters, get its extent mapping info for the proceeding extent
+   spliting operation.  */
+
+static void
+process_extent(int cwd_fd, char const *file,
+               char const *file_full_name)
+{
+  char buf[4096] = "";
+  struct fiemap *fiemap = (struct fiemap *)buf;
+  struct fiemap_extent *fm_ext = &fiemap->fm_extents[0];
+  uint32_t count = (sizeof (buf) - sizeof (*fiemap)) /
+               sizeof (struct fiemap_extent);
+  int last = 0;
+
+  int fd = openat (cwd_fd, file, O_RDONLY);
+  if (fd < 0)
+    {
+      fd = open (file_full_name, O_RDONLY);
+      if (fd < 0)
+        {
+          error(0, errno, _("cannot open %s"), quote (file_full_name));
+          return;
+    }
+    }
+
+  memset (fiemap, 0, sizeof (*fiemap));
+
+  do {
+    fiemap->fm_length = ~0ULL;
+    fiemap->fm_flags = fiemap_bits_flags;
+    fiemap->fm_extent_count = count;
+
+    if (ioctl (fd, FS_IOC_FIEMAP, (unsigned long) fiemap) < 0)
+      {
+        if (errno == EBADR)
+            error (0, errno, _("%s FIEMAP failed with unsupported

flags %x\n"),
+ quote (file_full_name),
fiemap->fm_flags);

coreutils-6.9/src/du.c +2 -0
+
+        error(0, errno, _("%s extent mapping failed"), quote

(file_full_name));

coreutils-6.9/src/du.c +5 -0
+        goto close_file;
+      }
+
+    /* If 0 extents are returned, then more ioctls
+       are not needed.  */
Quoted 8 lines

coreutils-6.9/src/du.c print_size (const struct duinfo *pdui, const char *string) · line 810

Quoted 7 lines
coreutils-6.9/src/du.c +6 -0
+    if (fiemap->fm_mapped_extents == 0)
+      goto close_file;
+
+    uint64_t ext_phy_offset;
+    uint64_t ext_len;
+    size_t i;

better move these declaration above.

Do you means this is a bad coding style?

Due to these variables resides function exceeds 1 screen page, so I declares them here to facilitate the variables reference like type and name. or else, someone have to page up to refer to them.
I'd like to keep the ext_phy_offset and ext_len in the bottom FOR logical, but move 'i' to the head of this function since it is well-known as an iterate counter.

How do you think about that?
I just want to make the code looks more professional.

Quoted 2 lines

coreutils-6.9/src/du.c

Quoted 2 lines
coreutils-6.9/src/du.c +2 -0
+    for (i = 0; i < fiemap->fm_mapped_extents; i++)
+      {
            uint64_t ext_phy_offset;
            uint64_t ext_len;
Quoted 20 lines
Quoted 20 lines
coreutils-6.9/src/du.c +20 -0
+        ext_phy_offset = fm_ext[i].fe_physical;
+    ext_len = fm_ext[i].fe_length;
+
+        /* Skip inline file which its data mixed with metadata.  */
+        if (fm_ext[i].fe_flags & FIEMAP_EXTENT_DATA_INLINE)
+      {
+            if (fm_ext[i].fe_flags & FIEMAP_EXTENT_LAST)
+              {
+                last = 1;
+                break;
+          }
+        continue;
+      }
+
+        /* Increase the shared extents size per file.  */
+        if (fm_ext[i].fe_flags & FIEMAP_EXTENT_SHARED)
+          file_shared_extents += fm_ext[i].fe_length;
+
+        split_extent (ext_phy_offset, ext_len);
+
Quoted 8 lines
Quoted 6 lines
coreutils-6.9/src/du.c +4 -0
+        if (fm_ext[i].fe_flags & FIEMAP_EXTENT_LAST)
+          last = 1;
+
+        fiemap->fm_start = (fm_ext[i-1].fe_logical +

fm_ext[i-1].fe_length);

I am just curious you start from i=0, so how could fm_ext[-1] work? Or I miss something here?

No, you are right, that's my mistake, the new start offset should be calcuated outside the FOR loop.

Thanks,
-Jeff

Quoted 7 lines

coreutils-6.9/src/du.c print_size (const struct duinfo *pdui, const char *string) · line 839

Quoted 4 lines
coreutils-6.9/src/du.c +3 -0
+      }
+    } while (last == 0);
+

Regards,
Tao

#5 lore raw

PATCH 3/3 du-enhancement: show the shared extents per file and the footprint v2

Hi jeff,

Quoted 53 lines · jeff.liu

Hi Tao,

Thanks for your comments.

Quoted 40 lines · Tao Ma
Quoted 39 lines · Jie 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.

---
 coreutils-6.9/src/du.c |  444
+++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 437 insertions(+), 7 deletions(-)
coreutils-6.9/src/du.c +20 -0
index 206d318..3adc3a8 100644
+/* Insert new extent based on the new parent.  */
+
+static void
+insert_new_extent_info (struct rb_node *parent,
+                        uint64_t fe_physical,
+                        uint64_t fe_length,
+                        size_t extent_shared_count)
+{
+  struct rb_node **p = parent ? &parent : &((&fe_root)->rb_node);
+  struct rb_node *pp = NULL;
+  struct extent_info *this = NULL;
+  struct extent_info *ei;
+
+  while (*p)
+    {
+      pp = *p;
+      this = rb_entry (*p, struct extent_info, ei_node);
+
+      if (this->ei_physical > fe_physical)
+        p = &(*p)->rb_left;
Quoted 8 lines

coreutils-6.9/src/du.c print_size (const struct duinfo *pdui, const char *string) · line 598

Quoted 5 lines
coreutils-6.9/src/du.c +4 -0
+      else if (this->ei_physical < fe_physical)
+    p = &(*p)->rb_right;
+      else
+    return;

I am just curious in your code the last "else" should never happen? If yes, maybe if we meet with this, it means a bug in the code. So better assert here?

Quoted 3 lines

IMHO, the last 'else' should not happen if the split algorithm works correctly. The current algorithm is designed to make sure there is no extent overlap occurrs in the rbtree. So I am prefer to abort the DU process by asserting there.

as you said, it is *designed* to work well, but you can't say it works well. With a "assert", you know there is a problem. Without assert, you may cheated by the codes. ;) btw, you can have a look in ocfs2-tools. there are some codes like it with "assert".

Quoted 18 lines
Quoted 10 lines

coreutils-6.9/src/du.c print_size (const struct duinfo *pdui, const char *string) · line 810

Quoted 9 lines
coreutils-6.9/src/du.c +8 -0
+    /* If 0 extents are returned, then more ioctls
+       are not needed.  */
+    if (fiemap->fm_mapped_extents == 0)
+      goto close_file;
+
+    uint64_t ext_phy_offset;
+    uint64_t ext_len;
+    size_t i;

better move these declaration above.

Do you means this is a bad coding style?

Due to these variables resides function exceeds 1 screen page, so I declares them here to facilitate the variables reference like type and name. or else, someone have to page up to refer to them.
I'd like to keep the ext_phy_offset and ext_len in the bottom FOR logical, but move 'i' to the head of this function since it is well-known as an iterate counter.

Quoted 7 lines

How do you think about that?
I just want to make the code looks more professional.

Quoted 2 lines

coreutils-6.9/src/du.c

Quoted 2 lines
coreutils-6.9/src/du.c +2 -0
+    for (i = 0; i < fiemap->fm_mapped_extents; i++)
+      {
            uint64_t ext_phy_offset;
            uint64_t ext_len;

yeah, this looks better and you can combine the 4 lines into 2 actually. ;)

		uint64_t ext_phy_offset = fm_ext[i].fe_physical;
		uint64_t ext_len = fm_ext[i].fe_length;
Quoted 2 lines
Quoted 2 lines

coreutils-6.9/src/du.c print_size (const struct duinfo *pdui, const char *string) · line 814

Quoted 2 lines
coreutils-6.9/src/du.c +2 -0
+        ext_phy_offset = fm_ext[i].fe_physical;
+    ext_len = fm_ext[i].fe_length;

Regards,
Tao

author
#6 lore raw

PATCH 3/3 du-enhancement: show the shared extents per file and the footprint v2

Quoted 61 lines · Tao Ma

Hi jeff,

Quoted 53 lines · jeff.liu

Hi Tao,

Thanks for your comments.

Quoted 40 lines · Tao Ma
Quoted 39 lines · Jie 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.

---
 coreutils-6.9/src/du.c |  444
+++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 437 insertions(+), 7 deletions(-)
coreutils-6.9/src/du.c +20 -0
index 206d318..3adc3a8 100644
+/* Insert new extent based on the new parent.  */
+
+static void
+insert_new_extent_info (struct rb_node *parent,
+                        uint64_t fe_physical,
+                        uint64_t fe_length,
+                        size_t extent_shared_count)
+{
+  struct rb_node **p = parent ? &parent : &((&fe_root)->rb_node);
+  struct rb_node *pp = NULL;
+  struct extent_info *this = NULL;
+  struct extent_info *ei;
+
+  while (*p)
+    {
+      pp = *p;
+      this = rb_entry (*p, struct extent_info, ei_node);
+
+      if (this->ei_physical > fe_physical)
+        p = &(*p)->rb_left;
Quoted 8 lines

coreutils-6.9/src/du.c print_size (const struct duinfo *pdui, const char *string) · line 598

Quoted 5 lines
coreutils-6.9/src/du.c +4 -0
+      else if (this->ei_physical < fe_physical)
+    p = &(*p)->rb_right;
+      else
+    return;

I am just curious in your code the last "else" should never happen? If yes, maybe if we meet with this, it means a bug in the code. So better assert here?

Quoted 5 lines

IMHO, the last 'else' should not happen if the split algorithm works correctly.
The current algorithm is designed to make sure there is no extent overlap occurrs in the rbtree.
So I am prefer to abort the DU process by asserting there.

Quoted 4 lines

as you said, it is *designed* to work well, but you can't say it works well. With a "assert", you know there is a problem. Without assert, you may cheated by the codes. ;) btw, you can have a look in ocfs2-tools. there are some codes like it with "assert".

Sorry, it looks my last comments didn't mentioned clearly, I means I agree with your point, it should be asserted here.

Quoted 21 lines
Quoted 21 lines
Quoted 10 lines

coreutils-6.9/src/du.c print_size (const struct duinfo *pdui, const char *string) · line 810

Quoted 9 lines
coreutils-6.9/src/du.c +8 -0
+    /* If 0 extents are returned, then more ioctls
+       are not needed.  */
+    if (fiemap->fm_mapped_extents == 0)
+      goto close_file;
+
+    uint64_t ext_phy_offset;
+    uint64_t ext_len;
+    size_t i;

better move these declaration above.

Do you means this is a bad coding style?

Due to these variables resides function exceeds 1 screen page, so I declares them here to
facilitate the variables reference like type and name. or else, someone have to page up to refer to
them.
I'd like to keep the ext_phy_offset and ext_len in the bottom FOR logical, but move 'i' to the
head of this function since it is well-known as an iterate counter.

Quoted 8 lines
Quoted 7 lines

How do you think about that?
I just want to make the code looks more professional.

Quoted 2 lines

coreutils-6.9/src/du.c

Quoted 2 lines
coreutils-6.9/src/du.c +2 -0
+    for (i = 0; i < fiemap->fm_mapped_extents; i++)
+      {
            uint64_t ext_phy_offset;
            uint64_t ext_len;

yeah, this looks better and you can combine the 4 lines into 2 actually. ;)

sure. :)

Quoted 7 lines
        uint64_t ext_phy_offset = fm_ext[i].fe_physical;
        uint64_t ext_len = fm_ext[i].fe_length;
Quoted 2 lines
Quoted 2 lines

coreutils-6.9/src/du.c print_size (const struct duinfo *pdui, const char *string) · line 814

Quoted 2 lines
coreutils-6.9/src/du.c +2 -0
+        ext_phy_offset = fm_ext[i].fe_physical;
+    ext_len = fm_ext[i].fe_length;

Regards,
Tao

Thanks,
-Jeff

author
#7 lore raw

[Ocfs2-devel] Shared-du: show the shared extents per file and the footprint v4

In reply to Tao Ma

Hello,

The coming patches introduce fiemap support to du(1), the goal is to teach du(1) to figure up the shared extents per file it goes through, as well as the footprint of the storage in the end.

Changes to v3:
. fix the issues according to Tao's comments.
. Try to merge to the left or right node if possible when inserting a new extent_info to rbtree.

I have done some tests in the past few days, it works fine, thanks Tao for help creating the test envionment!

Also, I write a tiny script to verify the result with shared-du as below, it show the total shared extents against the target storage in bytes.

usage:
./show_shared_extents.sh [storage_mount_path] [storage_device]
like: ./show_shared_extents.sh /storage /dev/sda8

#!/bin/bash

DEBUGGER="/sbin/debugfs.ocfs2 -n"

#
# Get the block size and cluster size, we make use of cluster size to calculate the

# shared extent physical offset and length in bytes.
#
ocfs2_block_cluster_size=($(echo "stats" | $DEBUGGER -n /dev/sda8 | grep "Block Size Bits" | awk '{
print $4" "$8 }'))
block_size=$[ 2 ** ${ocfs2_block_cluster_size[0]} ]
cluster_size=$[ 2 ** ${ocfs2_block_cluster_size[1]} ]
function process_file() {
	local __f=$1
        local device=$2
	local __start=0
	local __lines=0
	local start_line=0
	local end_line=0

	inode=$(stat --format="%i" ${__f})

        #
        # Check if we meet a refcount file
        #
	refcount_file=$(echo "stat <$inode>" | $DEBUGGER $device | sed '5!d' | grep "Refcounted")

	if (test -n "$refcount_file") then
                refcount_records=($(echo "refcount <$inode>"	|
				    $DEBUGGER $device		|
			    	    grep -n "Refcount records"	|
				    awk -F':' '{print $1 $4}'))

		refcount_records_num=${#refcount_records[@]}

		i=0
		while [[ $i -lt $refcount_records_num ]]
		do
			__start=${refcount_records[$i]}
			(( i++ ))
			__lines=$[ ${refcount_records[$i]} + 1 ]
			(( i++ ))
			let "start_line = __start + 1"
			let "end_line = start_line + __lines"

			extents=($(echo "refcount <$inode>" | $DEBUGGER $device |
				   awk "FNR > $start_line && FNR < $end_line"	|
				   awk '{ print $2" "$3" "$4 }' ))

			extents_num=${#extents[@]}

			for (( j = 0; j < $extents_num; ))
			do
				physical_offset=$[ ${extents[$j]} * $cluster_size ]

				(( j++ ))
				length=$[ ${extents[$j]} * $cluster_size ]
				(( j++ ))

                        	#
				# Decrease the reference count to meet the du semantics
				#
				count=$[${extents[$j]} - 1]
				(( j++ ))

				extent_array[$physical_offset]="$physical_offset:$length:$count"
			done
		done
	fi
}

STORAGE_MOUNT_PATH=$1
STORAGE_DEVICE=$2

for f in $(find $STORAGE_MOUNT_PATH -type f)
do

	process_file ${f} $STORAGE_DEVICE

done

items=${#extent_array[*]}

total_shared_length=0
for item in ${extent_array[@]}
do

	shared_length=$(echo "${item}" | awk -F: '{ print $2 * $3}')
	let "total_shared_length += shared_length"

done

echo "TOTAL_SHARED_LENGTH: $total_shared_length"

Regards,
-Jeff