]>
Commit | Line | Data |
---|---|---|
c1d0d21f CF |
1 | /* |
2 | * This is an implementation of the IETF SPF delay algorithm | |
3 | * as explained in draft-ietf-rtgwg-backoff-algo-04 | |
4 | * | |
5 | * Created: 25-01-2017 by S. Litkowski | |
6 | * | |
7 | * Copyright (C) 2017 Orange Labs http://www.orange.com/ | |
8 | * Copyright (C) 2017 by Christian Franke, Open Source Routing / NetDEF Inc. | |
9 | * | |
10 | * This file is part of FreeRangeRouting (FRR) | |
11 | * | |
12 | * FRR is free software; you can redistribute it and/or modify it | |
13 | * under the terms of the GNU General Public License as published by the | |
14 | * Free Software Foundation; either version 2, or (at your option) any | |
15 | * later version. | |
16 | * | |
17 | * FRR is distributed in the hope that it will be useful, but | |
18 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
19 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
20 | * General Public License for more details. | |
21 | * | |
22 | * You should have received a copy of the GNU General Public License | |
23 | * along with FRR; see the file COPYING. If not, write to the Free | |
24 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA | |
25 | * 02111-1307, USA. | |
26 | */ | |
27 | ||
28 | #include <zebra.h> | |
29 | ||
30 | #include "spf_backoff.h" | |
31 | ||
32 | #include "command.h" | |
33 | #include "memory.h" | |
34 | #include "thread.h" | |
35 | #include "vty.h" | |
36 | ||
37 | DEFINE_MTYPE_STATIC(LIB, SPF_BACKOFF, "SPF backoff") | |
38 | DEFINE_MTYPE_STATIC(LIB, SPF_BACKOFF_NAME, "SPF backoff name") | |
39 | ||
40 | static bool debug_spf_backoff = false; | |
41 | #define backoff_debug(...) \ | |
42 | do \ | |
43 | { \ | |
44 | if (debug_spf_backoff) \ | |
45 | zlog_debug(__VA_ARGS__); \ | |
46 | } \ | |
47 | while (0) | |
48 | ||
49 | enum spf_backoff_state { | |
50 | SPF_BACKOFF_QUIET, | |
51 | SPF_BACKOFF_SHORT_WAIT, | |
52 | SPF_BACKOFF_LONG_WAIT | |
53 | }; | |
54 | ||
55 | struct spf_backoff { | |
56 | struct thread_master *m; | |
57 | ||
58 | /* Timers as per draft */ | |
59 | long init_delay; | |
60 | long short_delay; | |
61 | long long_delay; | |
62 | long holddown; | |
63 | long timetolearn; | |
64 | ||
65 | /* State machine */ | |
66 | enum spf_backoff_state state; | |
67 | struct thread *t_holddown; | |
68 | struct thread *t_timetolearn; | |
69 | ||
70 | /* For debugging */ | |
71 | char *name; | |
72 | struct timeval first_event_time; | |
73 | struct timeval last_event_time; | |
74 | }; | |
75 | ||
76 | static const char * | |
77 | spf_backoff_state2str(enum spf_backoff_state state) | |
78 | { | |
79 | switch (state) | |
80 | { | |
81 | case SPF_BACKOFF_QUIET: | |
82 | return "QUIET"; | |
83 | case SPF_BACKOFF_SHORT_WAIT: | |
84 | return "SHORT_WAIT"; | |
85 | case SPF_BACKOFF_LONG_WAIT: | |
86 | return "LONG_WAIT"; | |
87 | } | |
88 | return "???"; | |
89 | } | |
90 | ||
91 | struct spf_backoff * | |
92 | spf_backoff_new(struct thread_master *m, | |
93 | const char *name, | |
94 | long init_delay, | |
95 | long short_delay, | |
96 | long long_delay, | |
97 | long holddown, | |
98 | long timetolearn) | |
99 | { | |
100 | struct spf_backoff *rv; | |
101 | ||
102 | rv = XCALLOC(MTYPE_SPF_BACKOFF, sizeof(*rv)); | |
103 | rv->m = m; | |
104 | ||
105 | rv->init_delay = init_delay; | |
106 | rv->short_delay = short_delay; | |
107 | rv->long_delay = long_delay; | |
108 | rv->holddown = holddown; | |
109 | rv->timetolearn = timetolearn; | |
110 | ||
111 | rv->state = SPF_BACKOFF_QUIET; | |
112 | ||
113 | rv->name = XSTRDUP(MTYPE_SPF_BACKOFF_NAME, name); | |
114 | return rv; | |
115 | } | |
116 | ||
117 | void | |
118 | spf_backoff_free(struct spf_backoff *backoff) | |
119 | { | |
120 | if (!backoff) | |
121 | return; | |
122 | ||
123 | THREAD_TIMER_OFF(backoff->t_holddown); | |
124 | THREAD_TIMER_OFF(backoff->t_timetolearn); | |
125 | XFREE(MTYPE_SPF_BACKOFF_NAME, backoff->name); | |
126 | ||
127 | XFREE(MTYPE_SPF_BACKOFF, backoff); | |
128 | } | |
129 | ||
130 | static int | |
131 | spf_backoff_timetolearn_elapsed(struct thread *thread) | |
132 | { | |
133 | struct spf_backoff *backoff = THREAD_ARG(thread); | |
134 | ||
135 | backoff->t_timetolearn = NULL; | |
136 | backoff->state = SPF_BACKOFF_LONG_WAIT; | |
137 | backoff_debug("SPF Back-off(%s) TIMETOLEARN elapsed, move to state %s", | |
138 | backoff->name, spf_backoff_state2str(backoff->state)); | |
139 | return 0; | |
140 | } | |
141 | ||
142 | static int | |
143 | spf_backoff_holddown_elapsed(struct thread *thread) | |
144 | { | |
145 | struct spf_backoff *backoff = THREAD_ARG(thread); | |
146 | ||
147 | backoff->t_holddown = NULL; | |
148 | THREAD_TIMER_OFF(backoff->t_timetolearn); | |
149 | timerclear(&backoff->first_event_time); | |
150 | backoff->state = SPF_BACKOFF_QUIET; | |
151 | backoff_debug("SPF Back-off(%s) HOLDDOWN elapsed, move to state %s", | |
152 | backoff->name, spf_backoff_state2str(backoff->state)); | |
153 | return 0; | |
154 | } | |
155 | ||
156 | long spf_backoff_schedule(struct spf_backoff *backoff) | |
157 | { | |
158 | long rv; | |
159 | struct timeval now; | |
160 | ||
161 | gettimeofday(&now, NULL); | |
162 | ||
163 | backoff_debug("SPF Back-off(%s) schedule called in state %s", | |
164 | backoff->name, spf_backoff_state2str(backoff->state)); | |
165 | ||
166 | backoff->last_event_time = now; | |
167 | ||
168 | switch (backoff->state) | |
169 | { | |
170 | case SPF_BACKOFF_QUIET: | |
171 | backoff->state = SPF_BACKOFF_SHORT_WAIT; | |
ffa2c898 QY |
172 | thread_add_timer_msec(backoff->m, spf_backoff_timetolearn_elapsed, |
173 | backoff, backoff->timetolearn, | |
174 | &backoff->t_timetolearn); | |
175 | thread_add_timer_msec(backoff->m, spf_backoff_holddown_elapsed, backoff, | |
176 | backoff->holddown, &backoff->t_holddown); | |
c1d0d21f CF |
177 | backoff->first_event_time = now; |
178 | rv = backoff->init_delay; | |
179 | break; | |
180 | case SPF_BACKOFF_SHORT_WAIT: | |
181 | case SPF_BACKOFF_LONG_WAIT: | |
182 | THREAD_TIMER_OFF(backoff->t_holddown); | |
ffa2c898 QY |
183 | thread_add_timer_msec(backoff->m, spf_backoff_holddown_elapsed, backoff, |
184 | backoff->holddown, &backoff->t_holddown); | |
c1d0d21f CF |
185 | if (backoff->state == SPF_BACKOFF_SHORT_WAIT) |
186 | rv = backoff->short_delay; | |
187 | else | |
188 | rv = backoff->long_delay; | |
189 | break; | |
190 | default: | |
191 | zlog_warn("SPF Back-off(%s) in unknown state", backoff->name); | |
192 | rv = backoff->init_delay; | |
193 | } | |
194 | ||
195 | backoff_debug("SPF Back-off(%s) changed state to %s and returned %ld delay", | |
196 | backoff->name, spf_backoff_state2str(backoff->state), rv); | |
197 | return rv; | |
198 | } | |
199 | ||
200 | static const char * | |
201 | timeval_format(struct timeval *tv) | |
202 | { | |
203 | struct tm tm_store; | |
204 | struct tm *tm; | |
205 | static char timebuf[256]; | |
206 | ||
207 | if (!tv->tv_sec && !tv->tv_usec) | |
208 | return "(never)"; | |
209 | ||
210 | tm = localtime_r(&tv->tv_sec, &tm_store); | |
211 | if (!tm || strftime(timebuf, sizeof(timebuf), | |
212 | "%Z %a %Y-%m-%d %H:%M:%S", tm) == 0) | |
213 | { | |
214 | return "???"; | |
215 | } | |
216 | ||
217 | size_t offset = strlen(timebuf); | |
218 | snprintf(timebuf + offset, sizeof(timebuf) - offset, ".%ld", tv->tv_usec); | |
219 | ||
220 | return timebuf; | |
221 | } | |
222 | ||
223 | void | |
224 | spf_backoff_show(struct spf_backoff *backoff, struct vty *vty, | |
225 | const char *prefix) | |
226 | { | |
227 | vty_out(vty, "%sCurrent state: %s%s", prefix, | |
228 | spf_backoff_state2str(backoff->state), VTY_NEWLINE); | |
229 | vty_out(vty, "%sInit timer: %ld msec%s", prefix, | |
230 | backoff->init_delay, VTY_NEWLINE); | |
231 | vty_out(vty, "%sShort timer: %ld msec%s", prefix, | |
232 | backoff->short_delay, VTY_NEWLINE); | |
233 | vty_out(vty, "%sLong timer: %ld msec%s", prefix, | |
234 | backoff->long_delay, VTY_NEWLINE); | |
235 | vty_out(vty, "%sHolddown timer: %ld msec%s", prefix, | |
236 | backoff->holddown, VTY_NEWLINE); | |
237 | if (backoff->t_holddown) | |
238 | { | |
239 | struct timeval remain = thread_timer_remain(backoff->t_holddown); | |
240 | vty_out(vty, "%s Still runs for %ld msec%s", | |
241 | prefix, remain.tv_sec * 1000 + remain.tv_usec/1000, VTY_NEWLINE); | |
242 | } | |
243 | else | |
244 | { | |
245 | vty_out(vty, "%s Inactive%s", prefix, VTY_NEWLINE); | |
246 | } | |
247 | ||
248 | vty_out(vty, "%sTimeToLearn timer: %ld msec%s", prefix, | |
249 | backoff->timetolearn, VTY_NEWLINE); | |
250 | if (backoff->t_timetolearn) | |
251 | { | |
252 | struct timeval remain = thread_timer_remain(backoff->t_timetolearn); | |
253 | vty_out(vty, "%s Still runs for %ld msec%s", | |
254 | prefix, remain.tv_sec * 1000 + remain.tv_usec/1000, VTY_NEWLINE); | |
255 | } | |
256 | else | |
257 | { | |
258 | vty_out(vty, "%s Inactive%s", prefix, VTY_NEWLINE); | |
259 | } | |
260 | ||
261 | vty_out(vty, "%sFirst event: %s%s", prefix, | |
262 | timeval_format(&backoff->first_event_time), VTY_NEWLINE); | |
263 | vty_out(vty, "%sLast event: %s%s", prefix, | |
264 | timeval_format(&backoff->last_event_time), VTY_NEWLINE); | |
265 | } | |
266 | ||
267 | DEFUN(spf_backoff_debug, | |
268 | spf_backoff_debug_cmd, | |
269 | "debug spf-delay-ietf", | |
270 | DEBUG_STR | |
271 | "SPF Back-off Debugging\n") | |
272 | { | |
273 | debug_spf_backoff = true; | |
274 | return CMD_SUCCESS; | |
275 | } | |
276 | ||
277 | DEFUN(no_spf_backoff_debug, | |
278 | no_spf_backoff_debug_cmd, | |
279 | "no debug spf-delay-ietf", | |
280 | NO_STR | |
281 | DEBUG_STR | |
282 | "SPF Back-off Debugging\n") | |
283 | { | |
284 | debug_spf_backoff = false; | |
285 | return CMD_SUCCESS; | |
286 | } | |
287 | ||
288 | int | |
289 | spf_backoff_write_config(struct vty *vty) | |
290 | { | |
291 | int written = 0; | |
292 | ||
293 | if (debug_spf_backoff) | |
294 | { | |
295 | vty_out(vty, "debug spf-delay-ietf%s", VTY_NEWLINE); | |
296 | written++; | |
297 | } | |
298 | ||
299 | return written; | |
300 | } | |
301 | ||
302 | void | |
303 | spf_backoff_cmd_init(void) | |
304 | { | |
305 | install_element(ENABLE_NODE, &spf_backoff_debug_cmd); | |
306 | install_element(CONFIG_NODE, &spf_backoff_debug_cmd); | |
307 | install_element(ENABLE_NODE, &no_spf_backoff_debug_cmd); | |
308 | install_element(CONFIG_NODE, &no_spf_backoff_debug_cmd); | |
309 | } | |
310 | ||
311 | long | |
312 | spf_backoff_init_delay(struct spf_backoff *backoff) | |
313 | { | |
314 | return backoff->init_delay; | |
315 | } | |
316 | ||
317 | long | |
318 | spf_backoff_short_delay(struct spf_backoff *backoff) | |
319 | { | |
320 | return backoff->short_delay; | |
321 | } | |
322 | ||
323 | long | |
324 | spf_backoff_long_delay(struct spf_backoff *backoff) | |
325 | { | |
326 | return backoff->long_delay; | |
327 | } | |
328 | ||
329 | long | |
330 | spf_backoff_holddown(struct spf_backoff *backoff) | |
331 | { | |
332 | return backoff->holddown; | |
333 | } | |
334 | ||
335 | long | |
336 | spf_backoff_timetolearn(struct spf_backoff *backoff) | |
337 | { | |
338 | return backoff->timetolearn; | |
339 | } |