contrib/timerwheel: bad 32-bit, use builtin fls(), fix copyright

It's bad form to remove other people's copyright and license when you
copy their source for your own use.

Defining BITS_PER_LONG as 64 is incorrect on 32-bit platforms.

The mismatch between the unsigned long of the timer and the int
param to fls() means on 64-bit platforms that any bits set in the
high 32-bits of the the timer are lost/ignored.

gf_tw_find_last_bit() is meant to find the last bit in an array of
longs. It's overkill for gluster's timerwheel  where we only ever pass
a single long; replacing it with a direct call to fls() which is
renamed to gf_tw_fls()

The timer routines are slightly modified from the kernel timer
functions that first appeared circa 2.6.x in .../kernel/timer.c
AFAICT.

find_last_bit() comes from the (linux) kernel (.../lib/find_bit.c
in 4.x kernels, .../lib/find_last_bit.c in 3.x kernels) but as noted
above, it is removed with this patch.

__fls() comes from the linux kernel (.../include/asm-generic/
bitops/{__fls.h,builtin-__fls.h}

Restoring/updating the copyright and license to the version from
the 4.x kernel find_bit.c. (timer.c does not have a license, __fls.h
and builtin-__fls.h do not have a copyright or license, but the whole
kernel is licensed under GPLv2 anyway.)

Change-Id: I2d2defccf1ccc74f55d99e94212747a36a1dff35
Signed-off-by: Kaleb S. KEITHLEY <kkeithle@redhat.com>
Reviewed-on: https://review.gluster.org/17146
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: Jeff Darcy <jeff@pl.atyp.us>

1 files changed, 48 insertions, 69 deletions

diff --git a/contrib/timer-wheel/find_last_bit.c b/contrib/timer-wheel/find_last_bit.c
index 054e90a076f..192fee802a8 100644
--- a/contrib/timer-wheel/find_last_bit.c
+++ b/contrib/timer-wheel/find_last_bit.c
@@ -1,18 +1,20 @@
-/*
-  This program is free software; you can redistribute it and/or modify
-  it under the terms of the GNU General Public License as published by
-  the Free Software Foundation; either version 2 of the License, or
-  (at your option) any later version.
-
-  This program is distributed in the hope that it will be useful,
-  but WITHOUT ANY WARRANTY; without even the implied warranty of
-  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-  GNU General Public License for more details.
-
-  You should have received a copy of the GNU General Public License along
-  with this program; if not, write to the Free Software Foundation, Inc.,
-  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
-*/
+/* bit search implementation
+ *
+ * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * Copyright (C) 2008 IBM Corporation
+ * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
+ * (Inspired by David Howell's find_next_bit implementation)
+ *
+ * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
+ * size and improve performance, 2015.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version
+ * 2 of the License, or (at your option) any later version.
+ */
 
 /**
  * @find_last_bit
@@ -20,63 +22,40 @@
  */
 
 #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)
-{
-	int r = 32;
-
-	if (!x)
-		return 0;
-	if (!(x & 0xffff0000u)) {
-		x <<= 16;
-		r -= 16;
-	}
-	if (!(x & 0xff000000u)) {
-		x <<= 8;
-		r -= 8;
-	}
-	if (!(x & 0xf0000000u)) {
-		x <<= 4;
-		r -= 4;
-	}
-	if (!(x & 0xc0000000u)) {
-		x <<= 2;
-		r -= 2;
-	}
-	if (!(x & 0x80000000u)) {
-		x <<= 1;
-		r -= 1;
-	}
-	return r;
-}
-
-
-unsigned long gf_tw_find_last_bit(const unsigned long *addr, unsigned long size)
+unsigned long gw_tw_fls (unsigned long word)
 {
-	unsigned long words;
-	unsigned long tmp;
-
-	/* Start at final word. */
-	words = size / BITS_PER_LONG;
+        int num = BITS_PER_LONG;
 
-	/* Partial final word? */
-	if (size & (BITS_PER_LONG-1)) {
-		tmp = (addr[words] & (~0UL >> (BITS_PER_LONG
-					 - (size & (BITS_PER_LONG-1)))));
-		if (tmp)
-			goto found;
-	}
-
-	while (words) {
-		tmp = addr[--words];
-		if (tmp) {
-found:
-			return words * BITS_PER_LONG + fls(tmp);
-		}
-	}
-
-	/* Not found */
-	return size;
+#if BITS_PER_LONG == 64
+        if (!(word & (~0ul << 32))) {
+                num -= 32;
+                word <<= 32;
+        }
+#endif
+        if (!(word & (~0ul << (BITS_PER_LONG-16)))) {
+                num -= 16;
+                word <<= 16;
+        }
+        if (!(word & (~0ul << (BITS_PER_LONG-8)))) {
+                num -= 8;
+                word <<= 8;
+        }
+        if (!(word & (~0ul << (BITS_PER_LONG-4)))) {
+                num -= 4;
+                word <<= 4;
+        }
+        if (!(word & (~0ul << (BITS_PER_LONG-2)))) {
+                num -= 2;
+                word <<= 2;
+        }
+        if (!(word & (~0ul << (BITS_PER_LONG-1))))
+                num -= 1;
+        return num;
 }