[cmaster-next] [PATCH 3/9] lib: Add Timer Wheel functionality
Donald Sharp
sharpd at cumulusnetworks.com
Wed Dec 14 15:49:47 EST 2016
Signed-off-by: Donald Sharp <sharpd at cumulusnetworks.com>
---
lib/Makefile.am | 4 +-
lib/wheel.c | 164 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
lib/wheel.h | 70 ++++++++++++++++++++++++
3 files changed, 236 insertions(+), 2 deletions(-)
create mode 100644 lib/wheel.c
create mode 100644 lib/wheel.h
diff --git a/lib/Makefile.am b/lib/Makefile.am
index ffbbacc..f657cb9 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -25,7 +25,7 @@ libzebra_la_SOURCES = \
sigevent.c pqueue.c jhash.c workqueue.c nexthop.c json.c \
ptm_lib.c csv.c bfd.c vrf.c systemd.c ns.c memory.c memory_vty.c \
imsg-buffer.c imsg.c skiplist.c \
- qobj.c \
+ qobj.c wheel.c \
event_counter.c \
strlcpy.c \
strlcat.c
@@ -46,7 +46,7 @@ pkginclude_HEADERS = \
workqueue.h route_types.h libospf.h nexthop.h json.h \
ptm_lib.h csv.h bfd.h vrf.h ns.h systemd.h bitfield.h \
fifo.h memory_vty.h mpls.h imsg.h openbsd-queue.h openbsd-tree.h \
- skiplist.h qobj.h \
+ skiplist.h qobj.h wheel.h \
event_counter.h
noinst_HEADERS = \
diff --git a/lib/wheel.c b/lib/wheel.c
new file mode 100644
index 0000000..3cfd925
--- /dev/null
+++ b/lib/wheel.c
@@ -0,0 +1,164 @@
+/*
+ * Timer Wheel
+ * Copyright (C) 2016 Cumulus Networks, Inc.
+ * Donald Sharp
+ *
+ * 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; see the file COPYING; if not, write to the
+ * Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston,
+ * MA 02110-1301 USA
+ */
+#include "zebra.h"
+#include "linklist.h"
+#include "thread.h"
+#include "memory.h"
+#include "wheel.h"
+#include "log.h"
+
+DEFINE_MTYPE_STATIC(LIB, TIMER_WHEEL, "Timer Wheel")
+DEFINE_MTYPE_STATIC(LIB, TIMER_WHEEL_LIST, "Timer Wheel Slot List")
+
+static int debug_timer_wheel = 1;
+
+static int
+wheel_timer_thread (struct thread *t)
+{
+ struct listnode *node, *nextnode;
+ unsigned long long curr_slot;
+ unsigned int slots_to_skip = 1;
+ struct timer_wheel *wheel;
+ void *data;
+
+ wheel = THREAD_ARG(t);
+ THREAD_OFF(wheel->timer);
+
+ wheel->curr_slot += wheel->slots_to_skip;
+
+ curr_slot = wheel->curr_slot % wheel->slots;
+
+ if (debug_timer_wheel)
+ zlog_debug ("%s: Wheel Slot: %lld(%lld) count: %d",
+ __PRETTY_FUNCTION__,
+ wheel->curr_slot,
+ curr_slot, listcount(wheel->wheel_slot_lists[curr_slot]));
+
+ for (ALL_LIST_ELEMENTS (wheel->wheel_slot_lists[curr_slot], node, nextnode, data))
+ (*wheel->slot_run)(data);
+
+ while (list_isempty(wheel->wheel_slot_lists[(curr_slot + slots_to_skip) % wheel->slots]) &&
+ (curr_slot + slots_to_skip ) % wheel->slots != curr_slot)
+ slots_to_skip++;
+
+ wheel->slots_to_skip = slots_to_skip;
+ THREAD_TIMER_MSEC_ON (wheel->master, wheel->timer,
+ wheel_timer_thread, wheel,
+ wheel->nexttime * slots_to_skip);
+
+ return 0;
+}
+
+struct timer_wheel *
+wheel_init (struct thread_master *master, int period, size_t slots,
+ unsigned int (*slot_key) (void *),
+ void (*slot_run) (void *))
+{
+ struct timer_wheel *wheel;
+ size_t i;
+
+ wheel = XCALLOC(MTYPE_TIMER_WHEEL, sizeof (struct timer_wheel));
+
+ wheel->slot_key = slot_key;
+ wheel->slot_run = slot_run;
+
+ wheel->period = period;
+ wheel->slots = slots;
+ wheel->curr_slot = 0;
+ wheel->master = master;
+ wheel->nexttime = period / slots;
+
+ wheel->wheel_slot_lists = XCALLOC(MTYPE_TIMER_WHEEL_LIST,
+ slots * sizeof (struct listnode *));
+ for (i = 0; i < slots; i++)
+ wheel->wheel_slot_lists[i] = list_new ();
+
+ THREAD_TIMER_MSEC_ON (wheel->master, wheel->timer,
+ wheel_timer_thread, wheel,
+ wheel->nexttime);
+
+ return wheel;
+}
+
+void
+wheel_delete (struct timer_wheel *wheel)
+{
+ int i;
+
+ for (i = 0; i < wheel->slots; i++)
+ {
+ list_delete(wheel->wheel_slot_lists[i]);
+ }
+
+ THREAD_OFF(wheel->timer);
+ XFREE(MTYPE_TIMER_WHEEL_LIST, wheel->wheel_slot_lists);
+ XFREE(MTYPE_TIMER_WHEEL, wheel);
+}
+
+int
+wheel_stop (struct timer_wheel *wheel)
+{
+ THREAD_OFF(wheel->timer);
+ return 0;
+}
+
+int
+wheel_start (struct timer_wheel *wheel)
+{
+ if (!wheel->timer)
+ THREAD_TIMER_MSEC_ON (wheel->master, wheel->timer,
+ wheel_timer_thread, wheel,
+ wheel->nexttime);
+
+ return 0;
+}
+
+int
+wheel_add_item (struct timer_wheel *wheel, void *item)
+{
+ long long slot;
+
+ slot = (*wheel->slot_key)(item);
+
+ if (debug_timer_wheel)
+ zlog_debug ("%s: Inserting %p: %lld %lld",
+ __PRETTY_FUNCTION__, item,
+ slot, slot % wheel->slots);
+ listnode_add (wheel->wheel_slot_lists[slot % wheel->slots], item);
+
+ return 0;
+}
+
+int
+wheel_remove_item (struct timer_wheel *wheel, void *item)
+{
+ long long slot;
+
+ slot = (*wheel->slot_key)(item);
+
+ if (debug_timer_wheel)
+ zlog_debug ("%s: Removing %p: %lld %lld",
+ __PRETTY_FUNCTION__, item,
+ slot, slot % wheel->slots);
+ listnode_delete (wheel->wheel_slot_lists[slot % wheel->slots], item);
+
+ return 0;
+}
diff --git a/lib/wheel.h b/lib/wheel.h
new file mode 100644
index 0000000..ddb7998
--- /dev/null
+++ b/lib/wheel.h
@@ -0,0 +1,70 @@
+/*
+ * Timer Wheel
+ * Copyright (C) 2016 Cumulus Networks, Inc.
+ * Donald Sharp
+ *
+ * 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; see the file COPYING; if not, write to the
+ * Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston,
+ * MA 02110-1301 USA
+ */
+#ifndef __WHEEL_H__
+#define __WHEEL_H__
+
+struct timer_wheel
+{
+ struct thread_master *master;
+ int slots;
+ long long curr_slot;
+ unsigned int period;
+ unsigned int nexttime;
+ unsigned int slots_to_skip;
+
+ struct list **wheel_slot_lists;
+ struct thread *timer;
+ /*
+ * Key to determine what slot the item belongs in
+ */
+ unsigned int (*slot_key) (void *);
+
+ void (*slot_run) (void *);
+};
+
+struct timer_wheel *wheel_init (struct thread_master *master, int period, size_t slots,
+ unsigned int (*slot_key) (void *),
+ void (*slot_run) (void *));
+void wheel_delete (struct timer_wheel *);
+
+/*
+ * Pause the Wheel from running
+ */
+int wheel_stop (struct timer_wheel *wheel);
+
+/*
+ * Start the wheel from running again
+ */
+int wheel_start (struct timer_wheel *wheel);
+
+/*
+ * Add item to a slot setup by the slot_key,
+ * possibly change next time pop.
+ */
+int wheel_add_item (struct timer_wheel *wheel, void *item);
+
+/*
+ * Remove a item to a slot setup by the slot_key,
+ * possibly change next time pop.
+ */
+int wheel_remove_item (struct timer_wheel *wheel, void *item);
+
+#endif
--
2.5.5
More information about the dev
mailing list