[PATCH] Replace XFS bit functions with Linux functions

[PATCH] Replace XFS bit functions with Linux functions

[Andi Kleen]

XFS had some own functions to find high and low bits.

This patch replaces them with a call to the respective Linux functions.
The semantics of the Linux functions differ a little, but i checked
all call sites that they can deal with that. I think all callers 
are ok; but i added a few more asserts for the 0 case (where Linux
and old XFS differ) just to make it easy to detect mistakes.

The resulting xfs.ko is about 500 bytes smaller on x86-64

This is similar to the patch Eric sent some days ago, but does
it more efficiently imho. It replaces his patch.

I wasn't able to do a full XFS QA run over this unfortunately; but did careful
review.

Signed-off-by: Andi Kleen <ak@suse.de>

Index: linux-2.6.23-rc8-misc/fs/xfs/xfs_bit.c
===================================================================
--- linux-2.6.23-rc8-misc.orig/fs/xfs/xfs_bit.c
+++ linux-2.6.23-rc8-misc/fs/xfs/xfs_bit.c
@@ -22,112 +22,9 @@
 #include "xfs_buf_item.h"
 
 /*
- * XFS bit manipulation routines, used in non-realtime code.
+ * XFS bit manipulation routines
  */
 
-#ifndef HAVE_ARCH_HIGHBIT
-/*
- * Index of high bit number in byte, -1 for none set, 0..7 otherwise.
- */
-static const char xfs_highbit[256] = {
-       -1, 0, 1, 1, 2, 2, 2, 2,			/* 00 .. 07 */
-	3, 3, 3, 3, 3, 3, 3, 3,			/* 08 .. 0f */
-	4, 4, 4, 4, 4, 4, 4, 4,			/* 10 .. 17 */
-	4, 4, 4, 4, 4, 4, 4, 4,			/* 18 .. 1f */
-	5, 5, 5, 5, 5, 5, 5, 5,			/* 20 .. 27 */
-	5, 5, 5, 5, 5, 5, 5, 5,			/* 28 .. 2f */
-	5, 5, 5, 5, 5, 5, 5, 5,			/* 30 .. 37 */
-	5, 5, 5, 5, 5, 5, 5, 5,			/* 38 .. 3f */
-	6, 6, 6, 6, 6, 6, 6, 6,			/* 40 .. 47 */
-	6, 6, 6, 6, 6, 6, 6, 6,			/* 48 .. 4f */
-	6, 6, 6, 6, 6, 6, 6, 6,			/* 50 .. 57 */
-	6, 6, 6, 6, 6, 6, 6, 6,			/* 58 .. 5f */
-	6, 6, 6, 6, 6, 6, 6, 6,			/* 60 .. 67 */
-	6, 6, 6, 6, 6, 6, 6, 6,			/* 68 .. 6f */
-	6, 6, 6, 6, 6, 6, 6, 6,			/* 70 .. 77 */
-	6, 6, 6, 6, 6, 6, 6, 6,			/* 78 .. 7f */
-	7, 7, 7, 7, 7, 7, 7, 7,			/* 80 .. 87 */
-	7, 7, 7, 7, 7, 7, 7, 7,			/* 88 .. 8f */
-	7, 7, 7, 7, 7, 7, 7, 7,			/* 90 .. 97 */
-	7, 7, 7, 7, 7, 7, 7, 7,			/* 98 .. 9f */
-	7, 7, 7, 7, 7, 7, 7, 7,			/* a0 .. a7 */
-	7, 7, 7, 7, 7, 7, 7, 7,			/* a8 .. af */
-	7, 7, 7, 7, 7, 7, 7, 7,			/* b0 .. b7 */
-	7, 7, 7, 7, 7, 7, 7, 7,			/* b8 .. bf */
-	7, 7, 7, 7, 7, 7, 7, 7,			/* c0 .. c7 */
-	7, 7, 7, 7, 7, 7, 7, 7,			/* c8 .. cf */
-	7, 7, 7, 7, 7, 7, 7, 7,			/* d0 .. d7 */
-	7, 7, 7, 7, 7, 7, 7, 7,			/* d8 .. df */
-	7, 7, 7, 7, 7, 7, 7, 7,			/* e0 .. e7 */
-	7, 7, 7, 7, 7, 7, 7, 7,			/* e8 .. ef */
-	7, 7, 7, 7, 7, 7, 7, 7,			/* f0 .. f7 */
-	7, 7, 7, 7, 7, 7, 7, 7,			/* f8 .. ff */
-};
-#endif
-
-/*
- * xfs_highbit32: get high bit set out of 32-bit argument, -1 if none set.
- */
-inline int
-xfs_highbit32(
-	__uint32_t	v)
-{
-#ifdef HAVE_ARCH_HIGHBIT
-	return highbit32(v);
-#else
-	int		i;
-
-	if (v & 0xffff0000)
-		if (v & 0xff000000)
-			i = 24;
-		else
-			i = 16;
-	else if (v & 0x0000ffff)
-		if (v & 0x0000ff00)
-			i = 8;
-		else
-			i = 0;
-	else
-		return -1;
-	return i + xfs_highbit[(v >> i) & 0xff];
-#endif
-}
-
-/*
- * xfs_lowbit64: get low bit set out of 64-bit argument, -1 if none set.
- */
-int
-xfs_lowbit64(
-	__uint64_t	v)
-{
-	__uint32_t	w = (__uint32_t)v;
-	int		n = 0;
-
-	if (w) {	/* lower bits */
-		n = ffs(w);
-	} else {	/* upper bits */
-		w = (__uint32_t)(v >> 32);
-		if (w && (n = ffs(w)))
-			n += 32;
-	}
-	return n - 1;
-}
-
-/*
- * xfs_highbit64: get high bit set out of 64-bit argument, -1 if none set.
- */
-int
-xfs_highbit64(
-	__uint64_t	v)
-{
-	__uint32_t	h = (__uint32_t)(v >> 32);
-
-	if (h)
-		return xfs_highbit32(h) + 32;
-	return xfs_highbit32((__uint32_t)v);
-}
-
-
 /*
  * Return whether bitmap is empty.
  * Size is number of words in the bitmap, which is padded to word boundary
Index: linux-2.6.23-rc8-misc/fs/xfs/xfs_bit.h
===================================================================
--- linux-2.6.23-rc8-misc.orig/fs/xfs/xfs_bit.h
+++ linux-2.6.23-rc8-misc/fs/xfs/xfs_bit.h
@@ -46,15 +46,6 @@ static inline __uint64_t xfs_mask64lo(in
 	return ((__uint64_t)1 << (n)) - 1;
 }
 
-/* Get high bit set out of 32-bit argument, -1 if none set */
-extern int xfs_highbit32(__uint32_t v);
-
-/* Get low bit set out of 64-bit argument, -1 if none set */
-extern int xfs_lowbit64(__uint64_t v);
-
-/* Get high bit set out of 64-bit argument, -1 if none set */
-extern int xfs_highbit64(__uint64_t);
-
 /* Return whether bitmap is empty (1 == empty) */
 extern int xfs_bitmap_empty(uint *map, uint size);
 
Index: linux-2.6.23-rc8-misc/fs/xfs/xfs_iget.c
===================================================================
--- linux-2.6.23-rc8-misc.orig/fs/xfs/xfs_iget.c
+++ linux-2.6.23-rc8-misc/fs/xfs/xfs_iget.c
@@ -55,8 +55,7 @@ xfs_ihash_init(xfs_mount_t *mp)
 	if (!mp->m_ihsize) {
 		icount = mp->m_maxicount ? mp->m_maxicount :
 			 (mp->m_sb.sb_dblocks << mp->m_sb.sb_inopblog);
-		mp->m_ihsize = 1 << max_t(uint, 8,
-					(xfs_highbit64(icount) + 1) / 2);
+		mp->m_ihsize = 1 << max_t(uint, 8, fls64(icount) / 2);
 		mp->m_ihsize = min_t(uint, mp->m_ihsize,
 					(64 * NBPP) / sizeof(xfs_ihash_t));
 	}
Index: linux-2.6.23-rc8-misc/fs/xfs/xfs_mount.c
===================================================================
--- linux-2.6.23-rc8-misc.orig/fs/xfs/xfs_mount.c
+++ linux-2.6.23-rc8-misc/fs/xfs/xfs_mount.c
@@ -439,7 +439,7 @@ xfs_xlatesb(
 	mem_ptr = (xfs_caddr_t)sb;
 
 	while (fields) {
-		f = (xfs_sb_field_t)xfs_lowbit64((__uint64_t)fields);
+		f = (xfs_sb_field_t)find_first_bit((unsigned long *)&fields,64);
 		first = xfs_sb_info[f].offset;
 		size = xfs_sb_info[f + 1].offset - first;
 
@@ -589,7 +589,7 @@ xfs_mount_common(xfs_mount_t *mp, xfs_sb
 	mp->m_blkbit_log = sbp->sb_blocklog + XFS_NBBYLOG;
 	mp->m_blkbb_log = sbp->sb_blocklog - BBSHIFT;
 	mp->m_sectbb_log = sbp->sb_sectlog - BBSHIFT;
-	mp->m_agno_log = xfs_highbit32(sbp->sb_agcount - 1) + 1;
+	mp->m_agno_log = fls(sbp->sb_agcount - 1);
 	mp->m_agino_log = sbp->sb_inopblog + sbp->sb_agblklog;
 	mp->m_litino = sbp->sb_inodesize -
 		((uint)sizeof(xfs_dinode_core_t) + (uint)sizeof(xfs_agino_t));
@@ -1428,11 +1428,11 @@ xfs_mod_sb(xfs_trans_t *tp, __int64_t fi
 
 	/* find modified range */
 
-	f = (xfs_sb_field_t)xfs_lowbit64((__uint64_t)fields);
+	f = (xfs_sb_field_t)find_first_bit((unsigned long *)&fields, 64);
 	ASSERT((1LL << f) & XFS_SB_MOD_BITS);
 	first = xfs_sb_info[f].offset;
 
-	f = (xfs_sb_field_t)xfs_highbit64((__uint64_t)fields);
+	f = (xfs_sb_field_t)fls64((__uint64_t)fields) - 1;
 	ASSERT((1LL << f) & XFS_SB_MOD_BITS);
 	last = xfs_sb_info[f + 1].offset - 1;
 
Index: linux-2.6.23-rc8-misc/fs/xfs/xfs_rtalloc.h
===================================================================
--- linux-2.6.23-rc8-misc.orig/fs/xfs/xfs_rtalloc.h
+++ linux-2.6.23-rc8-misc/fs/xfs/xfs_rtalloc.h
@@ -60,13 +60,19 @@ struct xfs_trans;
 #define	XFS_RTMIN(a,b)	((a) < (b) ? (a) : (b))
 #define	XFS_RTMAX(a,b)	((a) > (b) ? (a) : (b))
 
-#define	XFS_RTLOBIT(w)	xfs_lowbit32(w)
-#define	XFS_RTHIBIT(w)	xfs_highbit32(w)
+/* All callers check for 0 arguments already; so no -1 handling */
+static inline int xfs_rtlobit(unsigned long v)
+{
+	return find_first_bit(&v, 32);
+}
+
+#define	XFS_RTLOBIT(w)  xfs_rtlobit(w)
+#define	XFS_RTHIBIT(w)  (fls(w) - 1)
 
 #if XFS_BIG_BLKNOS
-#define	XFS_RTBLOCKLOG(b)	xfs_highbit64(b)
+#define	XFS_RTBLOCKLOG(b)	(fls64(b) - 1)
 #else
-#define	XFS_RTBLOCKLOG(b)	xfs_highbit32(b)
+#define	XFS_RTBLOCKLOG(b)	(fls(b) - 1)
 #endif
 
 
Index: linux-2.6.23-rc8-misc/fs/xfs/xfs_rtalloc.c
===================================================================
--- linux-2.6.23-rc8-misc.orig/fs/xfs/xfs_rtalloc.c
+++ linux-2.6.23-rc8-misc/fs/xfs/xfs_rtalloc.c
@@ -73,18 +73,6 @@ STATIC int xfs_rtmodify_summary(xfs_moun
  */
 
 /*
- * xfs_lowbit32: get low bit set out of 32-bit argument, -1 if none set.
- */
-STATIC int
-xfs_lowbit32(
-	__uint32_t	v)
-{
-	if (v)
-		return ffs(v) - 1;
-	return -1;
-}
-
-/*
  * Allocate space to the bitmap or summary file, and zero it, for growfs.
  */
 STATIC int				/* error */
@@ -444,7 +432,8 @@ xfs_rtallocate_extent_near(
 	}
 	bbno = XFS_BITTOBLOCK(mp, bno);
 	i = 0;
-	log2len = xfs_highbit32(minlen);
+	ASSERT(minlen != 0);
+	log2len = fls(minlen) - 1;
 	/*
 	 * Loop over all bitmap blocks (bbno + i is current block).
 	 */
@@ -607,11 +596,13 @@ xfs_rtallocate_extent_size(
 	int		error;		/* error value */
 	int		i;		/* bitmap block number */
 	int		l;		/* level number (loop control) */
+	int 		end;
 	xfs_rtblock_t	n;		/* next block to be tried */
 	xfs_rtblock_t	r;		/* result block number */
 	xfs_suminfo_t	sum;		/* summary information for extents */
 
 	ASSERT(minlen % prod == 0 && maxlen % prod == 0);
+	ASSERT(maxlen != 0);
 	/*
 	 * Loop over all the levels starting with maxlen.
 	 * At each level, look at all the bitmap blocks, to see if there
@@ -619,7 +610,7 @@ xfs_rtallocate_extent_size(
 	 * Note, only on the initial level can the allocation fail if
 	 * the summary says there's an extent.
 	 */
-	for (l = xfs_highbit32(maxlen); l < mp->m_rsumlevels; l++) {
+	for (l = fls(maxlen) - 1; l < mp->m_rsumlevels; l++) {
 		/*
 		 * Loop over all the bitmap blocks.
 		 */
@@ -669,12 +660,15 @@ xfs_rtallocate_extent_size(
 		*rtblock = NULLRTBLOCK;
 		return 0;
 	}
+	ASSERT(maxlen != 0);
+	ASSERT(minlen != 0);
 	/*
 	 * Loop over sizes, from maxlen down to minlen.
 	 * This time, when we do the allocations, allow smaller ones
 	 * to succeed.
 	 */
-	for (l = xfs_highbit32(maxlen); l >= xfs_highbit32(minlen); l--) {
+	end = fls(minlen) - 1;
+	for (l = fls(maxlen) - 1; l >= end; l--) {
 		/*
 		 * Loop over all the bitmap blocks, try an allocation
 		 * starting in that block.
@@ -1863,7 +1857,6 @@ xfs_growfs_rt(
 	xfs_drfsbno_t	nrblocks;	/* new number of realtime blocks */
 	xfs_extlen_t	nrbmblocks;	/* new number of rt bitmap blocks */
 	xfs_drtbno_t	nrextents;	/* new number of realtime extents */
-	uint8_t		nrextslog;	/* new log2 of sb_rextents */
 	xfs_extlen_t	nrsumblocks;	/* new number of summary blocks */
 	uint		nrsumlevels;	/* new rt summary levels */
 	uint		nrsumsize;	/* new size of rt summary, bytes */
@@ -1900,8 +1893,7 @@ xfs_growfs_rt(
 	nrextents = nrblocks;
 	do_div(nrextents, in->extsize);
 	nrbmblocks = howmany_64(nrextents, NBBY * sbp->sb_blocksize);
-	nrextslog = xfs_highbit32(nrextents);
-	nrsumlevels = nrextslog + 1;
+	nrsumlevels = fls(nrextents);
 	nrsumsize = (uint)sizeof(xfs_suminfo_t) * nrsumlevels * nrbmblocks;
 	nrsumblocks = XFS_B_TO_FSB(mp, nrsumsize);
 	nrsumsize = XFS_FSB_TO_B(mp, nrsumblocks);
@@ -1954,7 +1946,8 @@ xfs_growfs_rt(
 				  nsbp->sb_blocksize * nsbp->sb_rextsize);
 		nsbp->sb_rextents = nsbp->sb_rblocks;
 		do_div(nsbp->sb_rextents, nsbp->sb_rextsize);
-		nsbp->sb_rextslog = xfs_highbit32(nsbp->sb_rextents);
+		ASSERT(nsbp->sb_rextents != 0);
+		nsbp->sb_rextslog = fls(nsbp->sb_rextents) - 1;
 		nrsumlevels = nmp->m_rsumlevels = nsbp->sb_rextslog + 1;
 		nrsumsize =
 			(uint)sizeof(xfs_suminfo_t) * nrsumlevels *
@@ -2317,9 +2310,10 @@ xfs_rtpick_extent(
 		*seqp = 0;
 	}
 	seq = *seqp;
-	if ((log2 = xfs_highbit64(seq)) == -1)
+	if ((log2 = fls64(seq)) == 0)
 		b = 0;
 	else {
+		log2--;
 		resid = seq - (1ULL << log2);
 		b = (mp->m_sb.sb_rextents * ((resid << 1) + 1ULL)) >>
 		    (log2 + 1);
Index: linux-2.6.23-rc8-misc/fs/xfs/xfs_ialloc.h
===================================================================
--- linux-2.6.23-rc8-misc.orig/fs/xfs/xfs_ialloc.h
+++ linux-2.6.23-rc8-misc/fs/xfs/xfs_ialloc.h
@@ -57,10 +57,10 @@ xfs_make_iptr(struct xfs_mount *mp, stru
 #define	XFS_IALLOC_FIND_FREE(fp)	xfs_ialloc_find_free(fp)
 static inline int xfs_ialloc_find_free(xfs_inofree_t *fp)
 {
-	return xfs_lowbit64(*fp);
+	unsigned long v = *fp; /* Guarantee alignment */
+	return find_first_bit(&v, 64);
 }
 
-
 #ifdef __KERNEL__
 /*
  * Allocate an inode on disk.

Re: [PATCH] Replace XFS bit functions with Linux functions

[Christoph Hellwig]

On Tue, Oct 02, 2007 at 10:10:58AM +0200, Andi Kleen wrote:
> 
> XFS had some own functions to find high and low bits.
> 
> This patch replaces them with a call to the respective Linux functions.
> The semantics of the Linux functions differ a little, but i checked
> all call sites that they can deal with that. I think all callers 
> are ok; but i added a few more asserts for the 0 case (where Linux
> and old XFS differ) just to make it easy to detect mistakes.
> 
> The resulting xfs.ko is about 500 bytes smaller on x86-64
> 
> This is similar to the patch Eric sent some days ago, but does
> it more efficiently imho. It replaces his patch.
> 
> I wasn't able to do a full XFS QA run over this unfortunately; but did careful
> review.

The patch looks like it's against mainline, so there might be some
problems applying it to the xfs tree.  At least some of the touched
functions have changed names and maybe content aswell.

>  	while (fields) {
> -		f = (xfs_sb_field_t)xfs_lowbit64((__uint64_t)fields);
> +		f = (xfs_sb_field_t)find_first_bit((unsigned long *)&fields,64);

I don't think we should add the case here but rather pass the fields
varialble as an unsigned long to start with.

> @@ -1428,11 +1428,11 @@ xfs_mod_sb(xfs_trans_t *tp, __int64_t fi
>  
>  	/* find modified range */
>  
> -	f = (xfs_sb_field_t)xfs_lowbit64((__uint64_t)fields);
> +	f = (xfs_sb_field_t)find_first_bit((unsigned long *)&fields, 64);
>  	ASSERT((1LL << f) & XFS_SB_MOD_BITS);
>  	first = xfs_sb_info[f].offset;
>  
> -	f = (xfs_sb_field_t)xfs_highbit64((__uint64_t)fields);
> +	f = (xfs_sb_field_t)fls64((__uint64_t)fields) - 1;

Same here.

> +/* All callers check for 0 arguments already; so no -1 handling */
> +static inline int xfs_rtlobit(unsigned long v)
> +{
> +	return find_first_bit(&v, 32);
> +}
> +
> +#define	XFS_RTLOBIT(w)  xfs_rtlobit(w)

I think just a

#define	XFS_RTLOBIT(w)	find_first_bit(&(w), 32)

should be fine.  Or make it just an inline, but not both a macro an
an inline.

Re: [PATCH] Replace XFS bit functions with Linux functions

[Andi Kleen]

> 
> >  	while (fields) {
> > -		f = (xfs_sb_field_t)xfs_lowbit64((__uint64_t)fields);
> > +		f = (xfs_sb_field_t)find_first_bit((unsigned long *)&fields,64);
> 
> I don't think we should add the case here but rather pass the fields
> varialble as an unsigned long to start with.

I actually did this first, but ran into some issues I unfortunately can't remember right 
now so I reverted it to the cast.

> 
> > @@ -1428,11 +1428,11 @@ xfs_mod_sb(xfs_trans_t *tp, __int64_t fi
> >  
> >  	/* find modified range */
> >  
> > -	f = (xfs_sb_field_t)xfs_lowbit64((__uint64_t)fields);
> > +	f = (xfs_sb_field_t)find_first_bit((unsigned long *)&fields, 64);
> >  	ASSERT((1LL << f) & XFS_SB_MOD_BITS);
> >  	first = xfs_sb_info[f].offset;
> >  
> > -	f = (xfs_sb_field_t)xfs_highbit64((__uint64_t)fields);
> > +	f = (xfs_sb_field_t)fls64((__uint64_t)fields) - 1;
> 
> Same here.

The casts here are actually not needed, but I was too lazy to remove them
(they also don't hurt) 

> 
> > +/* All callers check for 0 arguments already; so no -1 handling */
> > +static inline int xfs_rtlobit(unsigned long v)
> > +{
> > +	return find_first_bit(&v, 32);
> > +}
> > +
> > +#define	XFS_RTLOBIT(w)  xfs_rtlobit(w)
> 
> I think just a
> 
> #define	XFS_RTLOBIT(w)	find_first_bit(&(w), 32)
> 
> should be fine. 

Nope -- not all callers pass sufficiently aligned unsigned longs
as ffb requires.

> Or make it just an inline, but not both a macro an 
> an inline.

That should be probably done as a separate patch because there
are much more macros that need this treatment in the rt code.

-Andi

Re: [PATCH] Replace XFS bit functions with Linux functions

[David Chinner]

On Tue, Oct 02, 2007 at 10:10:58AM +0200, Andi Kleen wrote:
> XFS had some own functions to find high and low bits.
> 
> This patch replaces them with a call to the respective Linux functions.
> The semantics of the Linux functions differ a little, but i checked
> all call sites that they can deal with that. I think all callers 
> are ok; but i added a few more asserts for the 0 case (where Linux
> and old XFS differ) just to make it easy to detect mistakes.
>  
> Index: linux-2.6.23-rc8-misc/fs/xfs/xfs_iget.c
> ===================================================================
> --- linux-2.6.23-rc8-misc.orig/fs/xfs/xfs_iget.c
> +++ linux-2.6.23-rc8-misc/fs/xfs/xfs_iget.c
> @@ -55,8 +55,7 @@ xfs_ihash_init(xfs_mount_t *mp)
>  	if (!mp->m_ihsize) {
>  		icount = mp->m_maxicount ? mp->m_maxicount :
>  			 (mp->m_sb.sb_dblocks << mp->m_sb.sb_inopblog);
> -		mp->m_ihsize = 1 << max_t(uint, 8,
> -					(xfs_highbit64(icount) + 1) / 2);
> +		mp->m_ihsize = 1 << max_t(uint, 8, fls64(icount) / 2);
>  		mp->m_ihsize = min_t(uint, mp->m_ihsize,
>  					(64 * NBPP) / sizeof(xfs_ihash_t));
>  	}

This is well out of date with where the XFS tree is now.
You might want to rebase this on the XFS CVS code or the master
branch of the XFS git tree...

So the conversion is:

	xfs_highbit64 -> fls64() - 1
	xfs_lowbit64(v) -> find_first_bit(&v, 64)
	xfs_highbit32 -> fls - 1
	xfs_lowbit32(v) -> find_first_bit(&v, 32)

and touching lots of places where the xfs functions are used.

One thing that is notable here is that the XFS code returns
-1 if no bits are set. fls/fls64 return 0 in the same case, so
the magic "- 1" will make them behave the same. however, it
appears that find_first_bit() will return the number of bits
searched. That might leave us with som nasty, non-obvious error
cases....

Also, I don't really like the fact it requires sprinkling magic "-
1" adjustments to the return value of the replacement functions.  If
that is the way the functions work and relate to the XFS bitmaps,
then that *should* be hidden away in a macro/static inline so it
doesn't get screwed up in future.

Hence I'd prefer to keep the xfs wrappers whilst replacing the guts of
them with the more efficient generic code. I'm not too concerned,
though, but Russell might want to comment here...

Cheers,

Dave.
-- 
Dave Chinner
Principal Engineer
SGI Australian Software Group

Re: [PATCH] Replace XFS bit functions with Linux functions

[Andi Kleen]

> One thing that is notable here is that the XFS code returns
> -1 if no bits are set. fls/fls64 return 0 in the same case, so
> the magic "- 1" will make them behave the same. however, it
> appears that find_first_bit() will return the number of bits
> searched. That might leave us with som nasty, non-obvious error
> cases....

See the changelog:

The semantics of the Linux functions differ a little, but i checked
all call sites that they can deal with that.

> 
> Also, I don't really like the fact it requires sprinkling magic "-
> 1" adjustments to the return value of the replacement functions.  If
> that is the way the functions work and relate to the XFS bitmaps,

Not all callers use them as bitmap indexes, some also use them as true log2s.
I also eliminated some + 1s.

Whatever you do it's not the same for all.

-Andi

Re: [PATCH] Replace XFS bit functions with Linux functions

[Russell Cattelan]

[-- Attachment #1: Type: text/plain, Size: 12750 bytes --]

Andi Kleen wrote:
> XFS had some own functions to find high and low bits.
>
> This patch replaces them with a call to the respective Linux functions.
> The semantics of the Linux functions differ a little, but i checked
> all call sites that they can deal with that. I think all callers 
> are ok; but i added a few more asserts for the 0 case (where Linux
> and old XFS differ) just to make it easy to detect mistakes.
>
> The resulting xfs.ko is about 500 bytes smaller on x86-64
>
> This is similar to the patch Eric sent some days ago, but does
> it more efficiently imho. It replaces his patch.
>
> I wasn't able to do a full XFS QA run over this unfortunately; but did careful
> review.
>
>   
I would like to keep thing abstracted enough such that it is won't be to
difficult keep to map to the FreeBSD bit functions.

I have not looked closely at the freebsd functions to see how close they
are semantically.
> Signed-off-by: Andi Kleen <ak@suse.de>
>
> Index: linux-2.6.23-rc8-misc/fs/xfs/xfs_bit.c
> ===================================================================
> --- linux-2.6.23-rc8-misc.orig/fs/xfs/xfs_bit.c
> +++ linux-2.6.23-rc8-misc/fs/xfs/xfs_bit.c
> @@ -22,112 +22,9 @@
>  #include "xfs_buf_item.h"
>  
>  /*
> - * XFS bit manipulation routines, used in non-realtime code.
> + * XFS bit manipulation routines
>   */
>  
> -#ifndef HAVE_ARCH_HIGHBIT
> -/*
> - * Index of high bit number in byte, -1 for none set, 0..7 otherwise.
> - */
> -static const char xfs_highbit[256] = {
> -       -1, 0, 1, 1, 2, 2, 2, 2,			/* 00 .. 07 */
> -	3, 3, 3, 3, 3, 3, 3, 3,			/* 08 .. 0f */
> -	4, 4, 4, 4, 4, 4, 4, 4,			/* 10 .. 17 */
> -	4, 4, 4, 4, 4, 4, 4, 4,			/* 18 .. 1f */
> -	5, 5, 5, 5, 5, 5, 5, 5,			/* 20 .. 27 */
> -	5, 5, 5, 5, 5, 5, 5, 5,			/* 28 .. 2f */
> -	5, 5, 5, 5, 5, 5, 5, 5,			/* 30 .. 37 */
> -	5, 5, 5, 5, 5, 5, 5, 5,			/* 38 .. 3f */
> -	6, 6, 6, 6, 6, 6, 6, 6,			/* 40 .. 47 */
> -	6, 6, 6, 6, 6, 6, 6, 6,			/* 48 .. 4f */
> -	6, 6, 6, 6, 6, 6, 6, 6,			/* 50 .. 57 */
> -	6, 6, 6, 6, 6, 6, 6, 6,			/* 58 .. 5f */
> -	6, 6, 6, 6, 6, 6, 6, 6,			/* 60 .. 67 */
> -	6, 6, 6, 6, 6, 6, 6, 6,			/* 68 .. 6f */
> -	6, 6, 6, 6, 6, 6, 6, 6,			/* 70 .. 77 */
> -	6, 6, 6, 6, 6, 6, 6, 6,			/* 78 .. 7f */
> -	7, 7, 7, 7, 7, 7, 7, 7,			/* 80 .. 87 */
> -	7, 7, 7, 7, 7, 7, 7, 7,			/* 88 .. 8f */
> -	7, 7, 7, 7, 7, 7, 7, 7,			/* 90 .. 97 */
> -	7, 7, 7, 7, 7, 7, 7, 7,			/* 98 .. 9f */
> -	7, 7, 7, 7, 7, 7, 7, 7,			/* a0 .. a7 */
> -	7, 7, 7, 7, 7, 7, 7, 7,			/* a8 .. af */
> -	7, 7, 7, 7, 7, 7, 7, 7,			/* b0 .. b7 */
> -	7, 7, 7, 7, 7, 7, 7, 7,			/* b8 .. bf */
> -	7, 7, 7, 7, 7, 7, 7, 7,			/* c0 .. c7 */
> -	7, 7, 7, 7, 7, 7, 7, 7,			/* c8 .. cf */
> -	7, 7, 7, 7, 7, 7, 7, 7,			/* d0 .. d7 */
> -	7, 7, 7, 7, 7, 7, 7, 7,			/* d8 .. df */
> -	7, 7, 7, 7, 7, 7, 7, 7,			/* e0 .. e7 */
> -	7, 7, 7, 7, 7, 7, 7, 7,			/* e8 .. ef */
> -	7, 7, 7, 7, 7, 7, 7, 7,			/* f0 .. f7 */
> -	7, 7, 7, 7, 7, 7, 7, 7,			/* f8 .. ff */
> -};
> -#endif
> -
> -/*
> - * xfs_highbit32: get high bit set out of 32-bit argument, -1 if none set.
> - */
> -inline int
> -xfs_highbit32(
> -	__uint32_t	v)
> -{
> -#ifdef HAVE_ARCH_HIGHBIT
> -	return highbit32(v);
> -#else
> -	int		i;
> -
> -	if (v & 0xffff0000)
> -		if (v & 0xff000000)
> -			i = 24;
> -		else
> -			i = 16;
> -	else if (v & 0x0000ffff)
> -		if (v & 0x0000ff00)
> -			i = 8;
> -		else
> -			i = 0;
> -	else
> -		return -1;
> -	return i + xfs_highbit[(v >> i) & 0xff];
> -#endif
> -}
> -
> -/*
> - * xfs_lowbit64: get low bit set out of 64-bit argument, -1 if none set.
> - */
> -int
> -xfs_lowbit64(
> -	__uint64_t	v)
> -{
> -	__uint32_t	w = (__uint32_t)v;
> -	int		n = 0;
> -
> -	if (w) {	/* lower bits */
> -		n = ffs(w);
> -	} else {	/* upper bits */
> -		w = (__uint32_t)(v >> 32);
> -		if (w && (n = ffs(w)))
> -			n += 32;
> -	}
> -	return n - 1;
> -}
> -
> -/*
> - * xfs_highbit64: get high bit set out of 64-bit argument, -1 if none set.
> - */
> -int
> -xfs_highbit64(
> -	__uint64_t	v)
> -{
> -	__uint32_t	h = (__uint32_t)(v >> 32);
> -
> -	if (h)
> -		return xfs_highbit32(h) + 32;
> -	return xfs_highbit32((__uint32_t)v);
> -}
> -
> -
>  /*
>   * Return whether bitmap is empty.
>   * Size is number of words in the bitmap, which is padded to word boundary
> Index: linux-2.6.23-rc8-misc/fs/xfs/xfs_bit.h
> ===================================================================
> --- linux-2.6.23-rc8-misc.orig/fs/xfs/xfs_bit.h
> +++ linux-2.6.23-rc8-misc/fs/xfs/xfs_bit.h
> @@ -46,15 +46,6 @@ static inline __uint64_t xfs_mask64lo(in
>  	return ((__uint64_t)1 << (n)) - 1;
>  }
>  
> -/* Get high bit set out of 32-bit argument, -1 if none set */
> -extern int xfs_highbit32(__uint32_t v);
> -
> -/* Get low bit set out of 64-bit argument, -1 if none set */
> -extern int xfs_lowbit64(__uint64_t v);
> -
> -/* Get high bit set out of 64-bit argument, -1 if none set */
> -extern int xfs_highbit64(__uint64_t);
> -
>  /* Return whether bitmap is empty (1 == empty) */
>  extern int xfs_bitmap_empty(uint *map, uint size);
>  
> Index: linux-2.6.23-rc8-misc/fs/xfs/xfs_iget.c
> ===================================================================
> --- linux-2.6.23-rc8-misc.orig/fs/xfs/xfs_iget.c
> +++ linux-2.6.23-rc8-misc/fs/xfs/xfs_iget.c
> @@ -55,8 +55,7 @@ xfs_ihash_init(xfs_mount_t *mp)
>  	if (!mp->m_ihsize) {
>  		icount = mp->m_maxicount ? mp->m_maxicount :
>  			 (mp->m_sb.sb_dblocks << mp->m_sb.sb_inopblog);
> -		mp->m_ihsize = 1 << max_t(uint, 8,
> -					(xfs_highbit64(icount) + 1) / 2);
> +		mp->m_ihsize = 1 << max_t(uint, 8, fls64(icount) / 2);
>  		mp->m_ihsize = min_t(uint, mp->m_ihsize,
>  					(64 * NBPP) / sizeof(xfs_ihash_t));
>  	}
> Index: linux-2.6.23-rc8-misc/fs/xfs/xfs_mount.c
> ===================================================================
> --- linux-2.6.23-rc8-misc.orig/fs/xfs/xfs_mount.c
> +++ linux-2.6.23-rc8-misc/fs/xfs/xfs_mount.c
> @@ -439,7 +439,7 @@ xfs_xlatesb(
>  	mem_ptr = (xfs_caddr_t)sb;
>  
>  	while (fields) {
> -		f = (xfs_sb_field_t)xfs_lowbit64((__uint64_t)fields);
> +		f = (xfs_sb_field_t)find_first_bit((unsigned long *)&fields,64);
>  		first = xfs_sb_info[f].offset;
>  		size = xfs_sb_info[f + 1].offset - first;
>  
> @@ -589,7 +589,7 @@ xfs_mount_common(xfs_mount_t *mp, xfs_sb
>  	mp->m_blkbit_log = sbp->sb_blocklog + XFS_NBBYLOG;
>  	mp->m_blkbb_log = sbp->sb_blocklog - BBSHIFT;
>  	mp->m_sectbb_log = sbp->sb_sectlog - BBSHIFT;
> -	mp->m_agno_log = xfs_highbit32(sbp->sb_agcount - 1) + 1;
> +	mp->m_agno_log = fls(sbp->sb_agcount - 1);
>  	mp->m_agino_log = sbp->sb_inopblog + sbp->sb_agblklog;
>  	mp->m_litino = sbp->sb_inodesize -
>  		((uint)sizeof(xfs_dinode_core_t) + (uint)sizeof(xfs_agino_t));
> @@ -1428,11 +1428,11 @@ xfs_mod_sb(xfs_trans_t *tp, __int64_t fi
>  
>  	/* find modified range */
>  
> -	f = (xfs_sb_field_t)xfs_lowbit64((__uint64_t)fields);
> +	f = (xfs_sb_field_t)find_first_bit((unsigned long *)&fields, 64);
>  	ASSERT((1LL << f) & XFS_SB_MOD_BITS);
>  	first = xfs_sb_info[f].offset;
>  
> -	f = (xfs_sb_field_t)xfs_highbit64((__uint64_t)fields);
> +	f = (xfs_sb_field_t)fls64((__uint64_t)fields) - 1;
>  	ASSERT((1LL << f) & XFS_SB_MOD_BITS);
>  	last = xfs_sb_info[f + 1].offset - 1;
>  
> Index: linux-2.6.23-rc8-misc/fs/xfs/xfs_rtalloc.h
> ===================================================================
> --- linux-2.6.23-rc8-misc.orig/fs/xfs/xfs_rtalloc.h
> +++ linux-2.6.23-rc8-misc/fs/xfs/xfs_rtalloc.h
> @@ -60,13 +60,19 @@ struct xfs_trans;
>  #define	XFS_RTMIN(a,b)	((a) < (b) ? (a) : (b))
>  #define	XFS_RTMAX(a,b)	((a) > (b) ? (a) : (b))
>  
> -#define	XFS_RTLOBIT(w)	xfs_lowbit32(w)
> -#define	XFS_RTHIBIT(w)	xfs_highbit32(w)
> +/* All callers check for 0 arguments already; so no -1 handling */
> +static inline int xfs_rtlobit(unsigned long v)
> +{
> +	return find_first_bit(&v, 32);
> +}
> +
> +#define	XFS_RTLOBIT(w)  xfs_rtlobit(w)
> +#define	XFS_RTHIBIT(w)  (fls(w) - 1)
>  
>  #if XFS_BIG_BLKNOS
> -#define	XFS_RTBLOCKLOG(b)	xfs_highbit64(b)
> +#define	XFS_RTBLOCKLOG(b)	(fls64(b) - 1)
>  #else
> -#define	XFS_RTBLOCKLOG(b)	xfs_highbit32(b)
> +#define	XFS_RTBLOCKLOG(b)	(fls(b) - 1)
>  #endif
>  
>  
> Index: linux-2.6.23-rc8-misc/fs/xfs/xfs_rtalloc.c
> ===================================================================
> --- linux-2.6.23-rc8-misc.orig/fs/xfs/xfs_rtalloc.c
> +++ linux-2.6.23-rc8-misc/fs/xfs/xfs_rtalloc.c
> @@ -73,18 +73,6 @@ STATIC int xfs_rtmodify_summary(xfs_moun
>   */
>  
>  /*
> - * xfs_lowbit32: get low bit set out of 32-bit argument, -1 if none set.
> - */
> -STATIC int
> -xfs_lowbit32(
> -	__uint32_t	v)
> -{
> -	if (v)
> -		return ffs(v) - 1;
> -	return -1;
> -}
> -
> -/*
>   * Allocate space to the bitmap or summary file, and zero it, for growfs.
>   */
>  STATIC int				/* error */
> @@ -444,7 +432,8 @@ xfs_rtallocate_extent_near(
>  	}
>  	bbno = XFS_BITTOBLOCK(mp, bno);
>  	i = 0;
> -	log2len = xfs_highbit32(minlen);
> +	ASSERT(minlen != 0);
> +	log2len = fls(minlen) - 1;
>  	/*
>  	 * Loop over all bitmap blocks (bbno + i is current block).
>  	 */
> @@ -607,11 +596,13 @@ xfs_rtallocate_extent_size(
>  	int		error;		/* error value */
>  	int		i;		/* bitmap block number */
>  	int		l;		/* level number (loop control) */
> +	int 		end;
>  	xfs_rtblock_t	n;		/* next block to be tried */
>  	xfs_rtblock_t	r;		/* result block number */
>  	xfs_suminfo_t	sum;		/* summary information for extents */
>  
>  	ASSERT(minlen % prod == 0 && maxlen % prod == 0);
> +	ASSERT(maxlen != 0);
>  	/*
>  	 * Loop over all the levels starting with maxlen.
>  	 * At each level, look at all the bitmap blocks, to see if there
> @@ -619,7 +610,7 @@ xfs_rtallocate_extent_size(
>  	 * Note, only on the initial level can the allocation fail if
>  	 * the summary says there's an extent.
>  	 */
> -	for (l = xfs_highbit32(maxlen); l < mp->m_rsumlevels; l++) {
> +	for (l = fls(maxlen) - 1; l < mp->m_rsumlevels; l++) {
>  		/*
>  		 * Loop over all the bitmap blocks.
>  		 */
> @@ -669,12 +660,15 @@ xfs_rtallocate_extent_size(
>  		*rtblock = NULLRTBLOCK;
>  		return 0;
>  	}
> +	ASSERT(maxlen != 0);
> +	ASSERT(minlen != 0);
>  	/*
>  	 * Loop over sizes, from maxlen down to minlen.
>  	 * This time, when we do the allocations, allow smaller ones
>  	 * to succeed.
>  	 */
> -	for (l = xfs_highbit32(maxlen); l >= xfs_highbit32(minlen); l--) {
> +	end = fls(minlen) - 1;
> +	for (l = fls(maxlen) - 1; l >= end; l--) {
>  		/*
>  		 * Loop over all the bitmap blocks, try an allocation
>  		 * starting in that block.
> @@ -1863,7 +1857,6 @@ xfs_growfs_rt(
>  	xfs_drfsbno_t	nrblocks;	/* new number of realtime blocks */
>  	xfs_extlen_t	nrbmblocks;	/* new number of rt bitmap blocks */
>  	xfs_drtbno_t	nrextents;	/* new number of realtime extents */
> -	uint8_t		nrextslog;	/* new log2 of sb_rextents */
>  	xfs_extlen_t	nrsumblocks;	/* new number of summary blocks */
>  	uint		nrsumlevels;	/* new rt summary levels */
>  	uint		nrsumsize;	/* new size of rt summary, bytes */
> @@ -1900,8 +1893,7 @@ xfs_growfs_rt(
>  	nrextents = nrblocks;
>  	do_div(nrextents, in->extsize);
>  	nrbmblocks = howmany_64(nrextents, NBBY * sbp->sb_blocksize);
> -	nrextslog = xfs_highbit32(nrextents);
> -	nrsumlevels = nrextslog + 1;
> +	nrsumlevels = fls(nrextents);
>  	nrsumsize = (uint)sizeof(xfs_suminfo_t) * nrsumlevels * nrbmblocks;
>  	nrsumblocks = XFS_B_TO_FSB(mp, nrsumsize);
>  	nrsumsize = XFS_FSB_TO_B(mp, nrsumblocks);
> @@ -1954,7 +1946,8 @@ xfs_growfs_rt(
>  				  nsbp->sb_blocksize * nsbp->sb_rextsize);
>  		nsbp->sb_rextents = nsbp->sb_rblocks;
>  		do_div(nsbp->sb_rextents, nsbp->sb_rextsize);
> -		nsbp->sb_rextslog = xfs_highbit32(nsbp->sb_rextents);
> +		ASSERT(nsbp->sb_rextents != 0);
> +		nsbp->sb_rextslog = fls(nsbp->sb_rextents) - 1;
>  		nrsumlevels = nmp->m_rsumlevels = nsbp->sb_rextslog + 1;
>  		nrsumsize =
>  			(uint)sizeof(xfs_suminfo_t) * nrsumlevels *
> @@ -2317,9 +2310,10 @@ xfs_rtpick_extent(
>  		*seqp = 0;
>  	}
>  	seq = *seqp;
> -	if ((log2 = xfs_highbit64(seq)) == -1)
> +	if ((log2 = fls64(seq)) == 0)
>  		b = 0;
>  	else {
> +		log2--;
>  		resid = seq - (1ULL << log2);
>  		b = (mp->m_sb.sb_rextents * ((resid << 1) + 1ULL)) >>
>  		    (log2 + 1);
> Index: linux-2.6.23-rc8-misc/fs/xfs/xfs_ialloc.h
> ===================================================================
> --- linux-2.6.23-rc8-misc.orig/fs/xfs/xfs_ialloc.h
> +++ linux-2.6.23-rc8-misc/fs/xfs/xfs_ialloc.h
> @@ -57,10 +57,10 @@ xfs_make_iptr(struct xfs_mount *mp, stru
>  #define	XFS_IALLOC_FIND_FREE(fp)	xfs_ialloc_find_free(fp)
>  static inline int xfs_ialloc_find_free(xfs_inofree_t *fp)
>  {
> -	return xfs_lowbit64(*fp);
> +	unsigned long v = *fp; /* Guarantee alignment */
> +	return find_first_bit(&v, 64);
>  }
>  
> -
>  #ifdef __KERNEL__
>  /*
>   * Allocate an inode on disk.
>
>   


[-- Attachment #2: cattelan.vcf --]
[-- Type: text/x-vcard, Size: 131 bytes --]

begin:vcard
fn:Russell Cattelan
n:Cattelan;Russell
email;internet:cattelan@thebarn.com
x-mozilla-html:FALSE
version:2.1
end:vcard

Re: [PATCH] Replace XFS bit functions with Linux functions

[Andi Kleen]

> I would like to keep thing abstracted enough such that it is won't be to
> difficult keep to map to the FreeBSD bit functions.

It's no different to map linux bit functions to FreeBSD than mapping
XFS bit functions to FreeBSD. Besides I expect it has fls already -- 
that is actually a BSDism.

-Andi

Re: [PATCH] Replace XFS bit functions with Linux functions

[Russell Cattelan]

[-- Attachment #1: Type: text/plain, Size: 1653 bytes --]

Andi Kleen wrote:
>> I would like to keep thing abstracted enough such that it is won't be to
>> difficult keep to map to the FreeBSD bit functions.
>>     
>
> It's no different to map linux bit functions to FreeBSD than mapping
> XFS bit functions to FreeBSD. Besides I expect it has fls already -- 
> that is actually a BSDism.
>
>   
Yes but for the most part the common code does not play favorites
to linux or bsd or X in terms of which platform is favored. (with some 
execptions).
I have been working getting the freebsd xfs code based updated and I've 
come
across calls to spin_lock that may need to redone.  I need to look at 
the XFS code
paths more to figure out which freebsd lock is needed.
For the most part freebsd tries not to use mutex spin_lock (disable 
interrupts and spin) since it is
more expensive that just mtx_lock (do not disable interrupts and spin 
for awhile then sleep)
and unless there is a good reason to disable interrupts they try 
avoiding doing so.

Playing favorites is kinda what has fueled this whole "ported half of 
irix to linux" FUD
that has dogged xfs forever.
So for the same reason that people complained about mapping irix calls 
to linux calls
I don't like the argument that linux calls should just be mapped to bsd 
calls.

And I agree with Dave the -1 adjustments are bit hard to follow and would
be better encapsulated in a inline call where it can be documented.

Having the xfs_ call in the common code would also allow the fbsd port 
to catch up with
this optimization  as some point vs having to back stitch the current 
code into  common layer
and eventually having to realign.

> -Andi
>
>   


[-- Attachment #2: cattelan.vcf --]
[-- Type: text/x-vcard, Size: 131 bytes --]

begin:vcard
fn:Russell Cattelan
n:Cattelan;Russell
email;internet:cattelan@thebarn.com
x-mozilla-html:FALSE
version:2.1
end:vcard