Skip to contentSkip to conversation

xfs: reduce stack usage in xfs_bmap_btalloc()

PATCH In review Denys Vlasenko 4 participants 8 messages Apr 26, 2008 – Apr 28, 2008 XFS filesystem

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 xfs: reduce stack usage in xfs_bmap_btalloc()

Hi David,

This patch reduces xfs_bmap_btalloc() stack usage by 50 bytes by moving part of its body into a helper function.

This results in some variables not taking stack space in xfs_bmap_btalloc() anymore.

The helper itself does not call anything stack-deep. Stack-deep call to xfs_alloc_vextent() happen in xfs_bmap_btalloc(), as before.

Compile tested only.

--
vda

fs/xfs/xfs_bmap.c +46 -17
diff -urpN linux-2.6-xfs1/fs/xfs/xfs_bmap.c linux-2.6-xfs1.stk1/fs/xfs/xfs_bmap.c
@@ -2648,26 +2648,18 @@ xfs_bmap_rtalloc(
 }
 
 STATIC int
-xfs_bmap_btalloc(
-	xfs_bmalloca_t	*ap)		/* bmap alloc argument struct */
+xfs_bmap_btalloc_helper(
+	xfs_bmalloca_t	*ap,		/* bmap alloc argument struct */
+	xfs_alloc_arg_t	*argsp,
+	xfs_extlen_t	*blenp)
 {
+#define args (*argsp)
+#define blen (*blenp)
 	xfs_mount_t	*mp;		/* mount point structure */
-	xfs_alloctype_t	atype = 0;	/* type for allocation routines */
 	xfs_extlen_t	align;		/* minimum allocation alignment */
 	xfs_agnumber_t	ag;
 	xfs_agnumber_t	fb_agno;	/* ag number of ap->firstblock */
-	xfs_agnumber_t	startag;
-	xfs_alloc_arg_t	args;
-	xfs_extlen_t	blen;
-	xfs_extlen_t	delta;
-	xfs_extlen_t	longest;
-	xfs_extlen_t	need;
-	xfs_extlen_t	nextminlen = 0;
-	xfs_perag_t	*pag;
 	int		nullfb;		/* true if ap->firstblock isn't set */
-	int		isaligned;
-	int		notinit;
-	int		tryagain;
 	int		error;
 
 	mp = ap->ip->i_mount;
@@ -2705,7 +2697,6 @@ xfs_bmap_btalloc(
 	/*
 	 * Normal allocation, done through xfs_alloc_vextent.
 	 */
-	tryagain = isaligned = 0;
 	args.tp = ap->tp;
 	args.mp = mp;
 	args.fsbno = ap->rval;
@@ -2713,6 +2704,9 @@ xfs_bmap_btalloc(
 	args.firstblock = ap->firstblock;
 	blen = 0;
 	if (nullfb) {
+		xfs_agnumber_t	startag;
+		int		notinit;
+
 		if (ap->userdata && xfs_inode_is_filestream(ap->ip))
 			args.type = XFS_ALLOCTYPE_NEAR_BNO;
 		else
@@ -2732,6 +2726,8 @@ xfs_bmap_btalloc(
 		notinit = 0;
 		down_read(&mp->m_peraglock);
 		while (blen < ap->alen) {
+			xfs_perag_t	*pag;
+
 			pag = &mp->m_perag[ag];
 			if (!pag->pagf_init &&
 			    (error = xfs_alloc_pagf_init(mp, args.tp,
@@ -2743,6 +2739,10 @@ xfs_bmap_btalloc(
 			 * See xfs_alloc_fix_freelist...
 			 */
 			if (pag->pagf_init) {
+				xfs_extlen_t	need;
+				xfs_extlen_t	delta;
+				xfs_extlen_t	longest;
+
 				need = XFS_MIN_FREELIST_PAG(pag, mp);
 				delta = need > pag->pagf_flcount ?
 					need - pag->pagf_flcount : 0;
@@ -2838,6 +2838,33 @@ xfs_bmap_btalloc(
 		if ((args.mod = (xfs_extlen_t)(do_mod(ap->off, args.prod))))
 			args.mod = (xfs_extlen_t)(args.prod - args.mod);
 	}
+
+	return 0; /* no error */
+#undef args
+#undef blen
+}
+
+STATIC int
+xfs_bmap_btalloc(
+	xfs_bmalloca_t	*ap)		/* bmap alloc argument struct */
+{
+	xfs_mount_t	*mp;		/* mount point structure */
+	xfs_alloctype_t	atype;		/* type for allocation routines */
+	xfs_alloc_arg_t	args;
+	xfs_extlen_t	blen;
+	xfs_extlen_t	nextminlen;
+	int		nullfb;		/* true if ap->firstblock isn't set */
+	int		isaligned;
+	int		tryagain;
+	int		error;
+
+	error = xfs_bmap_btalloc_helper(ap, &args, &blen);
+	if (error)
+		return error;
+
+	mp = ap->ip->i_mount;
+	nullfb = ap->firstblock == NULLFSBLOCK;
+
 	/*
 	 * If we are not low on available data blocks, and the
 	 * underlying logical volume manager is a stripe, and
@@ -2847,10 +2874,13 @@ xfs_bmap_btalloc(
 	 * is >= the stripe unit and the allocation offset is
 	 * at the end of file.
 	 */
+	atype = 0;
+	nextminlen = 0;
+	tryagain = isaligned = 0;
 	if (!ap->low && ap->aeof) {
+		atype = args.type;
 		if (!ap->off) {
 			args.alignment = mp->m_dalign;
-			atype = args.type;
 			isaligned = 1;
 			/*
 			 * Adjust for alignment
@@ -2864,7 +2894,6 @@ xfs_bmap_btalloc(
 			 * If it fails then do a near or start bno
 			 * allocation with alignment turned on.
 			 */
-			atype = args.type;
 			tryagain = 1;
 			args.type = XFS_ALLOCTYPE_THIS_BNO;
 			args.alignment = 1;
#1 lore raw
Quoted 12 lines · Denys Vlasenko

Hi David,

This patch reduces xfs_bmap_btalloc() stack usage by 50 bytes by moving part of its body into a helper function.

This results in some variables not taking stack space in xfs_bmap_btalloc() anymore.

The helper itself does not call anything stack-deep. Stack-deep call to xfs_alloc_vextent() happen in xfs_bmap_btalloc(), as before.

Quoted 6 lines

Compile tested only.

--
vda

Looks like a very good approach, it pushes a lot of large local vars off into the helper.

There is one build-time problem if DEBUG is turned on:

        if (args.fsbno != NULLFSBLOCK) {
                ap->firstblock = ap->rval = args.fsbno;
                ASSERT(nullfb || fb_agno == args.agno ||
                       (ap->low && fb_agno < args.agno));

in xfs_bmap_btalloc, which no longer has an fb_agno variable which the ASSERT macro uses.

Thanks,

-Eric

#3 lore raw
In reply to Denys Vlasenko
Quoted 5 lines · Denys Vlasenko

Hi David,

This patch reduces xfs_bmap_btalloc() stack usage by 50 bytes by moving part of its body into a helper function.

Quoted 8 lines

This results in some variables not taking stack space in xfs_bmap_btalloc() anymore.

The helper itself does not call anything stack-deep. Stack-deep call to xfs_alloc_vextent() happen in xfs_bmap_btalloc(), as before.

Compile tested only.

I think this is a good idea, although I'd rather split the function at a local boundary. The patch below (which passes xfsqa) does that by splitting out the handling of the most complicated nullfb case out. It probably won't help reducing stack useage as much as yours, but it helps beeing able to read the code a little better.

fs/xfs/xfs_bmap.c +143 -108
Index: linux-2.6-xfs/fs/xfs/xfs_bmap.c
===================================================================
@@ -2646,6 +2646,144 @@ xfs_bmap_rtalloc(
 	return 0;
 }
 
+STATIC void
+xfs_bmap_btalloc_fix_blen(
+	xfs_mount_t		*mp,
+	xfs_perag_t		*pag,
+	xfs_extlen_t		*blen)
+{
+	xfs_extlen_t		need, delta, longest;
+
+	need = XFS_MIN_FREELIST_PAG(pag, mp);
+	if (need > pag->pagf_flcount)
+		delta = need - pag->pagf_flcount;
+	else
+		delta = 0;
+
+	if (pag->pagf_longest > delta)
+		longest = pag->pagf_longest - delta;
+	else
+		longest = (pag->pagf_flcount > 0 ||
+			   pag->pagf_longest > 0);
+
+	if (*blen < longest)
+		*blen = longest;
+}
+
+STATIC int
+xfs_bmap_btalloc_nullfb(
+	xfs_bmalloca_t		*ap,
+	xfs_alloc_arg_t		*args,
+	xfs_extlen_t		*blen)
+{
+	xfs_mount_t		*mp = ap->ip->i_mount;
+	xfs_agnumber_t		ag, startag;
+	int			notinit = 0, error;
+
+	if (ap->userdata && xfs_inode_is_filestream(ap->ip))
+		args->type = XFS_ALLOCTYPE_NEAR_BNO;
+	else
+		args->type = XFS_ALLOCTYPE_START_BNO;
+	args->total = ap->total;
+
+	/*
+	 * Search for an allocation group with a single extent
+	 * large enough for the request.
+	 *
+	 * If one isn't found, then adjust the minimum allocation
+	 * size to the largest space found.
+	 */
+	startag = XFS_FSB_TO_AGNO(mp, args->fsbno);
+	if (startag == NULLAGNUMBER)
+		startag = 0;
+
+	ag = startag;
+	down_read(&mp->m_peraglock);
+	while (*blen < ap->alen) {
+		xfs_perag_t	*pag = &mp->m_perag[ag];
+
+		if (!pag->pagf_init) {
+			error = xfs_alloc_pagf_init(mp, args->tp, ag,
+			    			    XFS_ALLOC_FLAG_TRYLOCK);
+			if (error)
+				goto out_unlock;
+		}
+
+		/*
+		 * See xfs_alloc_fix_freelist...
+		 */
+		if (pag->pagf_init)
+			xfs_bmap_btalloc_fix_blen(mp, pag, blen);
+		else
+			notinit = 1;
+
+		if (xfs_inode_is_filestream(ap->ip)) {
+			if (*blen >= ap->alen)
+				break;
+
+			if (ap->userdata) {
+				/*
+				 * If startag is an invalid AG, we've come
+				 * here once before and xfs_filestream_new_ag
+				 * picked the best currently available.
+				 *
+				 * Don't continue looping, since we could
+				 * loop forever.
+				 */
+				if (startag == NULLAGNUMBER)
+					break;
+
+				error = xfs_filestream_new_ag(ap, &ag);
+				if (error)
+					goto out_unlock;
+
+				/* loop again to set 'blen'*/
+				startag = NULLAGNUMBER;
+				continue;
+			}
+		}
+		if (++ag == mp->m_sb.sb_agcount)
+			ag = 0;
+		if (ag == startag)
+			break;
+	}
+	up_read(&mp->m_peraglock);
+
+	/*
+	 * Since the above loop did a BUF_TRYLOCK, it is
+	 * possible that there is space for this request.
+	 */
+	if (notinit || *blen < ap->minlen)
+		args->minlen = ap->minlen;
+
+	/*
+	 * If the best seen length is less than the request
+	 * length, use the best as the minimum.
+	 */
+	else if (*blen < ap->alen)
+		args->minlen = *blen;
+
+	/*
+	 * Otherwise we've seen an extent as big as alen,
+	 * use that as the minimum.
+	 */
+	else
+		args->minlen = ap->alen;
+
+	/*
+	 * Set the failure fallback case to look in the selected AG as
+	 * the stream may have moved.
+	 */
+	if (xfs_inode_is_filestream(ap->ip))
+		ap->rval = args->fsbno = XFS_AGB_TO_FSB(mp, ag, 0);
+
+	return 0;
+
+ out_unlock:
+	up_read(&mp->m_peraglock);
+	return error;
+}
+
 STATIC int
 xfs_bmap_btalloc(
 	xfs_bmalloca_t	*ap)		/* bmap alloc argument struct */
@@ -2653,19 +2791,12 @@ xfs_bmap_btalloc(
 	xfs_mount_t	*mp;		/* mount point structure */
 	xfs_alloctype_t	atype = 0;	/* type for allocation routines */
 	xfs_extlen_t	align;		/* minimum allocation alignment */
-	xfs_agnumber_t	ag;
 	xfs_agnumber_t	fb_agno;	/* ag number of ap->firstblock */
-	xfs_agnumber_t	startag;
 	xfs_alloc_arg_t	args;
 	xfs_extlen_t	blen;
-	xfs_extlen_t	delta;
-	xfs_extlen_t	longest;
-	xfs_extlen_t	need;
 	xfs_extlen_t	nextminlen = 0;
-	xfs_perag_t	*pag;
 	int		nullfb;		/* true if ap->firstblock isn't set */
 	int		isaligned;
-	int		notinit;
 	int		tryagain;
 	int		error;
 
@@ -2682,6 +2813,8 @@ xfs_bmap_btalloc(
 	fb_agno = nullfb ? NULLAGNUMBER : XFS_FSB_TO_AGNO(mp, ap->firstblock);
 	if (nullfb) {
 		if (ap->userdata && xfs_inode_is_filestream(ap->ip)) {
+			xfs_agnumber_t	ag;
+
 			ag = xfs_filestream_lookup_ag(ap->ip);
 			ag = (ag != NULLAGNUMBER) ? ag : 0;
 			ap->rval = XFS_AGB_TO_FSB(mp, ag, 0);
@@ -2712,107 +2845,9 @@ xfs_bmap_btalloc(
 	args.firstblock = ap->firstblock;
 	blen = 0;
 	if (nullfb) {
-		if (ap->userdata && xfs_inode_is_filestream(ap->ip))
-			args.type = XFS_ALLOCTYPE_NEAR_BNO;
-		else
-			args.type = XFS_ALLOCTYPE_START_BNO;
-		args.total = ap->total;
-
-		/*
-		 * Search for an allocation group with a single extent
-		 * large enough for the request.
-		 *
-		 * If one isn't found, then adjust the minimum allocation
-		 * size to the largest space found.
-		 */
-		startag = ag = XFS_FSB_TO_AGNO(mp, args.fsbno);
-		if (startag == NULLAGNUMBER)
-			startag = ag = 0;
-		notinit = 0;
-		down_read(&mp->m_peraglock);
-		while (blen < ap->alen) {
-			pag = &mp->m_perag[ag];
-			if (!pag->pagf_init &&
-			    (error = xfs_alloc_pagf_init(mp, args.tp,
-				    ag, XFS_ALLOC_FLAG_TRYLOCK))) {
-				up_read(&mp->m_peraglock);
-				return error;
-			}
-			/*
-			 * See xfs_alloc_fix_freelist...
-			 */
-			if (pag->pagf_init) {
-				need = XFS_MIN_FREELIST_PAG(pag, mp);
-				delta = need > pag->pagf_flcount ?
-					need - pag->pagf_flcount : 0;
-				longest = (pag->pagf_longest > delta) ?
-					(pag->pagf_longest - delta) :
-					(pag->pagf_flcount > 0 ||
-					 pag->pagf_longest > 0);
-				if (blen < longest)
-					blen = longest;
-			} else
-				notinit = 1;
-
-			if (xfs_inode_is_filestream(ap->ip)) {
-				if (blen >= ap->alen)
-					break;
-
-				if (ap->userdata) {
-					/*
-					 * If startag is an invalid AG, we've
-					 * come here once before and
-					 * xfs_filestream_new_ag picked the
-					 * best currently available.
-					 *
-					 * Don't continue looping, since we
-					 * could loop forever.
-					 */
-					if (startag == NULLAGNUMBER)
-						break;
-
-					error = xfs_filestream_new_ag(ap, &ag);
-					if (error) {
-						up_read(&mp->m_peraglock);
-						return error;
-					}
-
-					/* loop again to set 'blen'*/
-					startag = NULLAGNUMBER;
-					continue;
-				}
-			}
-			if (++ag == mp->m_sb.sb_agcount)
-				ag = 0;
-			if (ag == startag)
-				break;
-		}
-		up_read(&mp->m_peraglock);
-		/*
-		 * Since the above loop did a BUF_TRYLOCK, it is
-		 * possible that there is space for this request.
-		 */
-		if (notinit || blen < ap->minlen)
-			args.minlen = ap->minlen;
-		/*
-		 * If the best seen length is less than the request
-		 * length, use the best as the minimum.
-		 */
-		else if (blen < ap->alen)
-			args.minlen = blen;
-		/*
-		 * Otherwise we've seen an extent as big as alen,
-		 * use that as the minimum.
-		 */
-		else
-			args.minlen = ap->alen;
-
-		/*
-		 * set the failure fallback case to look in the selected
-		 * AG as the stream may have moved.
-		 */
-		if (xfs_inode_is_filestream(ap->ip))
-			ap->rval = args.fsbno = XFS_AGB_TO_FSB(mp, ag, 0);
+		error = xfs_bmap_btalloc_nullfb(ap, &args, &blen);
+		if (error)
+			return error;
 	} else if (ap->low) {
 		if (xfs_inode_is_filestream(ap->ip))
 			args.type = XFS_ALLOCTYPE_FIRST_AG;
#2 lore raw
In reply to Eric Sandeen
Quoted 19 lines · Eric Sandeen
Quoted 6 lines

This patch reduces xfs_bmap_btalloc() stack usage by 50 bytes by moving part of its body into a helper function.

This results in some variables not taking stack space in xfs_bmap_btalloc() anymore.

Quoted 7 lines

The helper itself does not call anything stack-deep. Stack-deep call to xfs_alloc_vextent() happen in xfs_bmap_btalloc(), as before.

Compile tested only.

Looks like a very good approach, it pushes a lot of large local vars off into the helper.

There is one build-time problem if DEBUG is turned on:

Quoted 7 lines
        if (args.fsbno != NULLFSBLOCK) {
                ap->firstblock = ap->rval = args.fsbno;
                ASSERT(nullfb || fb_agno == args.agno ||
                       (ap->low && fb_agno < args.agno));

in xfs_bmap_btalloc, which no longer has an fb_agno variable which the ASSERT macro uses.

Do you want me to rework and resend the patch?
--
vda

#4 lore raw
In reply to Christoph Hellwig
Quoted 6 lines · Christoph Hellwig
Quoted 5 lines · Denys Vlasenko

Hi David,

This patch reduces xfs_bmap_btalloc() stack usage by 50 bytes by moving part of its body into a helper function.

Quoted 8 lines
Quoted 2 lines

This results in some variables not taking stack space in xfs_bmap_btalloc() anymore.

I think this is a good idea, although I'd rather split the function at a local boundary. The patch below (which passes xfsqa) does that by splitting out the handling of the most complicated nullfb case out. It probably won't help reducing stack useage as much as yours, but it helps beeing able to read the code a little better.

It saves only 16 bytes of stack.
--
vda

#5 lore raw
In reply to Denys Vlasenko
Quoted 4 lines · Denys Vlasenko

Hi David,

This patch reduces xfs_bmap_btalloc() stack usage by 50 bytes by moving part of its body into a helper function.

Can you please attach your patches inline, Denys (see Documentation/SubmittingPatches)?

Quoted 6 lines

This results in some variables not taking stack space in xfs_bmap_btalloc() anymore.

The helper itself does not call anything stack-deep. Stack-deep call to xfs_alloc_vextent() happen in xfs_bmap_btalloc(), as before.

I have a set of patches that introduces new functionality into the allocator (dynamic allocation policies) that reduces xfs_bmap_btalloc() function by 36 bytes (just by chance, I didn't design it for this purpose). It breaks it down on functional boundaries like Christoph's patch. I'm going to revist that patch w.r.t both these patches and see what falls out the bottom...

Cheers,

Dave.

Signature · 3 lines
Dave Chinner
Principal Engineer
SGI Australian Software Group
#6 lore raw
Quoted 8 lines · David Chinner
Quoted 4 lines · Denys Vlasenko

Hi David,

This patch reduces xfs_bmap_btalloc() stack usage by 50 bytes by moving part of its body into a helper function.

Can you please attach your patches inline, Denys (see Documentation/SubmittingPatches)?

I can, but Kmail is notorious for mangling them :(

Is it ok if I will paste them inline AND attach them too, so that you get guaranteed-nonmangled one in attachment?

Quoted 6 lines

I have a set of patches that introduces new functionality into the allocator (dynamic allocation policies) that reduces xfs_bmap_btalloc() function by 36 bytes (just by chance, I didn't design it for this purpose). It breaks it down on functional boundaries like Christoph's patch. I'm going to revist that patch w.r.t both these patches and see what falls out the bottom...

Nice to know that.

Can you point me to svn/CVS/git/whatever which holds latest xfs devel tree?
--
vda

#7 lore raw
In reply to David Chinner
Quoted 16 lines · David Chinner
Quoted 4 lines · Denys Vlasenko

Hi David,

This patch reduces xfs_bmap_btalloc() stack usage by 50 bytes by moving part of its body into a helper function.

Can you please attach your patches inline, Denys (see Documentation/SubmittingPatches)?

Quoted 6 lines

This results in some variables not taking stack space in xfs_bmap_btalloc() anymore.

The helper itself does not call anything stack-deep. Stack-deep call to xfs_alloc_vextent() happen in xfs_bmap_btalloc(), as before.

Quoted 6 lines

I have a set of patches that introduces new functionality into the allocator (dynamic allocation policies) that reduces xfs_bmap_btalloc() function by 36 bytes (just by chance, I didn't design it for this purpose). It breaks it down on functional boundaries like Christoph's patch. I'm going to revist that patch w.r.t both these patches and see what falls out the bottom...

44 bytes saved in xfs_bmap_btalloc with the same factoring as Christoph's patch being done. Given that most of this is now the struct xfs_alloc_arg, I don't think this will be reduced a whole lot more. I think I might be able to kill the tryagain and isaligned variables as well which will save another 8 bytes, but I'll leave that for later....

Good progress, folks.

Cheers,

Dave.

Signature · 3 lines
Dave Chinner
Principal Engineer
SGI Australian Software Group