]> git.proxmox.com Git - mirror_frr.git/blob - lib/wheel.c
lib: Remove tests for ipv[4|6]_prefix_table
[mirror_frr.git] / lib / wheel.c
1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /*
3 * Timer Wheel
4 * Copyright (C) 2016 Cumulus Networks, Inc.
5 * Donald Sharp
6 */
7 #include "zebra.h"
8 #include "linklist.h"
9 #include "thread.h"
10 #include "memory.h"
11 #include "wheel.h"
12 #include "log.h"
13
14 DEFINE_MTYPE_STATIC(LIB, TIMER_WHEEL, "Timer Wheel");
15 DEFINE_MTYPE_STATIC(LIB, TIMER_WHEEL_LIST, "Timer Wheel Slot List");
16
17 static int debug_timer_wheel = 0;
18
19 static void wheel_timer_thread(struct thread *t);
20
21 static void wheel_timer_thread_helper(struct thread *t)
22 {
23 struct listnode *node, *nextnode;
24 unsigned long long curr_slot;
25 unsigned int slots_to_skip = 1;
26 struct timer_wheel *wheel;
27 void *data;
28
29 wheel = THREAD_ARG(t);
30
31 wheel->curr_slot += wheel->slots_to_skip;
32
33 curr_slot = wheel->curr_slot % wheel->slots;
34
35 if (debug_timer_wheel)
36 zlog_debug("%s: Wheel Slot: %lld(%lld) count: %d", __func__,
37 wheel->curr_slot, curr_slot,
38 listcount(wheel->wheel_slot_lists[curr_slot]));
39
40 for (ALL_LIST_ELEMENTS(wheel->wheel_slot_lists[curr_slot], node,
41 nextnode, data))
42 (*wheel->slot_run)(data);
43
44 while (list_isempty(wheel->wheel_slot_lists[(curr_slot + slots_to_skip)
45 % wheel->slots])
46 && (curr_slot + slots_to_skip) % wheel->slots != curr_slot)
47 slots_to_skip++;
48
49 wheel->slots_to_skip = slots_to_skip;
50 thread_add_timer_msec(wheel->master, wheel_timer_thread, wheel,
51 wheel->nexttime * slots_to_skip, &wheel->timer);
52 }
53
54 static void wheel_timer_thread(struct thread *t)
55 {
56 struct timer_wheel *wheel;
57
58 wheel = THREAD_ARG(t);
59
60 thread_execute(wheel->master, wheel_timer_thread_helper, wheel, 0);
61 }
62
63 struct timer_wheel *wheel_init(struct thread_master *master, int period,
64 size_t slots, unsigned int (*slot_key)(const void *),
65 void (*slot_run)(void *),
66 const char *run_name)
67 {
68 struct timer_wheel *wheel;
69 size_t i;
70
71 wheel = XCALLOC(MTYPE_TIMER_WHEEL, sizeof(struct timer_wheel));
72
73 wheel->name = XSTRDUP(MTYPE_TIMER_WHEEL, run_name);
74 wheel->slot_key = slot_key;
75 wheel->slot_run = slot_run;
76
77 wheel->period = period;
78 wheel->slots = slots;
79 wheel->curr_slot = 0;
80 wheel->master = master;
81 wheel->nexttime = period / slots;
82
83 wheel->wheel_slot_lists = XCALLOC(MTYPE_TIMER_WHEEL_LIST,
84 slots * sizeof(struct list *));
85 for (i = 0; i < slots; i++)
86 wheel->wheel_slot_lists[i] = list_new();
87
88 thread_add_timer_msec(wheel->master, wheel_timer_thread, wheel,
89 wheel->nexttime, &wheel->timer);
90
91 return wheel;
92 }
93
94 void wheel_delete(struct timer_wheel *wheel)
95 {
96 int i;
97
98 for (i = 0; i < wheel->slots; i++) {
99 list_delete(&wheel->wheel_slot_lists[i]);
100 }
101
102 THREAD_OFF(wheel->timer);
103 XFREE(MTYPE_TIMER_WHEEL_LIST, wheel->wheel_slot_lists);
104 XFREE(MTYPE_TIMER_WHEEL, wheel->name);
105 XFREE(MTYPE_TIMER_WHEEL, wheel);
106 }
107
108 int wheel_add_item(struct timer_wheel *wheel, void *item)
109 {
110 long long slot;
111
112 slot = (*wheel->slot_key)(item);
113
114 if (debug_timer_wheel)
115 zlog_debug("%s: Inserting %p: %lld %lld", __func__, item, slot,
116 slot % wheel->slots);
117 listnode_add(wheel->wheel_slot_lists[slot % wheel->slots], item);
118
119 return 0;
120 }
121
122 int wheel_remove_item(struct timer_wheel *wheel, void *item)
123 {
124 long long slot;
125
126 slot = (*wheel->slot_key)(item);
127
128 if (debug_timer_wheel)
129 zlog_debug("%s: Removing %p: %lld %lld", __func__, item, slot,
130 slot % wheel->slots);
131 listnode_delete(wheel->wheel_slot_lists[slot % wheel->slots], item);
132
133 return 0;
134 }