]>
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 | * | |
896014f4 DL |
22 | * You should have received a copy of the GNU General Public License along |
23 | * with this program; see the file COPYING; if not, write to the Free Software | |
24 | * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA | |
c1d0d21f CF |
25 | */ |
26 | ||
27 | #include <zebra.h> | |
28 | ||
29 | #include "spf_backoff.h" | |
30 | ||
31 | #include "command.h" | |
32 | #include "memory.h" | |
33 | #include "thread.h" | |
34 | #include "vty.h" | |
35 | ||
36 | DEFINE_MTYPE_STATIC(LIB, SPF_BACKOFF, "SPF backoff") | |
37 | DEFINE_MTYPE_STATIC(LIB, SPF_BACKOFF_NAME, "SPF backoff name") | |
38 | ||
39 | static bool debug_spf_backoff = false; | |
d62a17ae | 40 | #define backoff_debug(...) \ |
41 | do { \ | |
42 | if (debug_spf_backoff) \ | |
43 | zlog_debug(__VA_ARGS__); \ | |
44 | } while (0) | |
c1d0d21f CF |
45 | |
46 | enum spf_backoff_state { | |
d62a17ae | 47 | SPF_BACKOFF_QUIET, |
48 | SPF_BACKOFF_SHORT_WAIT, | |
49 | SPF_BACKOFF_LONG_WAIT | |
c1d0d21f CF |
50 | }; |
51 | ||
52 | struct spf_backoff { | |
d62a17ae | 53 | struct thread_master *m; |
54 | ||
55 | /* Timers as per draft */ | |
56 | long init_delay; | |
57 | long short_delay; | |
58 | long long_delay; | |
59 | long holddown; | |
60 | long timetolearn; | |
61 | ||
62 | /* State machine */ | |
63 | enum spf_backoff_state state; | |
64 | struct thread *t_holddown; | |
65 | struct thread *t_timetolearn; | |
66 | ||
67 | /* For debugging */ | |
68 | char *name; | |
69 | struct timeval first_event_time; | |
70 | struct timeval last_event_time; | |
c1d0d21f CF |
71 | }; |
72 | ||
d62a17ae | 73 | static const char *spf_backoff_state2str(enum spf_backoff_state state) |
c1d0d21f | 74 | { |
d62a17ae | 75 | switch (state) { |
76 | case SPF_BACKOFF_QUIET: | |
77 | return "QUIET"; | |
78 | case SPF_BACKOFF_SHORT_WAIT: | |
79 | return "SHORT_WAIT"; | |
80 | case SPF_BACKOFF_LONG_WAIT: | |
81 | return "LONG_WAIT"; | |
82 | } | |
83 | return "???"; | |
c1d0d21f CF |
84 | } |
85 | ||
d62a17ae | 86 | struct spf_backoff *spf_backoff_new(struct thread_master *m, const char *name, |
87 | long init_delay, long short_delay, | |
88 | long long_delay, long holddown, | |
89 | long timetolearn) | |
c1d0d21f | 90 | { |
d62a17ae | 91 | struct spf_backoff *rv; |
c1d0d21f | 92 | |
d62a17ae | 93 | rv = XCALLOC(MTYPE_SPF_BACKOFF, sizeof(*rv)); |
94 | rv->m = m; | |
c1d0d21f | 95 | |
d62a17ae | 96 | rv->init_delay = init_delay; |
97 | rv->short_delay = short_delay; | |
98 | rv->long_delay = long_delay; | |
99 | rv->holddown = holddown; | |
100 | rv->timetolearn = timetolearn; | |
c1d0d21f | 101 | |
d62a17ae | 102 | rv->state = SPF_BACKOFF_QUIET; |
c1d0d21f | 103 | |
d62a17ae | 104 | rv->name = XSTRDUP(MTYPE_SPF_BACKOFF_NAME, name); |
105 | return rv; | |
c1d0d21f CF |
106 | } |
107 | ||
d62a17ae | 108 | void spf_backoff_free(struct spf_backoff *backoff) |
c1d0d21f | 109 | { |
d62a17ae | 110 | if (!backoff) |
111 | return; | |
c1d0d21f | 112 | |
d62a17ae | 113 | THREAD_TIMER_OFF(backoff->t_holddown); |
114 | THREAD_TIMER_OFF(backoff->t_timetolearn); | |
115 | XFREE(MTYPE_SPF_BACKOFF_NAME, backoff->name); | |
c1d0d21f | 116 | |
d62a17ae | 117 | XFREE(MTYPE_SPF_BACKOFF, backoff); |
c1d0d21f CF |
118 | } |
119 | ||
d62a17ae | 120 | static int spf_backoff_timetolearn_elapsed(struct thread *thread) |
c1d0d21f | 121 | { |
d62a17ae | 122 | struct spf_backoff *backoff = THREAD_ARG(thread); |
c1d0d21f | 123 | |
d62a17ae | 124 | backoff->t_timetolearn = NULL; |
125 | backoff->state = SPF_BACKOFF_LONG_WAIT; | |
126 | backoff_debug("SPF Back-off(%s) TIMETOLEARN elapsed, move to state %s", | |
127 | backoff->name, spf_backoff_state2str(backoff->state)); | |
128 | return 0; | |
c1d0d21f CF |
129 | } |
130 | ||
d62a17ae | 131 | static int spf_backoff_holddown_elapsed(struct thread *thread) |
c1d0d21f | 132 | { |
d62a17ae | 133 | struct spf_backoff *backoff = THREAD_ARG(thread); |
134 | ||
135 | backoff->t_holddown = NULL; | |
136 | THREAD_TIMER_OFF(backoff->t_timetolearn); | |
137 | timerclear(&backoff->first_event_time); | |
138 | backoff->state = SPF_BACKOFF_QUIET; | |
139 | backoff_debug("SPF Back-off(%s) HOLDDOWN elapsed, move to state %s", | |
140 | backoff->name, spf_backoff_state2str(backoff->state)); | |
141 | return 0; | |
c1d0d21f CF |
142 | } |
143 | ||
144 | long spf_backoff_schedule(struct spf_backoff *backoff) | |
145 | { | |
d62a17ae | 146 | long rv; |
147 | struct timeval now; | |
148 | ||
149 | gettimeofday(&now, NULL); | |
150 | ||
151 | backoff_debug("SPF Back-off(%s) schedule called in state %s", | |
152 | backoff->name, spf_backoff_state2str(backoff->state)); | |
153 | ||
154 | backoff->last_event_time = now; | |
155 | ||
156 | switch (backoff->state) { | |
157 | case SPF_BACKOFF_QUIET: | |
158 | backoff->state = SPF_BACKOFF_SHORT_WAIT; | |
159 | thread_add_timer_msec( | |
160 | backoff->m, spf_backoff_timetolearn_elapsed, backoff, | |
161 | backoff->timetolearn, &backoff->t_timetolearn); | |
162 | thread_add_timer_msec(backoff->m, spf_backoff_holddown_elapsed, | |
163 | backoff, backoff->holddown, | |
164 | &backoff->t_holddown); | |
165 | backoff->first_event_time = now; | |
166 | rv = backoff->init_delay; | |
167 | break; | |
168 | case SPF_BACKOFF_SHORT_WAIT: | |
169 | case SPF_BACKOFF_LONG_WAIT: | |
170 | THREAD_TIMER_OFF(backoff->t_holddown); | |
171 | thread_add_timer_msec(backoff->m, spf_backoff_holddown_elapsed, | |
172 | backoff, backoff->holddown, | |
173 | &backoff->t_holddown); | |
174 | if (backoff->state == SPF_BACKOFF_SHORT_WAIT) | |
175 | rv = backoff->short_delay; | |
176 | else | |
177 | rv = backoff->long_delay; | |
178 | break; | |
179 | default: | |
180 | zlog_warn("SPF Back-off(%s) in unknown state", backoff->name); | |
181 | rv = backoff->init_delay; | |
182 | } | |
183 | ||
184 | backoff_debug( | |
185 | "SPF Back-off(%s) changed state to %s and returned %ld delay", | |
186 | backoff->name, spf_backoff_state2str(backoff->state), rv); | |
187 | return rv; | |
c1d0d21f CF |
188 | } |
189 | ||
d62a17ae | 190 | static const char *timeval_format(struct timeval *tv) |
c1d0d21f | 191 | { |
d62a17ae | 192 | struct tm tm_store; |
193 | struct tm *tm; | |
194 | static char timebuf[256]; | |
c1d0d21f | 195 | |
d62a17ae | 196 | if (!tv->tv_sec && !tv->tv_usec) |
197 | return "(never)"; | |
c1d0d21f | 198 | |
d62a17ae | 199 | tm = localtime_r(&tv->tv_sec, &tm_store); |
200 | if (!tm | |
201 | || strftime(timebuf, sizeof(timebuf), "%Z %a %Y-%m-%d %H:%M:%S", tm) | |
202 | == 0) { | |
203 | return "???"; | |
204 | } | |
c1d0d21f | 205 | |
d62a17ae | 206 | size_t offset = strlen(timebuf); |
207 | snprintf(timebuf + offset, sizeof(timebuf) - offset, ".%ld", | |
a37bd5e0 | 208 | (long int)tv->tv_usec); |
c1d0d21f | 209 | |
d62a17ae | 210 | return timebuf; |
c1d0d21f CF |
211 | } |
212 | ||
d62a17ae | 213 | void spf_backoff_show(struct spf_backoff *backoff, struct vty *vty, |
214 | const char *prefix) | |
c1d0d21f | 215 | { |
d62a17ae | 216 | vty_out(vty, "%sCurrent state: %s\n", prefix, |
217 | spf_backoff_state2str(backoff->state)); | |
218 | vty_out(vty, "%sInit timer: %ld msec\n", prefix, | |
219 | backoff->init_delay); | |
220 | vty_out(vty, "%sShort timer: %ld msec\n", prefix, | |
221 | backoff->short_delay); | |
222 | vty_out(vty, "%sLong timer: %ld msec\n", prefix, | |
223 | backoff->long_delay); | |
224 | vty_out(vty, "%sHolddown timer: %ld msec\n", prefix, | |
225 | backoff->holddown); | |
226 | if (backoff->t_holddown) { | |
227 | struct timeval remain = | |
228 | thread_timer_remain(backoff->t_holddown); | |
a97986ff | 229 | vty_out(vty, "%s Still runs for %lld msec\n", |
996c9314 LB |
230 | prefix, |
231 | (long long)remain.tv_sec * 1000 | |
a97986ff | 232 | + remain.tv_usec / 1000); |
d62a17ae | 233 | } else { |
234 | vty_out(vty, "%s Inactive\n", prefix); | |
235 | } | |
236 | ||
237 | vty_out(vty, "%sTimeToLearn timer: %ld msec\n", prefix, | |
238 | backoff->timetolearn); | |
239 | if (backoff->t_timetolearn) { | |
240 | struct timeval remain = | |
241 | thread_timer_remain(backoff->t_timetolearn); | |
a97986ff | 242 | vty_out(vty, "%s Still runs for %lld msec\n", |
996c9314 LB |
243 | prefix, |
244 | (long long)remain.tv_sec * 1000 | |
a97986ff | 245 | + remain.tv_usec / 1000); |
d62a17ae | 246 | } else { |
247 | vty_out(vty, "%s Inactive\n", prefix); | |
248 | } | |
249 | ||
250 | vty_out(vty, "%sFirst event: %s\n", prefix, | |
251 | timeval_format(&backoff->first_event_time)); | |
252 | vty_out(vty, "%sLast event: %s\n", prefix, | |
253 | timeval_format(&backoff->last_event_time)); | |
c1d0d21f CF |
254 | } |
255 | ||
256 | DEFUN(spf_backoff_debug, | |
257 | spf_backoff_debug_cmd, | |
258 | "debug spf-delay-ietf", | |
259 | DEBUG_STR | |
260 | "SPF Back-off Debugging\n") | |
261 | { | |
d62a17ae | 262 | debug_spf_backoff = true; |
263 | return CMD_SUCCESS; | |
c1d0d21f CF |
264 | } |
265 | ||
266 | DEFUN(no_spf_backoff_debug, | |
267 | no_spf_backoff_debug_cmd, | |
268 | "no debug spf-delay-ietf", | |
269 | NO_STR | |
270 | DEBUG_STR | |
271 | "SPF Back-off Debugging\n") | |
272 | { | |
d62a17ae | 273 | debug_spf_backoff = false; |
274 | return CMD_SUCCESS; | |
c1d0d21f CF |
275 | } |
276 | ||
d62a17ae | 277 | int spf_backoff_write_config(struct vty *vty) |
c1d0d21f | 278 | { |
d62a17ae | 279 | int written = 0; |
c1d0d21f | 280 | |
d62a17ae | 281 | if (debug_spf_backoff) { |
282 | vty_out(vty, "debug spf-delay-ietf\n"); | |
283 | written++; | |
284 | } | |
c1d0d21f | 285 | |
d62a17ae | 286 | return written; |
c1d0d21f CF |
287 | } |
288 | ||
d62a17ae | 289 | void spf_backoff_cmd_init(void) |
c1d0d21f | 290 | { |
d62a17ae | 291 | install_element(ENABLE_NODE, &spf_backoff_debug_cmd); |
292 | install_element(CONFIG_NODE, &spf_backoff_debug_cmd); | |
293 | install_element(ENABLE_NODE, &no_spf_backoff_debug_cmd); | |
294 | install_element(CONFIG_NODE, &no_spf_backoff_debug_cmd); | |
c1d0d21f CF |
295 | } |
296 | ||
d62a17ae | 297 | long spf_backoff_init_delay(struct spf_backoff *backoff) |
c1d0d21f | 298 | { |
d62a17ae | 299 | return backoff->init_delay; |
c1d0d21f CF |
300 | } |
301 | ||
d62a17ae | 302 | long spf_backoff_short_delay(struct spf_backoff *backoff) |
c1d0d21f | 303 | { |
d62a17ae | 304 | return backoff->short_delay; |
c1d0d21f CF |
305 | } |
306 | ||
d62a17ae | 307 | long spf_backoff_long_delay(struct spf_backoff *backoff) |
c1d0d21f | 308 | { |
d62a17ae | 309 | return backoff->long_delay; |
c1d0d21f CF |
310 | } |
311 | ||
d62a17ae | 312 | long spf_backoff_holddown(struct spf_backoff *backoff) |
c1d0d21f | 313 | { |
d62a17ae | 314 | return backoff->holddown; |
c1d0d21f CF |
315 | } |
316 | ||
d62a17ae | 317 | long spf_backoff_timetolearn(struct spf_backoff *backoff) |
c1d0d21f | 318 | { |
d62a17ae | 319 | return backoff->timetolearn; |
c1d0d21f | 320 | } |