contrib/timerwheel: probable bug on 32-bit, use __builtin_ffs()

Simply always defining BITS_PER_LONG as 64 seems like it's almost
certainly wrong on 32-bit platforms and could potentially result in
incorrect results.

fls and, e.g., __builtin_ffs() return the same answer for any given
input, making it seem like the name fls (find last set) is a misnomer
and ffs (find first set, starting from the lsb) is the more accurate
name.

Using __builtin_ffs() causes the compiler (in intel) to emit code
with the bsf (bit scan forward) insn, which is approx 3x faster than
the code in ffs(), at least on the machine I tried it on. (Even so,
it takes 10M+ iterations for the speed difference to be measurable.
Choosing the "faster" implementation seems like a no-brainer, even
if there may not be any significant gain by doing so.)

Change-Id: I1616dda1a5b76f208ba737a713877c1673131e33
Signed-off-by: Kaleb S. KEITHLEY <kkeithle@redhat.com>
Reviewed-on: https://review.gluster.org/17142
Smoke: Gluster Build System <jenkins@build.gluster.org>
NetBSD-regression: NetBSD Build System <jenkins@build.gluster.org>
CentOS-regression: Gluster Build System <jenkins@build.gluster.org>
Reviewed-by: Niels de Vos <ndevos@redhat.com>
Reviewed-by: Jeff Darcy <jeff@pl.atyp.us>

1 files changed, 12 insertions, 5 deletions

diff --git a/contrib/timer-wheel/find_last_bit.c b/contrib/timer-wheel/find_last_bit.c
index 054e90a076f..0479c52f904 100644
--- a/contrib/timer-wheel/find_last_bit.c
+++ b/contrib/timer-wheel/find_last_bit.c
@@ -15,15 +15,22 @@
 */
 
 /**
- * @find_last_bit
- * optimized implementation of find last bit in
+ * @find_first_bit
+ * optimized implementation of find first bit in
  */
 
 #ifndef BITS_PER_LONG
+#ifdef __LP64__
 #define BITS_PER_LONG 64
+#else
+#define BITS_PER_LONG 32
+#endif
 #endif
 
-static inline int fls(int x)
+#if defined(__GNUC__) || defined(__clang__)
+#define ffs(p) __builtin_ffs(p)
+#else
+static inline int ffs(int x)
 {
 	int r = 32;
 
@@ -51,7 +58,7 @@ static inline int fls(int x)
 	}
 	return r;
 }
-
+#endif
 
 unsigned long gf_tw_find_last_bit(const unsigned long *addr, unsigned long size)
 {
@@ -73,7 +80,7 @@ unsigned long gf_tw_find_last_bit(const unsigned long *addr, unsigned long size)
 		tmp = addr[--words];
 		if (tmp) {
 found:
-			return words * BITS_PER_LONG + fls(tmp);
+			return words * BITS_PER_LONG + ffs(tmp);
 		}
 	}