ext4: add support for reading sparse files

Add support for sparse files in ext4. Also implement read-ahead, which
greatly increases the performance when transferring files from ext4.

Both features implemented by Damjan Jovanovic.

PR:		205816
MFC after:	1 week

4 files changed, 80 insertions, 34 deletions

diff --git a/sys/fs/ext2fs/ext2_bmap.c b/sys/fs/ext2fs/ext2_bmap.c
index 7d4a880..8656e59 100644
--- a/sys/fs/ext2fs/ext2_bmap.c
+++ b/sys/fs/ext2fs/ext2_bmap.c
@@ -102,9 +102,6 @@ ext4_bmapext(struct vnode *vp, int32_t bn, int64_t *bnp, int *runp, int *runb)
 	fs = ip->i_e2fs;
 	lbn = bn;
 
-	/*
-	 * TODO: need to implement read ahead to improve the performance.
-	 */
 	if (runp != NULL)
 		*runp = 0;
 
@@ -112,15 +109,25 @@ ext4_bmapext(struct vnode *vp, int32_t bn, int64_t *bnp, int *runp, int *runb)
 		*runb = 0;
 
 	ext4_ext_find_extent(fs, ip, lbn, &path);
-	ep = path.ep_ext;
-	if (ep == NULL)
-		ret = EIO;
-	else {
-		*bnp = fsbtodb(fs, lbn - ep->e_blk +
-		    (ep->e_start_lo | (daddr_t)ep->e_start_hi << 32));
-
-		if (*bnp == 0)
-			*bnp = -1;
+	if (path.ep_is_sparse) {
+		*bnp = -1;
+		if (runp != NULL)
+			*runp = path.ep_sparse_ext.e_len -
+			    (lbn - path.ep_sparse_ext.e_blk) - 1;
+	} else {
+		ep = path.ep_ext;
+		if (ep == NULL)
+			ret = EIO;
+		else {
+			*bnp = fsbtodb(fs, lbn - ep->e_blk +
+			    (ep->e_start_lo | (daddr_t)ep->e_start_hi << 32));
+
+			if (*bnp == 0)
+				*bnp = -1;
+
+			if (runp != NULL)
+				*runp = ep->e_len - (lbn - ep->e_blk) - 1;
+		}
 	}
 
 	if (path.ep_bp != NULL) {
diff --git a/sys/fs/ext2fs/ext2_extents.c b/sys/fs/ext2fs/ext2_extents.c
index 68704bb..1317fdc 100644
--- a/sys/fs/ext2fs/ext2_extents.c
+++ b/sys/fs/ext2fs/ext2_extents.c
@@ -66,13 +66,14 @@ static void
 ext4_ext_binsearch(struct inode *ip, struct ext4_extent_path *path, daddr_t lbn)
 {
 	struct ext4_extent_header *ehp = path->ep_header;
-	struct ext4_extent *l, *r, *m;
+	struct ext4_extent *first, *l, *r, *m;
 
 	if (ehp->eh_ecount == 0)
 		return;
 
-	l = (struct ext4_extent *)(char *)(ehp + 1);
-	r = (struct ext4_extent *)(char *)(ehp + 1) + ehp->eh_ecount - 1;
+	first = (struct ext4_extent *)(char *)(ehp + 1);
+	l = first;
+	r = first + ehp->eh_ecount - 1;
 	while (l <= r) {
 		m = l + (r - l) / 2;
 		if (lbn < m->e_blk)
@@ -81,7 +82,25 @@ ext4_ext_binsearch(struct inode *ip, struct ext4_extent_path *path, daddr_t lbn)
 			l = m + 1;
 	}
 
+	if (l == first) {
+		path->ep_sparse_ext.e_blk = lbn;
+		path->ep_sparse_ext.e_len = first->e_blk - lbn;
+		path->ep_sparse_ext.e_start_hi = 0;
+		path->ep_sparse_ext.e_start_lo = 0;
+		path->ep_is_sparse = 1;
+		return;
+	}
 	path->ep_ext = l - 1;
+	if (path->ep_ext->e_blk + path->ep_ext->e_len <= lbn) {
+		path->ep_sparse_ext.e_blk = lbn;
+		if (l <= (first + ehp->eh_ecount - 1))
+			path->ep_sparse_ext.e_len = l->e_blk - lbn;
+		else	// XXX: where does it end?
+			path->ep_sparse_ext.e_len = 1;
+		path->ep_sparse_ext.e_start_hi = 0;
+		path->ep_sparse_ext.e_start_lo = 0;
+		path->ep_is_sparse = 1;
+	}
 }
 
 /*
@@ -169,6 +188,7 @@ ext4_ext_find_extent(struct m_ext2fs *fs, struct inode *ip,
 	path->ep_depth = i;
 	path->ep_ext = NULL;
 	path->ep_index = NULL;
+	path->ep_is_sparse = 0;
 
 	ext4_ext_binsearch(ip, path, lbn);
 	return (path);
diff --git a/sys/fs/ext2fs/ext2_extents.h b/sys/fs/ext2fs/ext2_extents.h
index 94ded83..4ce16f3 100644
--- a/sys/fs/ext2fs/ext2_extents.h
+++ b/sys/fs/ext2fs/ext2_extents.h
@@ -84,7 +84,11 @@ struct ext4_extent_cache {
 struct ext4_extent_path {
 	uint16_t ep_depth;
 	struct buf *ep_bp;
-	struct ext4_extent *ep_ext;
+	int ep_is_sparse;
+	union {
+		struct ext4_extent ep_sparse_ext;
+		struct ext4_extent *ep_ext;
+	};
 	struct ext4_extent_index *ep_index;
 	struct ext4_extent_header *ep_header;
 };
diff --git a/sys/fs/ext2fs/ext2_vnops.c b/sys/fs/ext2fs/ext2_vnops.c
index 5b8990ee..bc239b8 100644
--- a/sys/fs/ext2fs/ext2_vnops.c
+++ b/sys/fs/ext2fs/ext2_vnops.c
@@ -1787,6 +1787,7 @@ ext2_ioctl(struct vop_ioctl_args *ap)
 static int
 ext4_ext_read(struct vop_read_args *ap)
 {
+	static unsigned char zeroes[EXT2_MAX_BLOCK_SIZE];
 	struct vnode *vp;
 	struct inode *ip;
 	struct uio *uio;
@@ -1831,11 +1832,15 @@ ext4_ext_read(struct vop_read_args *ap)
 		switch (cache_type) {
 		case EXT4_EXT_CACHE_NO:
 			ext4_ext_find_extent(fs, ip, lbn, &path);
-			ep = path.ep_ext;
+			if (path.ep_is_sparse)
+				ep = &path.ep_sparse_ext;
+			else
+				ep = path.ep_ext;
 			if (ep == NULL)
 				return (EIO);
 
-			ext4_ext_put_cache(ip, ep, EXT4_EXT_CACHE_IN);
+			ext4_ext_put_cache(ip, ep,
+			    path.ep_is_sparse ? EXT4_EXT_CACHE_GAP : EXT4_EXT_CACHE_IN);
 
 			newblk = lbn - ep->e_blk + (ep->e_start_lo |
 			    (daddr_t)ep->e_start_hi << 32);
@@ -1848,7 +1853,7 @@ ext4_ext_read(struct vop_read_args *ap)
 
 		case EXT4_EXT_CACHE_GAP:
 			/* block has not been allocated yet */
-			return (0);
+			break;
 
 		case EXT4_EXT_CACHE_IN:
 			newblk = lbn - nex.e_blk + (nex.e_start_lo |
@@ -1859,24 +1864,34 @@ ext4_ext_read(struct vop_read_args *ap)
 			panic("%s: invalid cache type", __func__);
 		}
 
-		error = bread(ip->i_devvp, fsbtodb(fs, newblk), size, NOCRED, &bp);
-		if (error) {
-			brelse(bp);
-			return (error);
-		}
+		if (cache_type == EXT4_EXT_CACHE_GAP ||
+		    (cache_type == EXT4_EXT_CACHE_NO && path.ep_is_sparse)) {
+			if (xfersize > sizeof(zeroes))
+				xfersize = sizeof(zeroes);
+			error = uiomove(zeroes, xfersize, uio);
+			if (error)
+				return (error);
+		} else {
+			error = bread(ip->i_devvp, fsbtodb(fs, newblk), size,
+			    NOCRED, &bp);
+			if (error) {
+				brelse(bp);
+				return (error);
+			}
 
-		size -= bp->b_resid;
-		if (size < xfersize) {
-			if (size == 0) {
-				bqrelse(bp);
-				break;
+			size -= bp->b_resid;
+			if (size < xfersize) {
+				if (size == 0) {
+					bqrelse(bp);
+					break;
+				}
+				xfersize = size;
 			}
-			xfersize = size;
+			error = uiomove(bp->b_data + blkoffset, xfersize, uio);
+			bqrelse(bp);
+			if (error)
+				return (error);
 		}
-		error = uiomove(bp->b_data + blkoffset, (int)xfersize, uio);
-		bqrelse(bp);
-		if (error)
-			return (error);
 	}
 
 	return (0);