summaryrefslogtreecommitdiffstats
path: root/contrib/timer-wheel
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/timer-wheel')
-rw-r--r--contrib/timer-wheel/find_last_bit.c117
-rw-r--r--contrib/timer-wheel/timer-wheel.c29
-rw-r--r--contrib/timer-wheel/timer-wheel.h4
3 files changed, 76 insertions, 74 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;
}
diff --git a/contrib/timer-wheel/timer-wheel.c b/contrib/timer-wheel/timer-wheel.c
index 013c0f278a1..58e0607bf0c 100644
--- a/contrib/timer-wheel/timer-wheel.c
+++ b/contrib/timer-wheel/timer-wheel.c
@@ -1,4 +1,12 @@
/*
+ * linux/kernel/timer.c
+ *
+ * Kernel internal timers
+ *
+ * Copyright (C) 1991, 1992 Linus Torvalds
+ *
+ */
+/*
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
@@ -57,9 +65,17 @@ __gf_tw_add_timer (struct tvec_base *base, struct gf_tw_timer_list *timer)
list_add_tail (&timer->entry, vec);
}
-/* optimized find_last_bit() */
unsigned long gf_tw_find_last_bit(const unsigned long *, unsigned long);
+#if defined(__GNUC__) || defined(__clang__)
+static inline unsigned long gf_tw_fls (unsigned long word)
+{
+ return BITS_PER_LONG - __builtin_clzl(word);
+}
+#else
+extern unsigned long gf_tw_fls (unsigned long);
+#endif
+
static inline unsigned long
apply_slack(struct tvec_base *base, struct gf_tw_timer_list *timer)
{
@@ -77,7 +93,7 @@ apply_slack(struct tvec_base *base, struct gf_tw_timer_list *timer)
if (mask == 0)
return expires;
- int bit = gf_tw_find_last_bit (&mask, BITS_PER_LONG);
+ int bit = gf_tw_fls (mask);
mask = (1UL << bit) - 1;
expires_limit = expires_limit & ~(mask);
@@ -143,7 +159,14 @@ run_timers (struct tvec_base *base)
data = timer->data;
__gf_tw_detach_timer (timer);
- fn (timer, data, call_time);
+ pthread_spin_unlock(&base->lock);
+ {
+ /* It is required to run the actual function outside
+ of the locked zone, so we don't bother about
+ locked operations inside that function */
+ fn(timer, data, call_time);
+ }
+ pthread_spin_lock(&base->lock);
}
}
pthread_spin_unlock (&base->lock);
diff --git a/contrib/timer-wheel/timer-wheel.h b/contrib/timer-wheel/timer-wheel.h
index baa029ebb30..5637735ec22 100644
--- a/contrib/timer-wheel/timer-wheel.h
+++ b/contrib/timer-wheel/timer-wheel.h
@@ -17,9 +17,9 @@
#ifndef __TIMER_WHEEL_H
#define __TIMER_WHEEL_H
-#include "locking.h"
+#include "glusterfs/locking.h"
-#include "list.h"
+#include "glusterfs/list.h"
#define TVR_BITS 8
#define TVN_BITS 6
generated by cgit (git 2.34.1) at 2025-12-28 21:56:16 +0000