3 * Copyright (C) 2016 Cumulus Networks, Inc.
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.
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.
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
27 DEFINE_MTYPE_STATIC(LIB
, TIMER_WHEEL
, "Timer Wheel");
28 DEFINE_MTYPE_STATIC(LIB
, TIMER_WHEEL_LIST
, "Timer Wheel Slot List");
30 static int debug_timer_wheel
= 0;
32 static void wheel_timer_thread(struct thread
*t
);
34 static void wheel_timer_thread_helper(struct thread
*t
)
36 struct listnode
*node
, *nextnode
;
37 unsigned long long curr_slot
;
38 unsigned int slots_to_skip
= 1;
39 struct timer_wheel
*wheel
;
42 wheel
= THREAD_ARG(t
);
44 wheel
->curr_slot
+= wheel
->slots_to_skip
;
46 curr_slot
= wheel
->curr_slot
% wheel
->slots
;
48 if (debug_timer_wheel
)
49 zlog_debug("%s: Wheel Slot: %lld(%lld) count: %d", __func__
,
50 wheel
->curr_slot
, curr_slot
,
51 listcount(wheel
->wheel_slot_lists
[curr_slot
]));
53 for (ALL_LIST_ELEMENTS(wheel
->wheel_slot_lists
[curr_slot
], node
,
55 (*wheel
->slot_run
)(data
);
57 while (list_isempty(wheel
->wheel_slot_lists
[(curr_slot
+ slots_to_skip
)
59 && (curr_slot
+ slots_to_skip
) % wheel
->slots
!= curr_slot
)
62 wheel
->slots_to_skip
= slots_to_skip
;
63 thread_add_timer_msec(wheel
->master
, wheel_timer_thread
, wheel
,
64 wheel
->nexttime
* slots_to_skip
, &wheel
->timer
);
67 static void wheel_timer_thread(struct thread
*t
)
69 struct timer_wheel
*wheel
;
71 wheel
= THREAD_ARG(t
);
73 thread_execute(wheel
->master
, wheel_timer_thread_helper
, wheel
, 0);
76 struct timer_wheel
*wheel_init(struct thread_master
*master
, int period
,
77 size_t slots
, unsigned int (*slot_key
)(const void *),
78 void (*slot_run
)(void *),
81 struct timer_wheel
*wheel
;
84 wheel
= XCALLOC(MTYPE_TIMER_WHEEL
, sizeof(struct timer_wheel
));
86 wheel
->name
= XSTRDUP(MTYPE_TIMER_WHEEL
, run_name
);
87 wheel
->slot_key
= slot_key
;
88 wheel
->slot_run
= slot_run
;
90 wheel
->period
= period
;
93 wheel
->master
= master
;
94 wheel
->nexttime
= period
/ slots
;
96 wheel
->wheel_slot_lists
= XCALLOC(MTYPE_TIMER_WHEEL_LIST
,
97 slots
* sizeof(struct list
*));
98 for (i
= 0; i
< slots
; i
++)
99 wheel
->wheel_slot_lists
[i
] = list_new();
101 thread_add_timer_msec(wheel
->master
, wheel_timer_thread
, wheel
,
102 wheel
->nexttime
, &wheel
->timer
);
107 void wheel_delete(struct timer_wheel
*wheel
)
111 for (i
= 0; i
< wheel
->slots
; i
++) {
112 list_delete(&wheel
->wheel_slot_lists
[i
]);
115 THREAD_OFF(wheel
->timer
);
116 XFREE(MTYPE_TIMER_WHEEL_LIST
, wheel
->wheel_slot_lists
);
117 XFREE(MTYPE_TIMER_WHEEL
, wheel
->name
);
118 XFREE(MTYPE_TIMER_WHEEL
, wheel
);
121 int wheel_stop(struct timer_wheel
*wheel
)
123 THREAD_OFF(wheel
->timer
);
127 int wheel_start(struct timer_wheel
*wheel
)
130 thread_add_timer_msec(wheel
->master
, wheel_timer_thread
, wheel
,
131 wheel
->nexttime
, &wheel
->timer
);
136 int wheel_add_item(struct timer_wheel
*wheel
, void *item
)
140 slot
= (*wheel
->slot_key
)(item
);
142 if (debug_timer_wheel
)
143 zlog_debug("%s: Inserting %p: %lld %lld", __func__
, item
, slot
,
144 slot
% wheel
->slots
);
145 listnode_add(wheel
->wheel_slot_lists
[slot
% wheel
->slots
], item
);
150 int wheel_remove_item(struct timer_wheel
*wheel
, void *item
)
154 slot
= (*wheel
->slot_key
)(item
);
156 if (debug_timer_wheel
)
157 zlog_debug("%s: Removing %p: %lld %lld", __func__
, item
, slot
,
158 slot
% wheel
->slots
);
159 listnode_delete(wheel
->wheel_slot_lists
[slot
% wheel
->slots
], item
);