From 9d70343977aa870004c836a800a5cec11647b409 Mon Sep 17 00:00:00 2001 From: "Kaleb S. KEITHLEY" Date: Mon, 1 May 2017 12:39:56 -0400 Subject: 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 Reviewed-on: https://review.gluster.org/17146 Smoke: Gluster Build System NetBSD-regression: NetBSD Build System CentOS-regression: Gluster Build System Reviewed-by: Jeff Darcy --- contrib/timer-wheel/find_last_bit.c | 117 +++++++++++++++--------------------- 1 file changed, 48 insertions(+), 69 deletions(-) (limited to 'contrib/timer-wheel/find_last_bit.c') 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 + * (Inspired by David Howell's find_next_bit implementation) + * + * Rewritten by Yury Norov 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; } -- cgit