[vfs PATCH v2 0/4] vfs: Expand iomap interface to fiemap

[vfs PATCH v2 0/4] vfs: Expand iomap interface to fiemap

[Bob Peterson]

Back in October 2014, I proposed an improvement to fiemap to accomodate
very large sparse files. This was done because the existing blockmap-based
code skips holes one block at a time, which is extremely slow when it comes
to large holes. For example, doing fiemap on a 1PB file whose only byte
exists at EOF can take an extremely long time. To recreate:

dd if=/dev/zero of=/mnt/holey-P bs=1 count=1 seek=1P
time filefrag -v /mnt/holey-P

At that time, someone suggested I use the iomap interface proposed by
Dave Chinner a long time ago, and so my patches never got off the ground
(until now).

Since then, Christoph apparently added the basics of iomap to exportfs.h.
which today is minimal, and limited to exportfs users.

On 11 January 2016, I posted a vfs patch that expanded the use of the iomap
infrastructure, but iomap was added to address_space_operations.

On 21 January 2016, Jan Kara suggested it NOT be included as an a_op,
but rather, to have the new iomap function be passed in, similar to
get_blocks(), along with some pretty generic flags, rather than a set of
commands.

This v2 patch set is my latest attempt to implement Jan's suggestions.

The first patch moves the iomap infrastructure from exportfs.h to its own
iomap.h. It also adds some basic declares for the iomap type and flags.

The second patch adds a new __generic_iomap_fiemap interface to be used
by file systems who want it. My original version of this function looked
nearly identical to the blockmap version, but this one is smaller and
simpler. So if people don't like my implementation, I can revert to that one.

The third patch introduces a new __gfs2_io_map function to the GFS2 file
system. To keep things simple, I omitted block allocations from this
function for now.

The fourth patch hooks the new function into GFS2's fiemap to take
advantage of the new code.

The result: for a 1PB sparse file, filefrag takes milliseconds rather
than a week.

Signed-off-by: Bob Peterson <rpeterso@redhat.com>
---
Bob Peterson (4):
  VFS: move iomap infrastructure from exportfs.h, add iomap to aops
  VFS: Add new __generic_iomap_fiemap interface
  GFS2: Add function __gfs2_io_map
  GFS2: Use new iomap interface for fiemap

 fs/gfs2/bmap.c           | 160 +++++++++++++++++++++++++++++++++++++++++++++++
 fs/gfs2/bmap.h           |   2 +
 fs/gfs2/inode.c          |   4 +-
 fs/ioctl.c               |  97 ++++++++++++++++++++++++++++
 include/linux/exportfs.h |  16 +----
 include/linux/fs.h       |  12 +++-
 include/linux/iomap.h    |  29 +++++++++
 7 files changed, 302 insertions(+), 18 deletions(-)
 create mode 100644 include/linux/iomap.h

-- 
2.5.0

[vfs PATCH v2 1/4] VFS: move iomap infrastructure from exportfs.h, add iomap to aops

[Bob Peterson]

This patch moves the iomap infrastructure from its current location in
exportfs.h to a new iomap.h. This may be used not only by nfs, but also by
other file systems. This also adds an iomap function call to the
address_space_operations. This will facilitate future improvements such
as a more efficient fiemap for holey files. Hopefully it will one day be
used for multipage writes as well.

Signed-off-by: Bob Peterson <rpeterso@redhat.com>
---
 include/linux/exportfs.h | 16 +---------------
 include/linux/fs.h       |  2 ++
 include/linux/iomap.h    | 29 +++++++++++++++++++++++++++++
 3 files changed, 32 insertions(+), 15 deletions(-)
 create mode 100644 include/linux/iomap.h

diff --git a/include/linux/exportfs.h b/include/linux/exportfs.h
index fa05e04..bb564c1 100644
--- a/include/linux/exportfs.h
+++ b/include/linux/exportfs.h
@@ -2,6 +2,7 @@
 #define LINUX_EXPORTFS_H 1
 
 #include <linux/types.h>
+#include <linux/iomap.h>
 
 struct dentry;
 struct iattr;
@@ -181,21 +182,6 @@ struct fid {
  *    get_name is not (which is possibly inconsistent)
  */
 
-/* types of block ranges for multipage write mappings. */
-#define IOMAP_HOLE	0x01	/* no blocks allocated, need allocation */
-#define IOMAP_DELALLOC	0x02	/* delayed allocation blocks */
-#define IOMAP_MAPPED	0x03	/* blocks allocated @blkno */
-#define IOMAP_UNWRITTEN	0x04	/* blocks allocated @blkno in unwritten state */
-
-#define IOMAP_NULL_BLOCK -1LL	/* blkno is not valid */
-
-struct iomap {
-	sector_t	blkno;	/* first sector of mapping */
-	loff_t		offset;	/* file offset of mapping, bytes */
-	u64		length;	/* length of mapping, bytes */
-	int		type;	/* type of mapping */
-};
-
 struct export_operations {
 	int (*encode_fh)(struct inode *inode, __u32 *fh, int *max_len,
 			struct inode *parent);
diff --git a/include/linux/fs.h b/include/linux/fs.h
index daf399d..6ae2b37 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -21,6 +21,7 @@
 #include <linux/capability.h>
 #include <linux/semaphore.h>
 #include <linux/fiemap.h>
+#include <linux/iomap.h>
 #include <linux/rculist_bl.h>
 #include <linux/atomic.h>
 #include <linux/shrinker.h>
@@ -316,6 +317,7 @@ enum positive_aop_returns {
 struct page;
 struct address_space;
 struct writeback_control;
+struct iomap;
 
 #define IOCB_EVENTFD		(1 << 0)
 #define IOCB_APPEND		(1 << 1)
diff --git a/include/linux/iomap.h b/include/linux/iomap.h
new file mode 100644
index 0000000..0026258
--- /dev/null
+++ b/include/linux/iomap.h
@@ -0,0 +1,29 @@
+#ifndef _IOMAP_H
+#define _IOMAP_H
+
+/* iomap flags */
+#define IOMAP_MODE_READ	0x01	/* iomap operation requires RO lock */
+#define IOMAP_MODE_RDWR	0x02	/* iomap operation requires R/W lock */
+
+/* types of block ranges for multipage write mappings. */
+#define IOMAP_HOLE	0x01	/* no blocks allocated, need allocation */
+#define IOMAP_DELALLOC	0x02	/* delayed allocation blocks */
+#define IOMAP_MAPPED	0x03	/* blocks allocated @blkno */
+#define IOMAP_UNWRITTEN	0x04	/* blocks allocated @blkno in unwritten state */
+
+#define IOMAP_NULL_BLOCK -1LL	/* blkno is not valid */
+
+struct iomap {
+	sector_t	blkno;	/* first sector of mapping */
+	loff_t		offset;	/* file offset of mapping, bytes */
+	ssize_t		length;	/* length of mapping, bytes */
+	int		type;	/* type of mapping */
+	void		*priv;	/* fs private data associated with map */
+};
+
+static inline bool iomap_needs_allocation(struct iomap *iomap)
+{
+	return iomap->type == IOMAP_HOLE;
+}
+
+#endif /* _IOMAP_H */
-- 
2.5.0

[vfs PATCH v2 2/4] VFS: Add new __generic_iomap_fiemap interface

[Bob Peterson]

This patch adds a new function __generic_iomap_fiemap similar to
__generic_block_fiemap, but it uses the new iomap interface.

Signed-off-by: Bob Peterson <rpeterso@redhat.com>
---
 fs/ioctl.c         | 97 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 include/linux/fs.h | 12 +++++--
 2 files changed, 107 insertions(+), 2 deletions(-)

diff --git a/fs/ioctl.c b/fs/ioctl.c
index 29466c3..49f3b34 100644
--- a/fs/ioctl.c
+++ b/fs/ioctl.c
@@ -15,6 +15,8 @@
 #include <linux/writeback.h>
 #include <linux/buffer_head.h>
 #include <linux/falloc.h>
+#include <linux/iomap.h>
+
 #include "internal.h"
 
 #include <asm/ioctls.h>
@@ -251,6 +253,101 @@ static inline loff_t blk_to_logical(struct inode *inode, sector_t blk)
 }
 
 /**
+ * __generic_iomap_fiemap - FIEMAP for iomap based inodes (no locking)
+ * @inode: the inode to map
+ * @fieinfo: the fiemap info struct that will be passed back to userspace
+ * @start: where to start mapping in the inode
+ * @len: how much space to map
+ *
+ * This does FIEMAP for iomap based inodes.  Basically it will just loop
+ * through iomap until we hit the number of extents we want to map, or we
+ * go past the end of the file and hit a hole.
+ *
+ * If it is possible to have data blocks beyond a hole past @inode->i_size, then
+ * please do not use this function, it will stop at the first unmapped block
+ * beyond i_size.
+ *
+ * If you use this function directly, you need to do your own locking. Use
+ * generic_iomap_fiemap if you want the locking done for you.
+ */
+
+int __generic_iomap_fiemap(struct inode *inode,
+			   struct fiemap_extent_info *fieinfo, loff_t start,
+			   loff_t len, iomap_t iomap)
+{
+	struct iomap iom, prev_iom;
+	loff_t isize = i_size_read(inode);
+	int ret = 0;
+
+	ret = fiemap_check_flags(fieinfo, FIEMAP_FLAG_SYNC);
+	memset(&prev_iom, 0, sizeof(prev_iom));
+	if (len >= isize)
+		len = isize;
+
+	while ((ret == 0) && (start < isize) && len) {
+		memset(&iom, 0, sizeof(iom));
+		ret = iomap(inode->i_mapping, start, len, &iom,
+			    IOMAP_MODE_READ);
+		if (ret)
+			break;
+
+		if (!iomap_needs_allocation(&iom)) {
+			if (prev_iom.blkno)
+				ret = fiemap_fill_next_extent(fieinfo,
+							      prev_iom.offset,
+							      blk_to_logical(inode,
+							      prev_iom.blkno),
+							      prev_iom.length,
+							      FIEMAP_EXTENT_MERGED);
+			prev_iom = iom;
+		}
+		start += iom.length;
+		if (len < iom.length)
+			break;
+		len -= iom.length;
+		cond_resched();
+	}
+
+	if (prev_iom.blkno)
+		ret = fiemap_fill_next_extent(fieinfo, prev_iom.offset,
+					      blk_to_logical(inode,
+							     prev_iom.blkno),
+					      prev_iom.length,
+					      FIEMAP_EXTENT_MERGED |
+					      FIEMAP_EXTENT_LAST);
+	/* If ret is 1 then we just hit the end of the extent array */
+	if (ret == 1)
+		ret = 0;
+
+	return ret;
+}
+EXPORT_SYMBOL(__generic_iomap_fiemap);
+
+/**
+ * generic_iomap_fiemap - FIEMAP for block based inodes
+ * @inode: The inode to map
+ * @fieinfo: The mapping information
+ * @start: The initial block to map
+ * @len: The length of the extect to attempt to map
+ * @get_block: The block mapping function for the fs
+ *
+ * Calls __generic_block_fiemap to map the inode, after taking
+ * the inode's mutex lock.
+ */
+
+int generic_iomap_fiemap(struct inode *inode,
+			 struct fiemap_extent_info *fieinfo, u64 start,
+			 u64 len, iomap_t iomap)
+{
+	int ret;
+	mutex_lock(&inode->i_mutex);
+	ret = __generic_iomap_fiemap(inode, fieinfo, start, len, iomap);
+	mutex_unlock(&inode->i_mutex);
+	return ret;
+}
+EXPORT_SYMBOL(generic_iomap_fiemap);
+
+/**
  * __generic_block_fiemap - FIEMAP for block based inodes (no locking)
  * @inode: the inode to map
  * @fieinfo: the fiemap info struct that will be passed back to userspace
diff --git a/include/linux/fs.h b/include/linux/fs.h
index 6ae2b37..9c431ff 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -69,8 +69,12 @@ extern int sysctl_protected_symlinks;
 extern int sysctl_protected_hardlinks;
 
 struct buffer_head;
+struct address_space;
+struct iomap;
 typedef int (get_block_t)(struct inode *inode, sector_t iblock,
 			struct buffer_head *bh_result, int create);
+typedef int (iomap_t)(struct address_space *mapping, loff_t pos,
+                    ssize_t length, struct iomap *iomap, unsigned int flags);
 typedef void (dio_iodone_t)(struct kiocb *iocb, loff_t offset,
 			ssize_t bytes, void *private);
 typedef void (dax_iodone_t)(struct buffer_head *bh_map, int uptodate);
@@ -315,9 +319,7 @@ enum positive_aop_returns {
  * oh the beauties of C type declarations.
  */
 struct page;
-struct address_space;
 struct writeback_control;
-struct iomap;
 
 #define IOCB_EVENTFD		(1 << 0)
 #define IOCB_APPEND		(1 << 1)
@@ -2779,6 +2781,12 @@ extern int vfs_lstat(const char __user *, struct kstat *);
 extern int vfs_fstat(unsigned int, struct kstat *);
 extern int vfs_fstatat(int , const char __user *, struct kstat *, int);
 
+extern int __generic_iomap_fiemap(struct inode *inode,
+				  struct fiemap_extent_info *fieinfo,
+				  loff_t start, loff_t len, iomap_t iomap);
+extern int generic_iomap_fiemap(struct inode *inode,
+				struct fiemap_extent_info *fieinfo, u64 start,
+				u64 len, iomap_t iomap);
 extern int __generic_block_fiemap(struct inode *inode,
 				  struct fiemap_extent_info *fieinfo,
 				  loff_t start, loff_t len,
-- 
2.5.0

[vfs PATCH v2 3/4] GFS2: Add function __gfs2_io_map

[Bob Peterson]

This patch adds a generic io_map interface to GFS2 for block mapping.

Signed-off-by: Bob Peterson <rpeterso@redhat.com>
---
 fs/gfs2/bmap.c | 160 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 fs/gfs2/bmap.h |   2 +
 2 files changed, 162 insertions(+)

diff --git a/fs/gfs2/bmap.c b/fs/gfs2/bmap.c
index 61296ec..7979a54 100644
--- a/fs/gfs2/bmap.c
+++ b/fs/gfs2/bmap.c
@@ -13,6 +13,7 @@
 #include <linux/blkdev.h>
 #include <linux/gfs2_ondisk.h>
 #include <linux/crc32.h>
+#include <linux/iomap.h>
 
 #include "gfs2.h"
 #include "incore.h"
@@ -587,6 +588,165 @@ static int gfs2_bmap_alloc(struct inode *inode, const sector_t lblock,
 }
 
 /**
+ * hole_size - figure out the size of a hole
+ * @ip: The inode
+ * @lblock: The logical starting block number
+ * @mp: The metapath
+ *
+ * Returns: The hole size in bytes
+ *
+ */
+static u64 hole_size(struct inode *inode, sector_t lblock, struct metapath *mp)
+{
+	struct gfs2_inode *ip = GFS2_I(inode);
+	struct gfs2_sbd *sdp = GFS2_SB(inode);
+	struct metapath mp_eof;
+	unsigned int end_of_metadata = ip->i_height - 1;
+	u64 factor = 1;
+	int hgt = end_of_metadata;
+	u64 holesz = 0, holestep;
+	const __be64 *first, *end, *ptr;
+	const struct buffer_head *bh;
+	u64 isize = i_size_read(inode);
+	int zeroptrs;
+	bool done = false;
+
+	/* Get another metapath, to the very last byte */
+	find_metapath(sdp, (isize - 1) >> inode->i_blkbits, &mp_eof,
+		      ip->i_height);
+	for (hgt = end_of_metadata; hgt >= 0 && !done; hgt--) {
+		bh = mp->mp_bh[hgt];
+		if (bh) {
+			zeroptrs = 0;
+			first = metapointer(hgt, mp);
+			end = (const __be64 *)(bh->b_data + bh->b_size);
+
+			for (ptr = first; ptr < end; ptr++) {
+				if (*ptr) {
+					done = true;
+					break;
+				} else {
+					zeroptrs++;
+				}
+			}
+		} else {
+			zeroptrs = sdp->sd_inptrs;
+		}
+		holestep = min(factor * zeroptrs,
+			       isize - (lblock + (zeroptrs * holesz)));
+		holesz += holestep;
+		if (lblock + holesz >= isize)
+			return holesz << inode->i_blkbits;
+
+		factor *= sdp->sd_inptrs;
+		if (hgt && (mp->mp_list[hgt - 1] < mp_eof.mp_list[hgt - 1]))
+			(mp->mp_list[hgt - 1])++;
+	}
+	return holesz << inode->i_blkbits;
+}
+
+/**
+ * __gfs2_io_map - Map blocks from an inode to disk blocks
+ * @mapping: The address space
+ * @pos: Starting position in bytes
+ * @length: Length to map, in bytes
+ * @iomap: The iomap structure
+ * @flags: The iomap RW flags
+ *
+ * Returns: errno
+ */
+
+int gfs2_iomap(struct address_space *mapping, loff_t pos, ssize_t length,
+	       struct iomap *iomap, unsigned int flags)
+{
+	struct inode *inode = mapping->host;
+	struct gfs2_inode *ip = GFS2_I(inode);
+	struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode);
+	unsigned int bsize = sdp->sd_sb.sb_bsize;
+	const u64 *arr = sdp->sd_heightsize;
+	__be64 *ptr;
+	sector_t lblock = pos >> sdp->sd_sb.sb_bsize_shift;
+	u64 size;
+	struct metapath mp;
+	int ret, eob;
+	unsigned int len;
+	struct buffer_head *bh;
+	u8 height;
+	loff_t isize = i_size_read(inode);
+
+	if (length == 0)
+		return -EINVAL;
+
+	iomap->offset = pos;
+	iomap->blkno = 0;
+	iomap->type = IOMAP_HOLE;
+	iomap->length = length;
+
+	if (pos >= isize)
+		return 0;
+
+	memset(mp.mp_bh, 0, sizeof(mp.mp_bh));
+	bmap_lock(ip, (flags & IOMAP_MODE_RDWR));
+	if (gfs2_is_dir(ip)) {
+		bsize = sdp->sd_jbsize;
+		arr = sdp->sd_jheightsize;
+	}
+
+	ret = gfs2_meta_inode_buffer(ip, &mp.mp_bh[0]);
+	if (ret)
+		goto out_release;
+
+	height = ip->i_height;
+	size = (lblock + 1) * bsize;
+	while (size > arr[height])
+		height++;
+	find_metapath(sdp, lblock, &mp, height);
+	ret = 1;
+	if (height > ip->i_height || gfs2_is_stuffed(ip))
+		goto do_alloc;
+	ret = lookup_metapath(ip, &mp);
+	if (ret < 0)
+		goto out_release;
+
+	if (ret != ip->i_height) {
+		if (flags & IOMAP_MODE_RDWR)
+			goto do_alloc;
+		iomap->length = hole_size(inode, lblock, &mp);
+		goto out_meta_hole;
+	}
+
+	ptr = metapointer(ip->i_height - 1, &mp);
+	iomap->blkno = be64_to_cpu(*ptr);
+	if (*ptr) {
+		iomap->type = IOMAP_MAPPED;
+	} else {
+		if (flags & IOMAP_MODE_RDWR)
+			goto do_alloc;
+		iomap->type = IOMAP_HOLE;
+	}
+	bh = mp.mp_bh[ip->i_height - 1];
+	len = gfs2_extent_length(bh->b_data, bh->b_size, ptr,
+				 length >> inode->i_blkbits, &eob);
+	iomap->length = len << sdp->sd_sb.sb_bsize_shift;
+	/* If we go past eof, round up to the nearest block */
+	if (iomap->offset + iomap->length >= isize)
+		iomap->length = (((isize - iomap->offset) + (bsize - 1)) &
+				 ~(bsize - 1));
+
+out_meta_hole:
+	ret = 0;
+out_release:
+	release_metapath(&mp);
+	bmap_unlock(ip, (flags & IOMAP_MODE_RDWR));
+	return ret;
+
+do_alloc:
+	/* Todo: Code an allocation path */
+	ret = -EINVAL;
+	goto out_release;
+}
+
+/**
  * gfs2_block_map - Map a block from an inode to a disk block
  * @inode: The inode
  * @lblock: The logical block number
diff --git a/fs/gfs2/bmap.h b/fs/gfs2/bmap.h
index 81ded5e..873f23c 100644
--- a/fs/gfs2/bmap.h
+++ b/fs/gfs2/bmap.h
@@ -47,6 +47,8 @@ static inline void gfs2_write_calc_reserv(const struct gfs2_inode *ip,
 extern int gfs2_unstuff_dinode(struct gfs2_inode *ip, struct page *page);
 extern int gfs2_block_map(struct inode *inode, sector_t lblock,
 			  struct buffer_head *bh, int create);
+extern int gfs2_iomap(struct address_space *mapping, loff_t pos,
+		      ssize_t length, struct iomap *iomap, unsigned int flags);
 extern int gfs2_extent_map(struct inode *inode, u64 lblock, int *new,
 			   u64 *dblock, unsigned *extlen);
 extern int gfs2_setattr_size(struct inode *inode, u64 size);
-- 
2.5.0

[vfs PATCH v2 4/4] GFS2: Use new iomap interface for fiemap

[Bob Peterson]

This patch switches the GFS2 fiemap interface so that it uses the
new iomap infrastructure rather than the old blockmap.

Signed-off-by: Bob Peterson <rpeterso@redhat.com>
---
 fs/gfs2/inode.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/fs/gfs2/inode.c b/fs/gfs2/inode.c
index 1bae189..f2f68bb 100644
--- a/fs/gfs2/inode.c
+++ b/fs/gfs2/inode.c
@@ -2090,8 +2090,8 @@ static int gfs2_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo,
 		if (ret == 1)
 			ret = 0;
 	} else {
-		ret = __generic_block_fiemap(inode, fieinfo, start, len,
-					     gfs2_block_map);
+		ret = __generic_iomap_fiemap(inode, fieinfo, start, len,
+					     gfs2_iomap);
 	}
 
 	gfs2_glock_dq_uninit(&gh);
-- 
2.5.0

Re: [vfs PATCH v2 1/4] VFS: move iomap infrastructure from exportfs.h, add iomap to aops

[Christoph Hellwig]

On Thu, Mar 03, 2016 at 02:31:52PM -0500, Bob Peterson wrote:
> This patch moves the iomap infrastructure from its current location in
> exportfs.h to a new iomap.h. This may be used not only by nfs, but also by

NFS never uses iomaps so far :)

> other file systems. This also adds an iomap function call to the
> address_space_operations.

It doesn't.  And adding that would be a horrible idea.

But it adds new fields and flag, some of which look flakey.
Please do a plain move as a first step.

It would also be great it you didn't include iomap.h in fs.h - fs.h
already includes way too much crap.

Re: [vfs PATCH v2 2/4] VFS: Add new __generic_iomap_fiemap interface

[Christoph Hellwig]

> +typedef int (iomap_t)(struct address_space *mapping, loff_t pos,
> +                    ssize_t length, struct iomap *iomap, unsigned int flags);

No flags argument for reads vs writes, please - just use a separate
function pointer for potential future write operations using this
interface.