Prototype to speed up searching for a free inode.
Don't search too far - abort is outside a certain radius
and simply does a linear search for the first free inode.

In AGs with a million inodes this can speed up allocation
speed by 3-4x.

Signed-off-by: Dave Chinner <dgc@sgi.com>
---
 fs/xfs/xfs_ag.h     |    9 ++++
 fs/xfs/xfs_ialloc.c |   99 +++++++++++++++++++++++++++++++++++++++++++++-------
 2 files changed, 95 insertions(+), 13 deletions(-)

Index: 2.6.x-xfs-new/fs/xfs/xfs_ag.h
===================================================================
--- 2.6.x-xfs-new.orig/fs/xfs/xfs_ag.h	2008-05-16 22:11:53.644463437 +1000
+++ 2.6.x-xfs-new/fs/xfs/xfs_ag.h	2008-05-16 22:33:47.697937989 +1000
@@ -201,6 +201,15 @@ typedef struct xfs_perag
 	int		pag_ici_init;	/* incore inode cache initialised */
 	spinlock_t	pag_ici_lock;	/* incore inode lock */
 	struct radix_tree_root pag_ici_root;	/* incore inode cache root */
+
+	/*
+	 * inode allocation search lookup optimisation.
+	 * If the pagino matches, the search for new inodes
+	 * doesn't need to search the near ones again straight away
+	 */
+	xfs_agino_t	pagl_pagino;
+	xfs_agino_t	pagl_leftrec;
+	xfs_agino_t	pagl_rightrec;
 } xfs_perag_t;
 
 /*
Index: 2.6.x-xfs-new/fs/xfs/xfs_ialloc.c
===================================================================
--- 2.6.x-xfs-new.orig/fs/xfs/xfs_ialloc.c	2008-05-08 10:05:16.000000000 +1000
+++ 2.6.x-xfs-new/fs/xfs/xfs_ialloc.c	2008-05-16 22:33:47.717935407 +1000
@@ -676,6 +676,7 @@ nextag:
 	 */
 	agno = tagno;
 	*IO_agbp = NULL;
+restart_pagno:
 	cur = xfs_btree_init_cursor(mp, tp, agbp, be32_to_cpu(agi->agi_seqno),
 				    XFS_BTNUM_INO, (xfs_inode_t *)0, 0);
 	/*
@@ -727,11 +728,14 @@ nextag:
 		else {
 			int	doneleft;	/* done, to the left */
 			int	doneright;	/* done, to the right */
+			int	searchdistance = 10;
+			int	found = 0;
 
 			if (error)
 				goto error0;
 			ASSERT(i == 1);
 			ASSERT(j == 1);
+
 			/*
 			 * Duplicate the cursor, search left & right
 			 * simultaneously.
@@ -739,11 +743,35 @@ nextag:
 			if ((error = xfs_btree_dup_cursor(cur, &tcur)))
 				goto error0;
 			/*
-			 * Search left with tcur, back up 1 record.
+			 * skip to last blocks looked up if same parent inode
 			 */
-			if ((error = xfs_inobt_decrement(tcur, 0, &i)))
-				goto error1;
-			doneleft = !i;
+			if (!((mp->m_perag[agno].pagl_pagino == NULLAGINO) ||
+			      (mp->m_perag[agno].pagl_leftrec == NULLAGINO) ||
+			      (mp->m_perag[agno].pagl_rightrec == NULLAGINO)) &&
+			    (mp->m_perag[agno].pagl_pagino == pagino)) {
+				error = xfs_inobt_lookup_eq(tcur, mp->m_perag[agno].pagl_leftrec, 0, 0, &i);
+				doneleft = !i || error;
+				if (error)
+					printk("xfs_inobt_lookup_eq left %x failed %d %d\n", mp->m_perag[agno].pagl_leftrec, error, i);
+				if (!error)
+					error = xfs_inobt_lookup_eq(cur, mp->m_perag[agno].pagl_rightrec, 0, 0, &i);
+				doneright = !i || error;
+				if (error)
+					printk("xfs_inobt_lookup_eq right %x failed %d %d\n", mp->m_perag[agno].pagl_rightrec, error, i);
+			} else {
+				/*
+				 * Search left with tcur, back up 1 record.
+				 */
+				if ((error = xfs_inobt_decrement(tcur, 0, &i)))
+					goto error1;
+				doneleft = !i;
+				/*
+				 * Search right with cur, go forward 1 record.
+				 */
+				if ((error = xfs_inobt_increment(cur, 0, &i)))
+					goto error1;
+				doneright = !i;
+			}
 			if (!doneleft) {
 				if ((error = xfs_inobt_get_rec(tcur,
 						&trec.ir_startino,
@@ -752,12 +780,6 @@ nextag:
 					goto error1;
 				XFS_WANT_CORRUPTED_GOTO(i == 1, error1);
 			}
-			/*
-			 * Search right with cur, go forward 1 record.
-			 */
-			if ((error = xfs_inobt_increment(cur, 0, &i)))
-				goto error1;
-			doneright = !i;
 			if (!doneright) {
 				if ((error = xfs_inobt_get_rec(cur,
 						&rec.ir_startino,
@@ -766,11 +788,21 @@ nextag:
 					goto error1;
 				XFS_WANT_CORRUPTED_GOTO(i == 1, error1);
 			}
+			/* nothing free? */
+			if (doneleft && doneright) {
+				mp->m_perag[agno].pagl_pagino = NULLAGINO;
+				mp->m_perag[agno].pagl_leftrec = NULLAGINO;
+				mp->m_perag[agno].pagl_rightrec = NULLAGINO;
+				xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
+				xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
+				goto restart_pagno;
+			}
+
 			/*
 			 * Loop until we find the closest inode chunk
 			 * with a free one.
 			 */
-			while (!doneleft || !doneright) {
+			while ((!doneleft || !doneright) && --searchdistance) {
 				int	useleft;  /* using left inode
 						     chunk this time */
 
@@ -798,6 +830,10 @@ nextag:
 					xfs_btree_del_cursor(cur,
 						XFS_BTREE_NOERROR);
 					cur = tcur;
+					mp->m_perag[agno].pagl_leftrec = trec.ir_startino;
+					mp->m_perag[agno].pagl_rightrec = rec.ir_startino;
+					mp->m_perag[agno].pagl_pagino = pagino;
+					found = 1;
 					break;
 				}
 				/*
@@ -810,6 +846,10 @@ nextag:
 					 */
 					xfs_btree_del_cursor(tcur,
 						XFS_BTREE_NOERROR);
+					mp->m_perag[agno].pagl_leftrec = trec.ir_startino;
+					mp->m_perag[agno].pagl_rightrec = rec.ir_startino;
+					mp->m_perag[agno].pagl_pagino = pagino;
+					found = 1;
 					break;
 				}
 				/*
@@ -853,6 +893,33 @@ nextag:
 					}
 				}
 			}
+			if (!found) {
+				if (!searchdistance) {
+					/*
+					 * not in range - save last search
+					 * location and allocate a new inode
+					 */
+					mp->m_perag[agno].pagl_leftrec = trec.ir_startino;
+					mp->m_perag[agno].pagl_rightrec = rec.ir_startino;
+					mp->m_perag[agno].pagl_pagino = pagino;
+					goto newino;
+				}
+				/*
+				 * we've reached the end of the btree. because
+				 * we are only searching a small chunk of the
+				 * btree each search, there is obviously free
+				 * inodes closer to the parent inode than we
+				 * are now. restart the search again.
+				 */
+				mp->m_perag[agno].pagl_pagino = NULLAGINO;
+				mp->m_perag[agno].pagl_leftrec = NULLAGINO;
+				mp->m_perag[agno].pagl_rightrec = NULLAGINO;
+				xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
+				xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
+				goto restart_pagno;
+			}
+			//printk("dl %d dr %d sd %d fd %d\n", doneleft,
+			//		doneright, searchdistance, found);
 			ASSERT(!doneleft || !doneright);
 		}
 	}
@@ -860,7 +927,9 @@ nextag:
 	 * In a different a.g. from the parent.
 	 * See if the most recently allocated block has any free.
 	 */
-	else if (be32_to_cpu(agi->agi_newino) != NULLAGINO) {
+	else {
+newino:
+	if (be32_to_cpu(agi->agi_newino) != NULLAGINO) {
 		if ((error = xfs_inobt_lookup_eq(cur,
 				be32_to_cpu(agi->agi_newino), 0, 0, &i)))
 			goto error0;
@@ -878,6 +947,7 @@ nextag:
 		 * None left in the last group, search the whole a.g.
 		 */
 		else {
+search_ag:
 			if (error)
 				goto error0;
 			if ((error = xfs_inobt_lookup_ge(cur, 0, 0, 0, &i)))
@@ -897,7 +967,10 @@ nextag:
 				XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
 			}
 		}
-	}
+	} else {
+		printk("searching ag %d\n", agno);
+		goto search_ag;
+	} }
 	offset = XFS_IALLOC_FIND_FREE(&rec.ir_free);
 	ASSERT(offset >= 0);
 	ASSERT(offset < XFS_INODES_PER_CHUNK);
