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.c61
-rw-r--r--contrib/timer-wheel/timer-wheel.c374
-rw-r--r--contrib/timer-wheel/timer-wheel.h77
3 files changed, 512 insertions, 0 deletions
diff --git a/contrib/timer-wheel/find_last_bit.c b/contrib/timer-wheel/find_last_bit.c
new file mode 100644
index 00000000000..192fee802a8
--- /dev/null
+++ b/contrib/timer-wheel/find_last_bit.c
@@ -0,0 +1,61 @@
+/* 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
+ * optimized implementation of find last bit in
+ */
+
+#ifndef BITS_PER_LONG
+#ifdef __LP64__
+#define BITS_PER_LONG 64
+#else
+#define BITS_PER_LONG 32
+#endif
+#endif
+
+unsigned long gw_tw_fls (unsigned long word)
+{
+ int num = BITS_PER_LONG;
+
+#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
new file mode 100644
index 00000000000..58e0607bf0c
--- /dev/null
+++ b/contrib/timer-wheel/timer-wheel.c
@@ -0,0 +1,374 @@
+/*
+ * 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
+ (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.
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/time.h>
+#include <sys/types.h>
+#include <unistd.h>
+#include <sys/select.h>
+
+#include "timer-wheel.h"
+
+static inline void
+__gf_tw_add_timer (struct tvec_base *base, struct gf_tw_timer_list *timer)
+{
+ int i;
+ unsigned long idx;
+ unsigned long expires;
+ struct list_head *vec;
+
+ expires = timer->expires;
+
+ idx = expires - base->timer_sec;
+
+ if (idx < TVR_SIZE) {
+ i = expires & TVR_MASK;
+ vec = base->tv1.vec + i;
+ } else if (idx < 1 << (TVR_BITS + TVN_BITS)) {
+ i = (expires >> TVR_BITS) & TVN_MASK;
+ vec = base->tv2.vec + i;
+ } else if (idx < 1 << (TVR_BITS + 2*TVN_BITS)) {
+ i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;
+ vec = base->tv3.vec + i;
+ } else if (idx < 1 << (TVR_BITS + 3*TVN_BITS)) {
+ i = (expires >> (TVR_BITS + 2*TVN_BITS)) & TVN_MASK;
+ vec = base->tv4.vec + i;
+ } else if (idx < 0) {
+ vec = base->tv1.vec + (base->timer_sec & TVR_MASK);
+ } else {
+ i = (expires >> (TVR_BITS + 3*TVN_BITS)) & TVN_MASK;
+ vec = base->tv5.vec + i;
+ }
+
+ list_add_tail (&timer->entry, vec);
+}
+
+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)
+{
+ long delta;
+ unsigned long mask, expires, expires_limit;
+
+ expires = timer->expires;
+
+ delta = expires - base->timer_sec;
+ if (delta < 256)
+ return expires;
+
+ expires_limit = expires + delta / 256;
+ mask = expires ^ expires_limit;
+ if (mask == 0)
+ return expires;
+
+ int bit = gf_tw_fls (mask);
+ mask = (1UL << bit) - 1;
+
+ expires_limit = expires_limit & ~(mask);
+ return expires_limit;
+}
+
+static inline void
+__gf_tw_detach_timer (struct gf_tw_timer_list *timer)
+{
+ struct list_head *entry = &timer->entry;
+
+ list_del (entry);
+ entry->next = NULL;
+}
+
+static inline int
+cascade (struct tvec_base *base, struct tvec *tv, int index)
+{
+ struct gf_tw_timer_list *timer, *tmp;
+ struct list_head tv_list;
+
+ list_replace_init (tv->vec + index, &tv_list);
+
+ list_for_each_entry_safe (timer, tmp, &tv_list, entry) {
+ __gf_tw_add_timer (base, timer);
+ }
+
+ return index;
+}
+
+#define INDEX(N) ((base->timer_sec >> (TVR_BITS + N * TVN_BITS)) & TVN_MASK)
+
+/**
+ * run expired timers
+ */
+static inline void
+run_timers (struct tvec_base *base)
+{
+ unsigned long index, call_time;
+ struct gf_tw_timer_list *timer;
+
+ struct list_head work_list;
+ struct list_head *head = &work_list;
+
+ pthread_spin_lock (&base->lock);
+ {
+ index = base->timer_sec & TVR_MASK;
+
+ if (!index &&
+ (!cascade (base, &base->tv2, INDEX(0))) &&
+ (!cascade (base, &base->tv3, INDEX(1))) &&
+ (!cascade (base, &base->tv4, INDEX(2))))
+ cascade (base, &base->tv5, INDEX(3));
+
+ call_time = base->timer_sec++;
+ list_replace_init (base->tv1.vec + index, head);
+ while (!list_empty(head)) {
+ void (*fn)(struct gf_tw_timer_list *, void *, unsigned long);
+ void *data;
+
+ timer = list_first_entry (head, struct gf_tw_timer_list, entry);
+ fn = timer->function;
+ data = timer->data;
+
+ __gf_tw_detach_timer (timer);
+ 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);
+
+}
+
+void *runner (void *arg)
+{
+ struct timeval tv = {0,};
+ struct tvec_base *base = arg;
+
+ while (1) {
+ run_timers (base);
+
+ tv.tv_sec = 1;
+ tv.tv_usec = 0;
+ (void) select (0, NULL, NULL, NULL, &tv);
+ }
+
+ return NULL;
+
+}
+
+static inline int timer_pending (struct gf_tw_timer_list *timer)
+{
+ struct list_head *entry = &timer->entry;
+
+ return (entry->next != NULL);
+}
+
+static inline int __detach_if_pending (struct gf_tw_timer_list *timer)
+{
+ if (!timer_pending (timer))
+ return 0;
+
+ __gf_tw_detach_timer (timer);
+ return 1;
+}
+
+static inline int __mod_timer (struct tvec_base *base,
+ struct gf_tw_timer_list *timer, int pending_only)
+{
+ int ret = 0;
+
+ ret = __detach_if_pending (timer);
+ if (!ret && pending_only)
+ goto done;
+
+ ret = 1;
+ __gf_tw_add_timer (base, timer);
+
+ done:
+ return ret;
+}
+
+/* interface */
+
+/**
+ * Add a timer in the timer wheel
+ */
+void gf_tw_add_timer (struct tvec_base *base, struct gf_tw_timer_list *timer)
+{
+ pthread_spin_lock (&base->lock);
+ {
+ timer->expires += base->timer_sec;
+ timer->expires = apply_slack (base, timer);
+ __gf_tw_add_timer (base, timer);
+ }
+ pthread_spin_unlock (&base->lock);
+}
+
+/**
+ * Remove a timer from the timer wheel
+ */
+int gf_tw_del_timer (struct tvec_base *base, struct gf_tw_timer_list *timer)
+{
+ int ret = 0;
+
+ pthread_spin_lock (&base->lock);
+ {
+ if (timer_pending (timer)) {
+ ret = 1;
+ __gf_tw_detach_timer (timer);
+ }
+ }
+ pthread_spin_unlock (&base->lock);
+
+ return ret;
+}
+
+int gf_tw_mod_timer_pending (struct tvec_base *base,
+ struct gf_tw_timer_list *timer,
+ unsigned long expires)
+{
+ int ret = 1;
+
+ pthread_spin_lock (&base->lock);
+ {
+ timer->expires = expires + base->timer_sec;
+ timer->expires = apply_slack (base, timer);
+
+ ret = __mod_timer (base, timer, 1);
+ }
+ pthread_spin_unlock (&base->lock);
+
+ return ret;
+}
+
+int gf_tw_mod_timer (struct tvec_base *base,
+ struct gf_tw_timer_list *timer, unsigned long expires)
+{
+ int ret = 1;
+
+ pthread_spin_lock (&base->lock);
+ {
+ /* fast path optimization */
+ if (timer_pending (timer) && timer->expires == expires)
+ goto unblock;
+
+ timer->expires = expires + base->timer_sec;
+ timer->expires = apply_slack (base, timer);
+
+ ret = __mod_timer (base, timer, 0);
+ }
+ unblock:
+ pthread_spin_unlock (&base->lock);
+
+ return ret;
+}
+
+int gf_tw_cleanup_timers (struct tvec_base *base)
+{
+ int ret = 0;
+ void *res = NULL;
+
+ /* terminate runner */
+ ret = pthread_cancel (base->runner);
+ if (ret != 0)
+ goto error_return;
+ ret = pthread_join (base->runner, &res);
+ if (ret != 0)
+ goto error_return;
+ if (res != PTHREAD_CANCELED)
+ goto error_return;
+
+ /* destroy lock */
+ ret = pthread_spin_destroy (&base->lock);
+ if (ret != 0)
+ goto error_return;
+
+ /* deallocated timer base */
+ free (base);
+ return 0;
+
+ error_return:
+ return -1;
+}
+
+/**
+ * Initialize various timer wheel lists and spawn a thread that
+ * invokes run_timers()
+ */
+struct tvec_base *gf_tw_init_timers ()
+{
+ int j = 0;
+ int ret = 0;
+ struct timeval tv = {0,};
+ struct tvec_base *base = NULL;
+
+ base = malloc (sizeof (*base));
+ if (!base)
+ goto error_return;
+
+ ret = pthread_spin_init (&base->lock, 0);
+ if (ret != 0)
+ goto error_dealloc;
+
+ for (j = 0; j < TVN_SIZE; j++) {
+ INIT_LIST_HEAD (base->tv5.vec + j);
+ INIT_LIST_HEAD (base->tv4.vec + j);
+ INIT_LIST_HEAD (base->tv3.vec + j);
+ INIT_LIST_HEAD (base->tv2.vec + j);
+ }
+
+ for (j = 0; j < TVR_SIZE; j++) {
+ INIT_LIST_HEAD (base->tv1.vec + j);
+ }
+
+ ret = gettimeofday (&tv, 0);
+ if (ret < 0)
+ goto destroy_lock;
+ base->timer_sec = tv.tv_sec;
+
+ ret = pthread_create (&base->runner, NULL, runner, base);
+ if (ret != 0)
+ goto destroy_lock;
+ return base;
+
+ destroy_lock:
+ (void) pthread_spin_destroy (&base->lock);
+ error_dealloc:
+ free (base);
+ error_return:
+ return NULL;
+}
diff --git a/contrib/timer-wheel/timer-wheel.h b/contrib/timer-wheel/timer-wheel.h
new file mode 100644
index 00000000000..5637735ec22
--- /dev/null
+++ b/contrib/timer-wheel/timer-wheel.h
@@ -0,0 +1,77 @@
+/*
+ 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.
+*/
+
+#ifndef __TIMER_WHEEL_H
+#define __TIMER_WHEEL_H
+
+#include "glusterfs/locking.h"
+
+#include "glusterfs/list.h"
+
+#define TVR_BITS 8
+#define TVN_BITS 6
+#define TVR_SIZE (1 << TVR_BITS)
+#define TVN_SIZE (1 << TVN_BITS)
+#define TVR_MASK (TVR_SIZE - 1)
+#define TVN_MASK (TVN_SIZE - 1)
+
+#define BITS_PER_LONG 64
+
+struct tvec {
+ struct list_head vec[TVN_SIZE];
+};
+
+struct tvec_root {
+ struct list_head vec[TVR_SIZE];
+};
+
+struct tvec_base {
+ pthread_spinlock_t lock; /* base lock */
+
+ pthread_t runner; /* run_timer() */
+
+ unsigned long timer_sec; /* time counter */
+
+ struct tvec_root tv1;
+ struct tvec tv2;
+ struct tvec tv3;
+ struct tvec tv4;
+ struct tvec tv5;
+};
+
+struct gf_tw_timer_list {
+ void *data;
+ unsigned long expires;
+
+ /** callback routine */
+ void (*function)(struct gf_tw_timer_list *, void *, unsigned long);
+
+ struct list_head entry;
+};
+
+/** The API! */
+struct tvec_base *gf_tw_init_timers ();
+int gf_tw_cleanup_timers (struct tvec_base *);
+void gf_tw_add_timer (struct tvec_base *, struct gf_tw_timer_list *);
+int gf_tw_del_timer (struct tvec_base *, struct gf_tw_timer_list *);
+
+int gf_tw_mod_timer_pending (struct tvec_base *,
+ struct gf_tw_timer_list *, unsigned long);
+
+int gf_tw_mod_timer (struct tvec_base *,
+ struct gf_tw_timer_list *, unsigned long);
+
+#endif
generated by cgit (git 2.34.1) at 2025-12-28 22:01:40 +0000