1 /*
2 * Timer Wheel
3 * Copyright (C) 2016 Cumulus Networks, Inc.
4 * Donald Sharp
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License along
17 * with this program; see the file COPYING; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 */
20 #include "zebra.h"
21 #include "linklist.h"
22 #include "thread.h"
23 #include "memory.h"
24 #include "wheel.h"
25 #include "log.h"
26
27 DEFINE_MTYPE_STATIC(LIB, TIMER_WHEEL, "Timer Wheel")
28 DEFINE_MTYPE_STATIC(LIB, TIMER_WHEEL_LIST, "Timer Wheel Slot List")
29
30 static int debug_timer_wheel = 0;
31
32 static int wheel_timer_thread(struct thread *t);
33
wheel_timer_thread_helper(struct thread * t)34 static int wheel_timer_thread_helper(struct thread *t)
35 {
36 struct listnode *node, *nextnode;
37 unsigned long long curr_slot;
38 unsigned int slots_to_skip = 1;
39 struct timer_wheel *wheel;
40 void *data;
41
42 wheel = THREAD_ARG(t);
43 THREAD_OFF(wheel->timer);
44
45 wheel->curr_slot += wheel->slots_to_skip;
46
47 curr_slot = wheel->curr_slot % wheel->slots;
48
49 if (debug_timer_wheel)
50 zlog_debug("%s: Wheel Slot: %lld(%lld) count: %d", __func__,
51 wheel->curr_slot, curr_slot,
52 listcount(wheel->wheel_slot_lists[curr_slot]));
53
54 for (ALL_LIST_ELEMENTS(wheel->wheel_slot_lists[curr_slot], node,
55 nextnode, data))
56 (*wheel->slot_run)(data);
57
58 while (list_isempty(wheel->wheel_slot_lists[(curr_slot + slots_to_skip)
59 % wheel->slots])
60 && (curr_slot + slots_to_skip) % wheel->slots != curr_slot)
61 slots_to_skip++;
62
63 wheel->slots_to_skip = slots_to_skip;
64 thread_add_timer_msec(wheel->master, wheel_timer_thread, wheel,
65 wheel->nexttime * slots_to_skip, &wheel->timer);
66
67 return 0;
68 }
69
wheel_timer_thread(struct thread * t)70 static int wheel_timer_thread(struct thread *t)
71 {
72 struct timer_wheel *wheel;
73
74 wheel = THREAD_ARG(t);
75
76 thread_execute_name(wheel->master, wheel_timer_thread_helper,
77 wheel, 0, wheel->name);
78
79 return 0;
80 }
81
wheel_init(struct thread_master * master,int period,size_t slots,unsigned int (* slot_key)(const void *),void (* slot_run)(void *),const char * run_name)82 struct timer_wheel *wheel_init(struct thread_master *master, int period,
83 size_t slots, unsigned int (*slot_key)(const void *),
84 void (*slot_run)(void *),
85 const char *run_name)
86 {
87 struct timer_wheel *wheel;
88 size_t i;
89
90 wheel = XCALLOC(MTYPE_TIMER_WHEEL, sizeof(struct timer_wheel));
91
92 wheel->name = XSTRDUP(MTYPE_TIMER_WHEEL, run_name);
93 wheel->slot_key = slot_key;
94 wheel->slot_run = slot_run;
95
96 wheel->period = period;
97 wheel->slots = slots;
98 wheel->curr_slot = 0;
99 wheel->master = master;
100 wheel->nexttime = period / slots;
101
102 wheel->wheel_slot_lists = XCALLOC(MTYPE_TIMER_WHEEL_LIST,
103 slots * sizeof(struct listnode *));
104 for (i = 0; i < slots; i++)
105 wheel->wheel_slot_lists[i] = list_new();
106
107 thread_add_timer_msec(wheel->master, wheel_timer_thread, wheel,
108 wheel->nexttime, &wheel->timer);
109
110 return wheel;
111 }
112
wheel_delete(struct timer_wheel * wheel)113 void wheel_delete(struct timer_wheel *wheel)
114 {
115 int i;
116
117 for (i = 0; i < wheel->slots; i++) {
118 list_delete(&wheel->wheel_slot_lists[i]);
119 }
120
121 THREAD_OFF(wheel->timer);
122 XFREE(MTYPE_TIMER_WHEEL_LIST, wheel->wheel_slot_lists);
123 XFREE(MTYPE_TIMER_WHEEL, wheel->name);
124 XFREE(MTYPE_TIMER_WHEEL, wheel);
125 }
126
wheel_stop(struct timer_wheel * wheel)127 int wheel_stop(struct timer_wheel *wheel)
128 {
129 THREAD_OFF(wheel->timer);
130 return 0;
131 }
132
wheel_start(struct timer_wheel * wheel)133 int wheel_start(struct timer_wheel *wheel)
134 {
135 if (!wheel->timer)
136 thread_add_timer_msec(wheel->master, wheel_timer_thread, wheel,
137 wheel->nexttime, &wheel->timer);
138
139 return 0;
140 }
141
wheel_add_item(struct timer_wheel * wheel,void * item)142 int wheel_add_item(struct timer_wheel *wheel, void *item)
143 {
144 long long slot;
145
146 slot = (*wheel->slot_key)(item);
147
148 if (debug_timer_wheel)
149 zlog_debug("%s: Inserting %p: %lld %lld", __func__, item, slot,
150 slot % wheel->slots);
151 listnode_add(wheel->wheel_slot_lists[slot % wheel->slots], item);
152
153 return 0;
154 }
155
wheel_remove_item(struct timer_wheel * wheel,void * item)156 int wheel_remove_item(struct timer_wheel *wheel, void *item)
157 {
158 long long slot;
159
160 slot = (*wheel->slot_key)(item);
161
162 if (debug_timer_wheel)
163 zlog_debug("%s: Removing %p: %lld %lld", __func__, item, slot,
164 slot % wheel->slots);
165 listnode_delete(wheel->wheel_slot_lists[slot % wheel->slots], item);
166
167 return 0;
168 }
169