[PATCH] JFS: Don't allocate extents that overlap existing extents

Modify xtSearch so that it returns the next allocated block when the
requested block is unmapped.  This can be used to make sure we don't
create a new extent that overlaps the next one.

Signed-off-by: Dave Kleikamp <shaggy@austin.ibm.com>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>
diff --git a/fs/jfs/inode.c b/fs/jfs/inode.c
index 6c04f5e..24a6891 100644
--- a/fs/jfs/inode.c
+++ b/fs/jfs/inode.c
@@ -178,7 +178,7 @@
 	xad_t xad;
 	s64 xaddr;
 	int xflag;
-	s32 xlen;
+	s32 xlen = max_blocks;
 
 	/*
 	 * Take appropriate lock on inode
@@ -190,7 +190,7 @@
 
 	if (((lblock64 << ip->i_sb->s_blocksize_bits) < ip->i_size) &&
 	    (!xtLookup(ip, lblock64, max_blocks, &xflag, &xaddr, &xlen, 0)) &&
-	    xlen) {
+	    xaddr) {
 		if (xflag & XAD_NOTRECORDED) {
 			if (!create)
 				/*
@@ -229,7 +229,7 @@
 #ifdef _JFS_4K
 	if ((rc = extHint(ip, lblock64 << ip->i_sb->s_blocksize_bits, &xad)))
 		goto unlock;
-	rc = extAlloc(ip, max_blocks, lblock64, &xad, FALSE);
+	rc = extAlloc(ip, xlen, lblock64, &xad, FALSE);
 	if (rc)
 		goto unlock;
 
diff --git a/fs/jfs/jfs_dtree.c b/fs/jfs/jfs_dtree.c
index 453bace..ac41f72 100644
--- a/fs/jfs/jfs_dtree.c
+++ b/fs/jfs/jfs_dtree.c
@@ -212,7 +212,7 @@
 	s32 xlen;
 
 	rc = xtLookup(inode, blkno, 1, &xflag, &xaddr, &xlen, 1);
-	if (rc || (xlen == 0))
+	if (rc || (xaddr == 0))
 		return NULL;
 
 	return read_metapage(inode, xaddr, PSIZE, 1);
@@ -231,7 +231,7 @@
 	s32 xlen;
 
 	rc = xtLookup(inode, blkno, 1, &xflag, &xaddr, &xlen, 1);
-	if (rc || (xlen == 0))
+	if (rc || (xaddr == 0))
 		return NULL;
 
 	return get_metapage(inode, xaddr, PSIZE, 1);
diff --git a/fs/jfs/jfs_xtree.c b/fs/jfs/jfs_xtree.c
index 11c58c5..2c1f311 100644
--- a/fs/jfs/jfs_xtree.c
+++ b/fs/jfs/jfs_xtree.c
@@ -111,8 +111,8 @@
 /*
  * forward references
  */
-static int xtSearch(struct inode *ip,
-		    s64 xoff, int *cmpp, struct btstack * btstack, int flag);
+static int xtSearch(struct inode *ip, s64 xoff, s64 *next, int *cmpp,
+		    struct btstack * btstack, int flag);
 
 static int xtSplitUp(tid_t tid,
 		     struct inode *ip,
@@ -159,11 +159,12 @@
 	xtpage_t *p;
 	int index;
 	xad_t *xad;
-	s64 size, xoff, xend;
+	s64 next, size, xoff, xend;
 	int xlen;
 	s64 xaddr;
 
-	*plen = 0;
+	*paddr = 0;
+	*plen = llen;
 
 	if (!no_check) {
 		/* is lookup offset beyond eof ? */
@@ -180,7 +181,7 @@
 	 * search for the xad entry covering the logical extent
 	 */
 //search:
-	if ((rc = xtSearch(ip, lstart, &cmp, &btstack, 0))) {
+	if ((rc = xtSearch(ip, lstart, &next, &cmp, &btstack, 0))) {
 		jfs_err("xtLookup: xtSearch returned %d", rc);
 		return rc;
 	}
@@ -198,8 +199,11 @@
 	 * lstart is a page start address,
 	 * i.e., lstart cannot start in a hole;
 	 */
-	if (cmp)
+	if (cmp) {
+		if (next)
+			*plen = min(next - lstart, llen);
 		goto out;
+	}
 
 	/*
 	 * lxd covered by xad
@@ -284,7 +288,7 @@
 	if (lstart >= size)
 		return 0;
 
-	if ((rc = xtSearch(ip, lstart, &cmp, &btstack, 0)))
+	if ((rc = xtSearch(ip, lstart, NULL, &cmp, &btstack, 0)))
 		return rc;
 
 	/*
@@ -488,6 +492,7 @@
  * parameters:
  *      ip      - file object;
  *      xoff    - extent offset;
+ *      nextp	- address of next extent (if any) for search miss
  *      cmpp    - comparison result:
  *      btstack - traverse stack;
  *      flag    - search process flag (XT_INSERT);
@@ -497,7 +502,7 @@
  *      *cmpp is set to result of comparison with the entry returned.
  *      the page containing the entry is pinned at exit.
  */
-static int xtSearch(struct inode *ip, s64 xoff,	/* offset of extent */
+static int xtSearch(struct inode *ip, s64 xoff,	s64 *nextp,
 		    int *cmpp, struct btstack * btstack, int flag)
 {
 	struct jfs_inode_info *jfs_ip = JFS_IP(ip);
@@ -511,6 +516,7 @@
 	struct btframe *btsp;
 	int nsplit = 0;		/* number of pages to split */
 	s64 t64;
+	s64 next = 0;
 
 	INCREMENT(xtStat.search);
 
@@ -579,6 +585,7 @@
 						 * previous and this entry
 						 */
 						*cmpp = 1;
+						next = t64;
 						goto out;
 					}
 
@@ -623,6 +630,9 @@
 			/* update sequential access heuristics */
 			jfs_ip->btindex = index;
 
+			if (nextp)
+				*nextp = next;
+
 			INCREMENT(xtStat.fastSearch);
 			return 0;
 		}
@@ -675,10 +685,11 @@
 
 					return 0;
 				}
-
 				/* search hit - internal page:
 				 * descend/search its child page
 				 */
+				if (index < p->header.nextindex - 1)
+					next = offsetXAD(&p->xad[index + 1]);
 				goto next;
 			}
 
@@ -694,6 +705,8 @@
 		 * base is the smallest index with key (Kj) greater than
 		 * search key (K) and may be zero or maxentry index.
 		 */
+		if (base < p->header.nextindex)
+			next = offsetXAD(&p->xad[base]);
 		/*
 		 * search miss - leaf page:
 		 *
@@ -727,6 +740,9 @@
 				jfs_ip->btorder = BT_RANDOM;
 			jfs_ip->btindex = base;
 
+			if (nextp)
+				*nextp = next;
+
 			return 0;
 		}
 
@@ -793,6 +809,7 @@
 	struct xtsplit split;	/* split information */
 	xad_t *xad;
 	int cmp;
+	s64 next;
 	struct tlock *tlck;
 	struct xtlock *xtlck;
 
@@ -806,7 +823,7 @@
 	 * n.b. xtSearch() may return index of maxentry of
 	 * the full page.
 	 */
-	if ((rc = xtSearch(ip, xoff, &cmp, &btstack, XT_INSERT)))
+	if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT)))
 		return rc;
 
 	/* retrieve search result */
@@ -814,7 +831,7 @@
 
 	/* This test must follow XT_GETSEARCH since mp must be valid if
 	 * we branch to out: */
-	if (cmp == 0) {
+	if ((cmp == 0) || (next && (xlen > next - xoff))) {
 		rc = -EEXIST;
 		goto out;
 	}
@@ -1626,7 +1643,7 @@
 	jfs_info("xtExtend: nxoff:0x%lx nxlen:0x%x", (ulong) xoff, xlen);
 
 	/* there must exist extent to be extended */
-	if ((rc = xtSearch(ip, xoff - 1, &cmp, &btstack, XT_INSERT)))
+	if ((rc = xtSearch(ip, xoff - 1, NULL, &cmp, &btstack, XT_INSERT)))
 		return rc;
 
 	/* retrieve search result */
@@ -1794,7 +1811,7 @@
 */
 
 	/* there must exist extent to be tailgated */
-	if ((rc = xtSearch(ip, xoff, &cmp, &btstack, XT_INSERT)))
+	if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, XT_INSERT)))
 		return rc;
 
 	/* retrieve search result */
@@ -1977,7 +1994,7 @@
 	nxlen = lengthXAD(nxad);
 	nxaddr = addressXAD(nxad);
 
-	if ((rc = xtSearch(ip, nxoff, &cmp, &btstack, XT_INSERT)))
+	if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT)))
 		return rc;
 
 	/* retrieve search result */
@@ -2291,7 +2308,7 @@
 	if (nextindex == le16_to_cpu(p->header.maxentry)) {
 		XT_PUTPAGE(mp);
 
-		if ((rc = xtSearch(ip, nxoff, &cmp, &btstack, XT_INSERT)))
+		if ((rc = xtSearch(ip, nxoff, NULL, &cmp, &btstack, XT_INSERT)))
 			return rc;
 
 		/* retrieve search result */
@@ -2438,6 +2455,7 @@
 	int nsplit, nblocks, xlen;
 	struct pxdlist pxdlist;
 	pxd_t *pxd;
+	s64 next;
 
 	xaddr = *xaddrp;
 	xlen = *xlenp;
@@ -2452,7 +2470,7 @@
 	 * n.b. xtSearch() may return index of maxentry of
 	 * the full page.
 	 */
-	if ((rc = xtSearch(ip, xoff, &cmp, &btstack, XT_INSERT)))
+	if ((rc = xtSearch(ip, xoff, &next, &cmp, &btstack, XT_INSERT)))
 		return rc;
 
 	/* retrieve search result */
@@ -2462,6 +2480,9 @@
 		rc = -EEXIST;
 		goto out;
 	}
+
+	if (next)
+		xlen = min(xlen, (int)(next - xoff));
 //insert:
 	/*
 	 *      insert entry for new extent
@@ -2600,7 +2621,7 @@
 	/*
 	 * find the matching entry; xtSearch() pins the page
 	 */
-	if ((rc = xtSearch(ip, xoff, &cmp, &btstack, 0)))
+	if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0)))
 		return rc;
 
 	XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);
@@ -2852,7 +2873,7 @@
 	 */
 	if (xtype == DATAEXT) {
 		/* search in leaf entry */
-		rc = xtSearch(ip, xoff, &cmp, &btstack, 0);
+		rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0);
 		if (rc)
 			return rc;
 
@@ -2958,7 +2979,7 @@
 		}
 
 		/* get back parent page */
-		if ((rc = xtSearch(ip, xoff, &cmp, &btstack, 0)))
+		if ((rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0)))
 			return rc;
 
 		XT_GETSEARCH(ip, btstack.top, bn, pmp, pp, index);
@@ -3991,7 +4012,7 @@
 
 	if (committed_size) {
 		xoff = (committed_size >> JFS_SBI(ip->i_sb)->l2bsize) - 1;
-		rc = xtSearch(ip, xoff, &cmp, &btstack, 0);
+		rc = xtSearch(ip, xoff, NULL, &cmp, &btstack, 0);
 		if (rc)
 			return rc;