[Ocfs2-devel] [PATCH 1/4] du_enhancement: add the shared extents and the footprint statistics support v1

[Ocfs2-devel] [PATCH 1/4] du_enhancement: add the shared extents and the footprint statistics support v1

[Jeff Liu]

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 <jeff.liu@oracle.com>
---
 gnulib |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/gnulib b/gnulib
index 8fc05d0..4b93a25 160000
--- a/gnulib
+++ b/gnulib
@@ -1 +1 @@
-Subproject commit 8fc05d032b3f9a9d068613ab5ee297b4e7d5a08a
+Subproject commit 4b93a2579fb567b9fbbeb24439770d814dac95cd
-- 
1.5.4.3

[Ocfs2-devel] [PATCH 2/4] du_enhancement: add rbtree algorithm support

[Jeff Liu]

rbtree algorithm copy from ocfs2-tools

Signed-off-by: Jeff Liu <jeff.liu@oracle.com>
---
 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

diff --git a/lib/Makefile.am b/lib/Makefile.am
index c89ef75..2b814d8 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -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)
diff --git a/lib/rbtree.c b/lib/rbtree.c
new file mode 100644
index 0000000..a497d28
--- /dev/null
+++ b/lib/rbtree.c
@@ -0,0 +1,395 @@
+/* -*- mode: c; c-basic-offset: 8; -*-
+ * vim: noexpandtab sw=8 ts=8 sts=0:
+ *
+ * kernel-rbtree.c
+ *
+ * This is imported from the Linux kernel to give us a tested and
+ * portable tree library.
+ */
+/*
+  Red Black Trees
+  (C) 1999  Andrea Arcangeli <andrea@suse.de>
+  (C) 2002  David Woodhouse <dwmw2@infradead.org>
+
+  This program is free software; you can redistribute it and/or modify
+  it under the terms of the GNU General Public License as published by
+  the Free Software Foundation; either version 2 of the License, or
+  (at your option) any later version.
+
+  This program is distributed in the hope that it will be useful,
+  but WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+  GNU General Public License for more details.
+
+  You should have received a copy of the GNU General Public License
+  along with this program; if not, write to the Free Software
+  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+  linux/lib/rbtree.c
+*/
+
+#include "rbtree.h"
+
+static void __rb_rotate_left (struct rb_node *node, struct rb_root *root)
+{
+  struct rb_node *right = node->rb_right;
+
+  if ((node->rb_right = right->rb_left))
+    right->rb_left->rb_parent = node;
+  right->rb_left = node;
+
+  if ((right->rb_parent = node->rb_parent))
+    {
+      if (node == node->rb_parent->rb_left)
+        node->rb_parent->rb_left = right;
+      else
+        node->rb_parent->rb_right = right;
+    }
+  else
+    root->rb_node = right;
+    node->rb_parent = right;
+}
+
+static void __rb_rotate_right (struct rb_node *node, struct rb_root *root)
+{
+  struct rb_node *left = node->rb_left;
+
+  if ((node->rb_left = left->rb_right))
+    left->rb_right->rb_parent = node;
+  left->rb_right = node;
+
+  if ((left->rb_parent = node->rb_parent))
+    {
+      if (node == node->rb_parent->rb_right)
+        node->rb_parent->rb_right = left;
+      else
+        node->rb_parent->rb_left = left;
+    }
+  else
+    root->rb_node = left;
+
+  node->rb_parent = left;
+}
+
+void rb_insert_color (struct rb_node *node, struct rb_root *root)
+{
+  struct rb_node *parent, *gparent;
+
+  while ((parent = node->rb_parent) && parent->rb_color == RB_RED)
+    {
+      gparent = parent->rb_parent;
+
+      if (parent == gparent->rb_left)
+        {
+          {
+            register struct rb_node *uncle = gparent->rb_right;
+            if (uncle && uncle->rb_color == RB_RED)
+              {
+                uncle->rb_color = RB_BLACK;
+                parent->rb_color = RB_BLACK;
+                gparent->rb_color = RB_RED;
+                node = gparent;
+                continue;
+              }
+          }
+
+          if (parent->rb_right == node)
+            {
+              register struct rb_node *tmp;
+              __rb_rotate_left(parent, root);
+              tmp = parent;
+              parent = node;
+              node = tmp;
+            }
+
+        parent->rb_color = RB_BLACK;
+        gparent->rb_color = RB_RED;
+        __rb_rotate_right(gparent, root);
+        }
+      else
+        {
+          {
+            register struct rb_node *uncle = gparent->rb_left;
+            if (uncle && uncle->rb_color == RB_RED)
+              {
+                uncle->rb_color = RB_BLACK;
+                parent->rb_color = RB_BLACK;
+                gparent->rb_color = RB_RED;
+                node = gparent;
+                continue;
+              }
+          }
+
+          if (parent->rb_left == node)
+            {
+              register struct rb_node *tmp;
+              __rb_rotate_right(parent, root);
+              tmp = parent;
+              parent = node;
+              node = tmp;
+            }
+
+          parent->rb_color = RB_BLACK;
+          gparent->rb_color = RB_RED;
+          __rb_rotate_left(gparent, root);
+        }
+    }
+
+  root->rb_node->rb_color = RB_BLACK;
+}
+
+static void __rb_erase_color (struct rb_node *node, struct rb_node *parent,
+			      struct rb_root *root)
+{
+  struct rb_node *other;
+
+  while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node)
+    {
+      if (parent->rb_left == node)
+        {
+          other = parent->rb_right;
+          if (other->rb_color == RB_RED)
+            {
+              other->rb_color = RB_BLACK;
+              parent->rb_color = RB_RED;
+              __rb_rotate_left(parent, root);
+              other = parent->rb_right;
+            }
+          if ((!other->rb_left || other->rb_left->rb_color == RB_BLACK) &&
+              (!other->rb_right || other->rb_right->rb_color == RB_BLACK))
+            {
+              other->rb_color = RB_RED;
+              node = parent;
+              parent = node->rb_parent;
+            }
+          else
+            {
+              if (!other->rb_right || other->rb_right->rb_color == RB_BLACK)
+                {
+                  register struct rb_node *o_left;
+                  if ((o_left = other->rb_left))
+                    o_left->rb_color = RB_BLACK;
+                  other->rb_color = RB_RED;
+                  __rb_rotate_right(other, root);
+                  other = parent->rb_right;
+                }
+              other->rb_color = parent->rb_color;
+              parent->rb_color = RB_BLACK;
+              if (other->rb_right)
+                other->rb_right->rb_color = RB_BLACK;
+              __rb_rotate_left(parent, root);
+              node = root->rb_node;
+              break;
+            }
+        }
+      else
+        {
+          other = parent->rb_left;
+          if (other->rb_color == RB_RED)
+            {
+              other->rb_color = RB_BLACK;
+              parent->rb_color = RB_RED;
+              __rb_rotate_right(parent, root);
+              other = parent->rb_left;
+            }
+          if ((!other->rb_left || other->rb_left->rb_color == RB_BLACK) &&
+              (!other->rb_right || other->rb_right->rb_color == RB_BLACK))
+            {
+              other->rb_color = RB_RED;
+              node = parent;
+              parent = node->rb_parent;
+            }
+          else
+            {
+              if (!other->rb_left || other->rb_left->rb_color == RB_BLACK)
+                {
+                  register struct rb_node *o_right;
+                  if ((o_right = other->rb_right))
+                    o_right->rb_color = RB_BLACK;
+                  other->rb_color = RB_RED;
+                  __rb_rotate_left(other, root);
+                  other = parent->rb_left;
+                }
+              other->rb_color = parent->rb_color;
+              parent->rb_color = RB_BLACK;
+
+              if (other->rb_left)
+                other->rb_left->rb_color = RB_BLACK;
+              __rb_rotate_right(parent, root);
+              node = root->rb_node;
+              break;
+            }
+        }
+    }
+  if (node)
+    node->rb_color = RB_BLACK;
+}
+
+void rb_erase (struct rb_node *node, struct rb_root *root)
+{
+  struct rb_node *child, *parent;
+  int color;
+
+  if (!node->rb_left)
+    child = node->rb_right;
+  else if (!node->rb_right)
+    child = node->rb_left;
+  else
+    {
+      struct rb_node *old = node, *left;
+
+      node = node->rb_right;
+      while ((left = node->rb_left) != NULL)
+        node = left;
+      child = node->rb_right;
+      parent = node->rb_parent;
+      color = node->rb_color;
+
+      if (child)
+        child->rb_parent = parent;
+      if (parent)
+        {
+          if (parent->rb_left == node)
+            parent->rb_left = child;
+          else
+            parent->rb_right = child;
+        }
+      else
+        root->rb_node = child;
+
+      if (node->rb_parent == old)
+        parent = node;
+      node->rb_parent = old->rb_parent;
+      node->rb_color = old->rb_color;
+      node->rb_right = old->rb_right;
+      node->rb_left = old->rb_left;
+
+      if (old->rb_parent)
+        {
+          if (old->rb_parent->rb_left == old)
+            old->rb_parent->rb_left = node;
+          else
+            old->rb_parent->rb_right = node;
+        } else
+          root->rb_node = node;
+
+      old->rb_left->rb_parent = node;
+      if (old->rb_right)
+        old->rb_right->rb_parent = node;
+      goto color;
+  }
+
+  parent = node->rb_parent;
+  color = node->rb_color;
+
+  if (child)
+    child->rb_parent = parent;
+  if (parent)
+    {
+      if (parent->rb_left == node)
+        parent->rb_left = child;
+      else
+        parent->rb_right = child;
+    }
+  else
+    root->rb_node = child;
+
+color:
+if (color == RB_BLACK)
+  __rb_erase_color(child, parent, root);
+}
+
+/*
+ * This function returns the first node (in sort order) of the tree.
+ */
+struct rb_node *rb_first (struct rb_root *root)
+{
+  struct rb_node *n;
+
+  n = root->rb_node;
+  if (!n)
+    return NULL;
+  while (n->rb_left)
+    n = n->rb_left;
+  return n;
+}
+
+struct rb_node *rb_last (struct rb_root *root)
+{
+  struct rb_node *n;
+
+  n = root->rb_node;
+  if (!n)
+    return NULL;
+  while (n->rb_right)
+    n = n->rb_right;
+  return n;
+}
+
+struct rb_node *rb_next (struct rb_node *node)
+{
+  /* If we have a right-hand child, go down and then left as far
+   * as we can. */
+  if (node->rb_right)
+    {
+      node = node->rb_right;
+      while (node->rb_left)
+        node=node->rb_left;
+      return node;
+    }
+
+  /* No right-hand children.  Everything down and left is
+   * smaller than us, so any 'next' node must be in the general
+   * direction of our parent. Go up the tree; any time the
+   * ancestor is a right-hand child of its parent, keep going
+   * up. First time it's a left-hand child of its parent, said
+   * parent is our 'next' node. */
+  while (node->rb_parent && node == node->rb_parent->rb_right)
+    node = node->rb_parent;
+
+  return node->rb_parent;
+}
+
+struct rb_node *rb_prev (struct rb_node *node)
+{
+  /* If we have a left-hand child, go down and then right as far
+   * as we can. */
+  if (node->rb_left)
+    {
+      node = node->rb_left;
+      while (node->rb_right)
+        node=node->rb_right;
+      return node;
+    }
+
+  /* No left-hand children. Go up till we find an ancestor which
+   * is a right-hand child of its parent */
+  while (node->rb_parent && node == node->rb_parent->rb_left)
+    node = node->rb_parent;
+
+  return node->rb_parent;
+}
+
+void rb_replace_node (struct rb_node *victim, struct rb_node *new,
+		     struct rb_root *root)
+{
+  struct rb_node *parent = victim->rb_parent;
+
+  /* Set the surrounding nodes to point to the replacement */
+  if (parent) {
+    if (victim == parent->rb_left)
+      parent->rb_left = new;
+    else
+      parent->rb_right = new;
+  } else {
+    root->rb_node = new;
+  }
+
+  if (victim->rb_left)
+    victim->rb_left->rb_parent = new;
+  if (victim->rb_right)
+    victim->rb_right->rb_parent = new;
+
+  /* Copy the pointers/colour from the victim to the replacement */
+  *new = *victim;
+}
diff --git a/lib/rbtree.h b/lib/rbtree.h
new file mode 100644
index 0000000..ad646b1
--- /dev/null
+++ b/lib/rbtree.h
@@ -0,0 +1,143 @@
+/*
+  Red Black Trees
+  (C) 1999  Andrea Arcangeli <andrea@suse.de>
+
+  This program is free software; you can redistribute it and/or modify
+  it under the terms of the GNU General Public License as published by
+  the Free Software Foundation; either version 2 of the License, or
+  (at your option) any later version.
+
+  This program is distributed in the hope that it will be useful,
+  but WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+  GNU General Public License for more details.
+
+  You should have received a copy of the GNU General Public License
+  along with this program; if not, write to the Free Software
+  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+  rbtree.h
+
+  To use rbtrees you'll have to implement your own insert and search cores.
+  This will avoid us to use callbacks and to drop drammatically performances.
+  I know it's not the cleaner way,  but in C (not in C++) to get
+  performances and genericity...
+
+  Some example of insert and search follows here. The search is a plain
+  normal search over an ordered tree. The insert instead must be implemented
+  int two steps: as first thing the code must insert the element in
+  order as a red leaf in the tree, then the support library function
+  rb_insert_color() must be called. Such function will do the
+  not trivial work to rebalance the rbtree if necessary.
+
+-----------------------------------------------------------------------
+static inline struct page * rb_search_page_cache (struct inode * inode,
+						  unsigned long offset)
+{
+  struct rb_node * n = inode->i_rb_page_cache.rb_node;
+  struct page * page;
+
+  while (n)
+    {
+      page = rb_entry (n, struct page, rb_page_cache);
+
+      if (offset < page->offset)
+        n = n->rb_left;
+      else if (offset > page->offset)
+        n = n->rb_right;
+      else
+        return page;
+    }
+  return NULL;
+}
+
+static inline struct page * __rb_insert_page_cache (struct inode * inode,
+						    unsigned long offset,
+						    struct rb_node * node)
+{
+  struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
+  struct rb_node * parent = NULL;
+  struct page * page;
+
+  while (*p)
+    {
+      parent = *p;
+      page = rb_entry (parent, struct page, rb_page_cache);
+
+      if (offset < page->offset)
+        p = &(*p)->rb_left;
+      else if (offset > page->offset)
+        p = &(*p)->rb_right;
+      else
+        return page;
+    }
+
+  rb_link_node (node, parent, p);
+
+  return NULL;
+}
+
+static inline struct page * rb_insert_page_cache (struct inode * inode,
+						  unsigned long offset,
+						  struct rb_node * node)
+{
+  struct page * ret;
+  if ((ret = __rb_insert_page_cache (inode, offset, node)))
+    goto out;
+  rb_insert_color (node, &inode->i_rb_page_cache);
+ out:
+	return ret;
+}
+-----------------------------------------------------------------------
+*/
+
+#ifndef	_LINUX_RBTREE_H
+#define	_LINUX_RBTREE_H
+
+#include <stdlib.h>
+
+struct rb_node
+  {
+    struct rb_node *rb_parent;
+    int rb_color;
+#define	RB_RED    0
+#define	RB_BLACK  1
+    struct rb_node *rb_right;
+    struct rb_node *rb_left;
+  };
+
+struct rb_root
+  {
+    struct rb_node *rb_node;
+  };
+
+#define RB_ROOT	(struct rb_root) { NULL, }
+#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 *);
+
+/* Find logical next and previous nodes in a tree */
+extern struct rb_node *rb_next (struct rb_node *);
+extern struct rb_node *rb_prev (struct rb_node *);
+extern struct rb_node *rb_first (struct rb_root *);
+extern struct rb_node *rb_last (struct rb_root *);
+
+/* Fast replacement of a single node without remove/rebalance/add/rebalance */
+extern void rb_replace_node (struct rb_node *victim,
+                             struct rb_node *new,
+                             struct rb_root *root);
+
+static inline void rb_link_node (struct rb_node * node,
+                                 struct rb_node * parent,
+                                 struct rb_node ** rb_link)
+{
+  node->rb_parent = parent;
+  node->rb_color = RB_RED;
+  node->rb_left = node->rb_right = NULL;
+
+  *rb_link = node;
+}
+
+#endif	/* _LINUX_RBTREE_H */
-- 
1.5.4.3

[Ocfs2-devel] [PATCH 3/4] du_enhancement: add fiemap header

[Jeff Liu]

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

Signed-off-by: Jeff Liu <jeff.liu@oracle.com>
---
 src/fiemap.h |   68 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 68 insertions(+), 0 deletions(-)
 create mode 100644 src/fiemap.h

diff --git a/src/fiemap.h b/src/fiemap.h
new file mode 100644
index 0000000..df3a32c
--- /dev/null
+++ b/src/fiemap.h
@@ -0,0 +1,68 @@
+/*
+ * FS_IOC_FIEMAP ioctl infrastructure.
+ *
+ * Some portions copyright (C) 2007 Cluster File Systems, Inc
+ *
+ * Authors: Mark Fasheh <mfasheh@suse.com>
+ *          Kalpak Shah <kalpak.shah@sun.com>
+ *          Andreas Dilger <adilger@sun.com>
+ */
+
+#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 */
-- 
1.5.4.3

[Ocfs2-devel] [PATCH 4/4] du_enhancement: show the shared extents per file and the footprint

[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 <jeff.liu@oracle.com>
---
 lib/rbtree.h |    4 +-
 src/du.c     |  378 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 378 insertions(+), 4 deletions(-)

diff --git a/lib/rbtree.h b/lib/rbtree.h
index ad646b1..bb23391 100644
--- a/lib/rbtree.h
+++ b/lib/rbtree.h
@@ -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 *);
diff --git a/src/du.c b/src/du.c
index 907ad79..df4cb23 100644
--- a/src/du.c
+++ b/src/du.c
@@ -26,6 +26,8 @@
 #include <config.h>
 #include <getopt.h>
 #include <sys/types.h>
+#include <sys/ioctl.h>
+#include <linux/fs.h>
 #include <assert.h>
 #include "system.h"
 #include "argmatch.h"
@@ -42,6 +44,8 @@
 #include "stdio--.h"
 #include "xfts.h"
 #include "xstrtol.h"
+#include "rbtree.h"
+#include "fiemap.h"
 
 extern bool fts_debug;
 
@@ -65,6 +69,8 @@ extern bool fts_debug;
 /* Initial size of the hash table.  */
 #define INITIAL_TABLE_SIZE 103
 
+#define FS_IOC_FIEMAP _IOWR('f', 11, struct fiemap)
+
 /* Hash structure for inode and device numbers.  The separate entry
    structure makes it easier to rehash "in place".  */
 struct entry
@@ -171,6 +177,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 shared extents per file and the 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;
 
@@ -180,6 +214,11 @@ static struct exclude *exclude;
 /* Grand total size of all args, in bytes. Also latest modified date. */
 static struct duinfo tot_dui;
 
+/* Undefine, to avoid warning about redefinition on some systems.
+ * copy from src/comm.c.  */
+#undef min
+#define min(x, y) ((x) < (y) ? (x) : (y))
+
 #define IS_DIR_TYPE(Type)	\
   ((Type) == FTS_DP		\
    || (Type) == FTS_DNR)
@@ -194,7 +233,9 @@ enum
   HUMAN_SI_OPTION,
   MAX_DEPTH_OPTION,
   TIME_OPTION,
-  TIME_STYLE_OPTION
+  TIME_STYLE_OPTION,
+  FIEMAP_FLAG_SYNC_OPTION,
+  FIEMAP_FLAG_XATTR_OPTION
 };
 
 static struct option const long_options[] =
@@ -204,6 +245,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},
@@ -302,6 +346,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\
@@ -437,10 +486,301 @@ 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);
+}
+
+/* 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);
 }
 
+/* Free all allocated extents info.  */
+
+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 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_right;
+      else if (this->ei_physical > fe_physical)
+	p = &(*p)->rb_left;
+      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);
+
+  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);
+
+      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);
+
+          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)
+            {
+	      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);
+	    }
+
+          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);
+
+          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);
+
+          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);
+    }
+}
+
+static void
+process_extent(const char *filename)
+{
+  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 = open (filename, O_RDONLY);
+  if (fd == -1)
+    {
+      error(0, errno, _("cannot open %s"), quote (filename));
+      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 (filename), fiemap->fm_flags);
+
+        error(0, errno, _("%s extent mapping failed"), quote (filename));
+        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 (filename));
+}
+
 /* 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
@@ -606,6 +946,9 @@ process_file (FTS *fts, FTSENT *ent)
   if (!print)
     return ok;
 
+  if (print_shared_size)
+        process_extent (file);
+
   if ((IS_DIR_TYPE (ent->fts_info) && level <= max_depth)
       || ((opt_all && level <= max_depth) || level == 0))
     print_size (&dui_to_print, file);
@@ -694,7 +1037,7 @@ main (int argc, char **argv)
   for (;;)
     {
       int oi = -1;
-      int c = getopt_long (argc, argv, DEBUG_OPT "0abchHklmsxB:DLPSX:",
+      int c = getopt_long (argc, argv, DEBUG_OPT "0abchHklmsxB:DELPSX:",
                            long_options, &oi);
       if (c == -1)
         break;
@@ -814,6 +1157,17 @@ main (int argc, char **argv)
             }
           break;
 
+	case 'E':
+	  print_shared_size = true;
+	  break;
+
+	case FIEMAP_FLAG_SYNC_OPTION:
+	  fiemap_bits_flags |= FIEMAP_FLAG_SYNC;
+          break;
+
+        case FIEMAP_FLAG_XATTR_OPTION:
+	  fiemap_bits_flags |= FIEMAP_FLAG_XATTR;
+	  break;
         case FILES0_FROM_OPTION:
           files_from = optarg;
           break;
@@ -865,6 +1219,16 @@ main (int argc, char **argv)
       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_summarize_only)
     max_depth = 0;
 
@@ -1025,6 +1389,16 @@ main (int argc, char **argv)
   if (print_grand_total)
     print_size (&tot_dui, _("total"));
 
+  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);
-- 
1.5.4.3

[Ocfs2-devel] [PATCH 1/4] du_enhancement: add the shared extents and the footprint statistics support v1

[Coly Li]

On 2010?01?26? 16:00, Jeff Liu Wrote:
> 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 <jeff.liu@oracle.com>
> ---

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 ?

-- 
Coly Li
SuSE Labs

[Ocfs2-devel] [PATCH 1/4] du_enhancement: add the shared extents and the footprint statistics support v1

[Sunil Mushran]

Coly Li wrote:
> 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.

[Ocfs2-devel] [PATCH 1/4] du_enhancement: add the shared extents and the footprint statistics support v1

[Coly Li]

On 2010?01?27? 03:52, Sunil Mushran Wrote:
> Coly Li wrote:
>> 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 :-)

-- 
Coly Li
SuSE Labs

[Ocfs2-devel] [PATCH 1/4] du_enhancement: add the shared extents and the footprint statistics support v1

[jeff.liu]

An HTML attachment was scrubbed...
URL: http://oss.oracle.com/pipermail/ocfs2-devel/attachments/20100127/f17de160/attachment.html 

[Ocfs2-devel] [PATCH 4/4] du_enhancement: show the shared extents per file and the footprint

[Tao Ma]

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

Jeff Liu wrote:
> 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 <jeff.liu@oracle.com>
> ---
>  lib/rbtree.h |    4 +-
>  src/du.c     |  378 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
>  2 files changed, 378 insertions(+), 4 deletions(-)
> 
> diff --git a/lib/rbtree.h b/lib/rbtree.h
> index ad646b1..bb23391 100644
> --- a/lib/rbtree.h
> +++ b/lib/rbtree.h
> @@ -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 '\"?
>  
>  extern void rb_insert_color (struct rb_node *, struct rb_root *);
>  extern void rb_erase (struct rb_node *, struct rb_root *);
<snip>
> +/* 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, 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.
> +      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.
> +
> +          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)
> +            {
> +	      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.
> +	    }
> +
> +          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);
> +
> +          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.
> +
> +          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

[Ocfs2-devel] [PATCH 4/4] du_enhancement: show the shared extents per file and the footprint

[jeff.liu]

Hi Tao,

Thanks for your help review.

Tao Ma ??:
> Hi Jeff,
> Thanks for the work. and sorry for the delay of review.
>
> Jeff Liu wrote:
>> 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 <jeff.liu@oracle.com>
>> ---
>> lib/rbtree.h | 4 +-
>> src/du.c | 378
>> +++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
>> 2 files changed, 378 insertions(+), 4 deletions(-)
>>
>> diff --git a/lib/rbtree.h b/lib/rbtree.h
>> index ad646b1..bb23391 100644
>> --- a/lib/rbtree.h
>> +++ b/lib/rbtree.h
>> @@ -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 '\"?
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.
>>
>> extern void rb_insert_color (struct rb_node *, struct rb_root *);
>> extern void rb_erase (struct rb_node *, struct rb_root *);
> <snip>
>> +/* 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,
>> 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.
That's really needed.
>> + 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.
>> +
>> + 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)
>> + {
>> + 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.
>> + }
>> +
>> + 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);
>> +
>> + 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.
> 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
>> +
>> + 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);
>> + }
>> +}
>
BTW, Maybe I will have to delay the new patch submits time due to my
current works and the spring Festival annual leave.
> Regards,
> Tao
Thanks,
-Jeff